Joining in query decomposition I have a question about query decomposition and localization, as in 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:



Would the following also be possible (just switching the order of PROJ and EMP):
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.