I have a question about query decomposition and localization, as in here:

enter image description here

When joining 3 tables (here EMP, ASG and PROJ) is there any specifiy order, when to join which table?
Why ASG and EMP are joined first, then the "result" is joined with PROJ?

Can all the 3 tables not be joined parallelly:

enter image description here

Would the following also be possible (just switching the order of PROJ and EMP): enter image description here

  • Today's databases have their own optimizers. They do not take into account on how you write it. If you want the theoretical approach then you should start with the most limiting join and then do the others. Since you do not give the description of the entities there is not much to say. From what I understand only that you should start with the entity that holds the PNAME and DUR (PROJ?). Looks like the last possibility. – Marco Aug 16 '15 at 20:02
  • 1
    @Marco: I believe by "They do not take into account on how you write it" you probably mean that today's databases may change the actual order of execution of the query for optimisation purposes making sure the results would match the logical order of the query's execution. (And so they do take into account how you've written your statement.) – Andriy M Aug 17 '15 at 5:54
  • @Andriy M: You are right that is what I meant. The optimizer is taking over the work to find the best execution path. – Marco Aug 17 '15 at 6:33

The problem as shown is transforming relational calculus, of which SQL is a variant, into relational algebra, which consists of the original operators Codd defined on relations. I will assume that the EMP, ASG, and PROJ represent employees, projects, and the assignment of employees to projects. The query, as stated in relational calculus, is asking for the names of employees who aren't J. Doe and who are assigned to the CAD/CAM project for a duration of 12 or 24 months. The operator in question, natural join, is associative - which means the ability to group the operands in any way without changing the result. So it does not matter the order in which the EMP, ASG, and PROG are joined. This is because natural join is really just the product of EMP, ASG, and PROG, then restricted by EMP not J. Doe, ASG DUR 12 or 24, PROG CAD/CAM, EMP.ENO = ASG.ENO, and ASG.PNO = PROJ.PNO, then only the ENAME column projected out. When you think of it this way, you realize that to first get the product of the rows in EMP, ASG, and PROJ it makes no difference the order you multiply them. This corresponds to integer algebra, where it makes no difference in what order you multiple 3, 6, and 2. Thinking of it this way also shows why you can't do the join "in parallel." You can't take the product of ASG and PROJ, and the product of ASG and EMP, and then... what? No more than you could take the product of 3 and 6, which is 18, and 6 and 2, which is 12, and then... what? to get what is the right answer - 36.

This is a great question as it shows the job of the optimizer when parsing relational calculus is to first build a corresponding tree of equivalent operators in relational algebra. There are many ways to build the tree that yield the same result, and as Marco pointed out the optimizer's job is to figure out which of the ways will cost the least. Part of that cost estimation is determining which access methods (ie indexes) are available to execute each relational operator and the cost of each. In this way, access methods can be added and removed without impacting the formulation of the query. This was a huge benefit over the navigation systems which pre-date the SQL DBMS'. A great reference on this is Fabian Pascal's book SQL and Relational Basics which, while written over 20 years ago still provides the best explanation I have found of these concepts. It is unfortunately out of print now but you may be able to purchase an old copy. You can however purchase his Practical Database Foundation Series on his website. I would also highly recommend any of the writings of Chris Date, Hugh Darwen, and/or David McGoveran on the topic.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.