On the expressive power of datalog: tools and a case study

ABSTRACT

We study here the language Datalog(≠), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules. We view Datalog(≠) as a fragment of an infinitary logic L&ohgr; and show that L&ohgr; can be characterized in terms of certain two-person pebble games. This characterization provides us with tools for investigating the expressive power of Datalog(≠). As a case study, we classify the expressibility of fixed subgraph homeomorphism queries on directed graphs. Fortune et al. [FHW80] classified the computational complexity of these queries by establishing two dichotomies, which are proper only if P ≠ NP. Without using any complexity-theoretic assumptions, we show here that the two dichotomies are indeed proper in terms of expressibility in Datalog(≠).

REFERENCES

• AG89: Miklos Ajtai , Yuri Gurevich, Datalog vs. first-order logic, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.562-588, December 1994, Research Triangle Park, North Carolina, United States
• 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]
• Bar77: j. Barwise, On Moschovakis closure ordinals, Journal of Symbolic Logic 42, 1977, pp. 292-296.
• BG87: Andreas Blass , Yuri Gurevich, Existential fixed-point logic, Computation theory and logic, Springer-Verlag, London, 1987
• Bol79: B. Bollobas, Graph Theory, Springer- Verlag, 1979.
• CH80: A. Chandra and D. Hard, Computable queries for relational databases, Journal of Computer and System Sciences 21, 1980, pp. 156-178.
• CH82: A. Chandra and D. Hard, Structure and complexity of relational queries, journal of Computer and System Sciences 25, 1982, pp. 99-128.
• CH85: A. Chandra and D. Harel, Horn clause queries and generalizations, Journal of Logic Programming 1, 1985, pp. 1- 15.
• Coo74: S.A. Cook, An obsgrvation of timestorage trade-off, Journal of Computer and System Sciences 9, 1974, pp. 308-316.
• deR87: M. de Rougemont, Second-order and inductive definability on finite structures, Zeitschr. f. math. Logik und Grundlagen d. Math. 33, 1987, pp. 47-63.
• FHW80: S. Fortune, J. Hopcroft, and J. Wyllie, The directed homeomorphism problem, Theoretical Compuler Science 10, 1980, pp. 111-121.
• Gai82: H. Gaifman, On local and nonlocal properties, Logic Colloquium '81 (j. Stern, ed.), North Holland, 1982, pp. 105-135.
• GMSV87: H. Gaifman, H. Mairson, Y. Sagiv, and M. Y. Vardi, Undecidable optimization problems for database logic programs, Proc. 2nd IEEE Syrup. on Logic in Computer Science, 1987, pp. 106-115.
• GS53: D. Gale and F. M. Stewart, Infinite games of perfect information, Ann. Math. Studies 28, 1953, pp. 245-266.
• GS86: Y. Gurevich and S. Shelah, Fixedpoint extensions of first-order logic, Annals of Pure and Applied Logic 32, 1986, pp. 265-280.
• Imm82: N. Immerman, Upper and lower bounds for first-order expressibility, Journal of Computer and System Sciences 25, 1982, pp. 76-98.
• Imm86: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• Kei71: H.J. Keisler, Model Theory for Infinitary Logic, North Holland, 1971.
• Kol85: Phokion G. Kolaitis, On Asymptotic Probability of Inductive Queries and Their Decision Problem, Proceedings of the Conference on Logic of Programs, p.153-166, June 17-19, 1985
• KV89: Ph. G. Kolaitis and M. Y. Vardi, 0-1 laws and decision problems for infinitary logics, 1989. Forthcoming.
• LM89: V. S. Lakshmanan , A. O. Mendelzon, Inductive pebble games and the expressive power of datalog, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.301-310, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73751]
• Mos74: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• Pap85: C.H. Papadimitriou, A note on the expressive power of Prolog, Bulletin of the EA TCS 26, 1985, pp. 21-23.
• Shm87: 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]
• Ull89: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• Var82: 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]

INDEX TERMS

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

          Nouns: Datalog

General Terms:
Design, Languages, Management, Performance, Theory, Verification