Datalog expressiveness of chain queries: grammar tools and characterizations

ABSTRACT

A chain query seeks, for each input database (viewed as directed graph), all pairs of start and end nodes of paths whose labels spell words in an associated (possibly non context-free) language over some binary predicates. We study the expressive power of Datalog for chain queries. Extending context-free productions with labels, we introduce a new tool called “indexed positive programmed grammarr” (IPPG). Three variations of IPPG are introduced to characterize chain queries computable (i) by linear Datalog, (ii) by “semi-linear Datalog”, and (iii) by general Datalog, respectively, under a natural “addressable” condition.

REFERENCES

• AC89: F. Afrati , S. S. Cosmadakis, Expressiveness of restricted recursive queries, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.113-126, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73018]
• ACY91: Foto Afrati , Stavros S. Cosmadakis , Mihalis Yannakakis, On Datalog vs. polynomial time (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.13-25, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113415]
• AG90: 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
• Aho68: Alfred V. Aho, Indexed Grammars—An Extension of Context-Free Grammars, Journal of the ACM (JACM), v.15 n.4, p.647-671, Oct. 1968 [doi>10.1145/321479.321488]
• 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]
• CH85: A.K. Chandra and D. Harel. Horn clauses and generalizations. Yournal of Logic Programming, 1(1):1-15, 1985.
• DG91: G. Dong and S. Ginsburg. On decomposing chain datalog programs into 7) (Left-)Linear sequences of chain rules. Technical report, Melbourne University, 1991.
• Don91a: G. Dong. A note on idb-width and undecidability for Datalog linearization of chain queries. Technical Report TR- 91/23, Computer Science Department, The University of Melbourne, 1991.
• Don91b: Guozhu Dong, On datalog linearization of chain queries, Theoretical studies in computer science: thr, Academic Press Professional, Inc., San Diego, CA, 1991
• KV90: Phokion G. Kolaitis , Moshe Y. Vardi, On the expressive power of datalog: tools and a case study, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.61-71, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298542]
• Llo87: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 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]
• Pap85: C. H. Papadimitriou. A note on the expressive power of prolog. In Bulletin EATCS. June 1985.
• Ros69: Daniel J. Rosenkrantz, Programmed Grammars and Classes of Formal Languages, Journal of the ACM (JACM), v.16 n.1, p.107-131, Jan. 1969 [doi>10.1145/321495.321504]
• Sal73: Arto Salomaa, Formal languages, Academic Press Professional, Inc., San Diego, CA, 1987
• 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]
• UV88: J.D. Ullman and A. Van Gelder. Parallel complexity of logical query programs. Algomthmica, 3:5-42, 1988.

INDEX TERMS

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

          Nouns: Datalog

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Languages