Finding nonrecursive envelopes for Datalog predicate

ABSTRACT

In this paper, we study the ability of data-independent conjunctive expressions (envelopes) to approximate fixpoint of Datalog predicates. We show that no effective procedure exists for finding envelopes that best approximate the fix-point (tight envelopes). Moreover, the problem of determining existence of tight envelopes is undecidable. The relationship between tight envelopes and the boundedness property is explored. Although the property of having tight envelopes seems weaker than boundedness, we note that a predicate can have a tight (lower) envelope iff it is bounded. On the other hand, there exist Datalog predicates that are not bounded but have tight (upper) envelopes. We relax our requirement for tight envelopes and settle for connected envelopes. An algorithm to determine connected envelopes for Datalog predicates is presented. We mention several applications of envelopes.

REFERENCES

• AU79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• CM77: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• C91: Surajit Chaudhuri, Detecting redundant tuples during query evaluation, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.115-126, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113424]
• CV92: Surajit Chaudhuri , Moshe Y. Vardi, On the equivalence of recursive and nonrecursive datalog programs, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.55-66, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137109]
• GMSV87: Gaifman, H., Mairson, H., Sagiv, Y., Vardi M.Y.: Undecidable optimization problems for database logic programs. Proc. 2nd IEEE Syrup. on Logic zn Computer Science, Ithaca, 1987, pp. 106-115.
• HKMV91: Gerd G. Hillebrand , Paris C. Kanellakis , Harry G. Mairson , Moshe Y. Vardi, Tools for Datalog boundedness, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-12, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113414]
• KA89: P. Kanellakis , S. Abiteboul, Database theory column, ACM SIGACT News, v.20 n.4, p.17-23, Nov. 1989 [doi>10.1145/74074.74077]
• HR92: Harland J., Ramamohanarao K.: Constraints for Query Optimization in Deductive Databases, Proc. of the Second Far East Workshop on Future Database Systems, Kyoto, 1992.
• M90: R. van der Meyden, Recursively indefinite databases (extended abstract), Proceedings of the third international conference on database theory on Database theory, p.364-378, November 1990, Paris, France
• S90: Yehoshua Sagiv, Is there anything better than magic, Proceedings of the 1990 North American conference on Logic programming, p.235-254, January 1990, Austin, Texas, United States
• SY81: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• S*79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• U89: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• Va82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• Va88: Moshe Y. Vardi, Decidability and undecidability results for boundedness of linear recursive queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.341-351, March 1988, Austin, Texas, United States [doi>10.1145/308386.308470]

INDEX TERMS

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

          Nouns: Datalog

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Languages, Theory, Verification