Normalization

Canonical form:

?{ e | x1 ? path1, …, xn ? pathn, pred }

(path is a cascade of projections: X.A1.A2…Am)

Two important normalization rules:

?{ e | , x ? ?{ u | }, }

? ?{ e | , , x ? u, }

?{ e | , ?{ pred | }, }

? ?{ e | , , pred, }

?

?

?

?

?

?

?

?

?

?

?

?

Previous slide

Next slide

Back to first slide

View graphic version

Comprehensions can put into a canonical form by a simple algorithm, called the normalization algorithm. In this canonical form, generators are over simple domains (path expressions). Here are two normalization rules. The first rule flattens a nested comprehension in which a generator ranges over the result of another comprehension. In that case, the qualifiers of the inner comprehension are promoted inside the qualifiers of the outer comprehension and the range variable is bound to the head of the inner comprehension. The other rule flattens a nested comprehension where the inner comprehension denotes an existential quantification.