Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've converted the following SQL query:

FROM dog d, works_at w
WHERE (d.owner_name = w.person_name) AND (w.kennal_name = "Breeders");

into the following expression tree:

enter image description here

My main question is how does one apply heuristics to optimise an expression tree?

And is it OK to use the abbreviaions (e.g. dog as d) in the query tree, or do I have to write out dog.owner_name in place of d.owner_name?

share|improve this question
Just an observation, it's spelt "kennel" – Phil Apr 16 '14 at 16:07
up vote 1 down vote accepted

I've just figured out how to do this, so I'll answer it in case anyone else has a similar problem.

  1. Introduced SELECTs as far down the tree as possible, to reduce the number of comparisons needed.
  2. Introduced PROJECTs as far down the tree too, to reduce the number of columns.
  3. Used a JOIN wherever a CARTESIAN PRODUCT was followed by a SELECT. (There weren't any in my tree but this is what's done apparently).

My final tree looks like this:

optimised canonical query tree

share|improve this answer
Mark your own answer as correct - that way people searching for similar material in the future can get what they need more easily. – Vérace Jun 18 '14 at 9:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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