Constraints and Redundancy in Datalog

Reference: Levy, A. & Sagiv, Y. Constraints and Redundancy in Datalog. 1992.

Abstract: Two types of redundancies in datalog programs are considered. Redundancy based on reachability eliminates rules and predicates that do not participate in any derivation tree of a fact for the query predicate. Redundancy based on irrelevance is similar, but considers only minimal derivation trees, that is, derivation trees having no pair of identical atoms, such that one is an ancestor of the other. Algorithms for detecting these redundancies are given, including the case of programs with constraint literals. These algortihms not only detect redundancies in the presence of constraints, but also push constraints from the given query and rules to the EDB predicates. Under certain assumptions discussed in the paper, the constraints are pushed to the EDB as tightly as possible.

Full paper available as ps.

Jump to... [KSL] [SMI] [Reports by Author] [Reports by KSL Number] [Reports by Year]
Send mail to: ksl-info@ksl.stanford.edu to send a message to the maintainer of the KSL Reports.