Uniform Equivalence

Equivalence:

• Two datalog programs X and Y are equivalent if, for every set of extensional predicates, the two programs produce the same output.

• Undecidable

Uniform Equivalence:

• X and Y are equivalent if, for every set of extensional and intensional predicates the two plans produce the same output

• Decidable

• Implies equivalence

[Sagiv 88]

Previous slide

Next slide

Back to first slide

View graphic version