0
$\begingroup$

Let's say we have a database with a given table named food. The food table has many columns but we are interested in only 3 of them:

  1. buyorsell, which specifies if the food is for selling or buying.
  2. amount, which is the amount of food to be bought or sold.
  3. isVegan, which is set true if the food is vegan.

The goal is to find the best match between 2 rows. The best match should satisfy the following rules:

  1. Both rows have the same value for 'isVegan'
  2. One row should be buy/sell and the other row must be the opposite
  3. Both amounts must be equal

The table will have millions of rows and the table is changing rapidly.

What is the right algorithm in matters of speed and resource usage for this matching problem?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Please take some time to improve your post. Your sentences are missing words, you talk about four columns and then list only three, and it is unclear how your notion of "best" is non-binary. Furthermore, how are "speed" and "runtime" different? Which cost measures are the most important to you? $\endgroup$ Commented Oct 17, 2016 at 23:35
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ Commented Oct 17, 2016 at 23:35

1 Answer 1

Reset to default
1
$\begingroup$

Assuming we're talking about a relational database, a straightforward query would be to do a theta-join on two copies of the food relation, renamed $a$ and $b$, with the condition $$ \theta = (a.isvegan)\land\neg(a.buyorsell=b.buyorsell)\land(a.amount=b.amount) $$ Without knowing the internal workings of the DB engine, your question about the "right" algorithm to use is impossible to answer. For instance, does the engine use, say, merge join or hash join to answer the query; is the table sorted by some attribute, do you have indexes to help you, if so how are they implemented?

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think you want (𝑎.𝑖𝑠𝑣𝑒𝑔𝑎𝑛 = b.𝑖𝑠𝑣𝑒𝑔𝑎𝑛) for the first term. $\endgroup$ Commented May 7, 2024 at 15:51

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.