Dotaz na tranzitivní uzávěr (2)

• 3. Lemma: Je-li E výraz relační algebry, pak pro dostatečně velké s

• E(Rs) b1,...,bk |b1,...,bk),

• kde k 1 a  je formule v disjunktivní normální formě.

• Atomické formule v mají speciální tvar:

• bi = aj, bi aj,

• bi = bj + c nebo bi bj + c, kde c je (ne nutně kladná)

• konstanta, přičemž

• bj + c je zkratka pro “takové am, pro které bj = am-c“

• Doména interpretace pro ohodnocení proměnných bj je s.

• Pz.: bi = bj + c bi je za bj ve vzdálenosti c uzlů.