Constraints and redundancy in datalog

ABSTRACT

Two types of redundancies in datalog program 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 algorithms 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.

REFERENCES

• BK*89: Balbin, I., Kemp, D.B., Meenakshi, K., and Ramamohanarao, K. Propagating constraints in recursive deductive databases. North American Conf. on Logic Programming, 1989, pp. 16- 20.
• BS91: Alexander Brodsky , Yehoshua Sagiv, Inference of inequality constraints in logic programs (extended abstracts), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-240, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113434]
• Co91: Bruno Courcelle, Recursive queries and context-free graph grammars, Theoretical Computer Science, v.78 n.1, p.217-244, Jan. 21, 1991
• KKR90: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• Ki88: Kifer, M. On safety, domain independence, and capturability of database queries. Proc. Int. Conf. on Data and Knowledge Bases, Jerusalem, 1988.
• Kl88: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• MF*90: Inderpal Singh Mumick , Sheldon J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic conditions, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.314-330, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298584]
• Sag88: Y. Sagiv, Optimizing datalog programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• Sar90: Yatin P. Saraiya, Hard problems for simple logic programs, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.64-73, May 23-26, 1990, Atlantic City, New Jersey, United States
• Sh87: O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.237-249, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28685]
• SS90: Seppo Sippu , Eljas Soisalon-Soininen, Multiple SIP strategies and bottom-up adorning in logic query optimization, Proceedings of the third international conference on database theory on Database theory, p.485-498, November 1990, Paris, France
• Ull89: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• VG90: Allen van Gelder, Deriving constraints among argument sizes in logic programs (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.47-60, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298541]
• Va89: M. Y. Vardi, Invited talk: automata theory for database theoreticians, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.83-92, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73729]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Languages, Theory, Verification