Example of Query Unnesting

Find all students that have taken all DB courses:

?{ s | s ? Students,

?{ ?{ t.cno = c.cno | t ? Transcript, t.id = s.id }

| c ? Courses, c.title = “DB” } }

Previous slide

Next slide

Back to first slide

View graphic version

Our query unnesting algorithm is very simple and in a way generalizes the outerjoin-grouping technique already in use in relational databases. Consider the above double-nested query, which finds all the students who have taken all database courses. First we translate each comprehension into an algebraic form as it shown. Each form that corresponds to an inner comprehension has one input and one output. The nesting appears in the arguments of an operator, such as a predicate. These are the small dark boxes which, when opened, they contain other algebraic operators.