A call to regularity

ABSTRACT

From the mid 1980s to the mid 1990s, with the active involvement of Paris C. Kanellakis, a major theme in database theory was the study of Datalog, the language of logic programs without function symbols. Unfortunately, most decision problems involving Datalog turned out to be undecidable. Furthermore, well-behaved fragments of Datalog turned out to be rather restrictive and unnatural. Surprisingly, a natural and quite general fragment of Datalog did emerge in the mid 1990s, in the context of semistructured data. This fragment is the class of regular queries, whose basic element is that of regular path queries. In this talk I describe the class of regular queries and its well-behavedness in the context of view-based query processing.

REFERENCES

• 1: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Rewriting of regular expressions and regular path queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.194-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303996]
• 2: Answering Regular Path Queries Using Views, Proceedings of the 16th International Conference on Data Engineering, p.389, February 28-March 03, 2000
• 3: D. Calvanese, G. De~Giacomo, M. Lenzerini, and M. Y. Vardi. Containment of conjunctive regular path queries with inverse. In Proc. of the 7th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR~2000), pages 176--185, 2000.
• 4: Diego Calvanese , Moshe Y. Vardi , Giuseppe de Giacomo , Maurizio Lenzerini, View-based query processing for regular path queries with inverse, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.58-66, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335207]
• 5: Diego Calvanese , Giuseppe de Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-Based Query Processing and Constraint Satisfaction, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, p.361, June 26-29, 2000
• 6: D. Calvanese, G. De~Giacomo, M. Lenzerini, and M. Y. Vardi. What is query rewriting? In Proc. of the 7th Int. Workshop on Knowledge Representation meets Databases (KRDB~2000), pages 17--27. CEUR Electronic Workshop Proceedings, http://ceur-ws.org/Vol-29/, 2000.
• 7: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Lossless regular views, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543646]
• 8: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-Based Query Answering and Query Containment over Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.40-61, September 08-10, 2001
• 9: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-based query containment, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.56-67, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773160]

INDEX TERMS

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

General Terms:
Languages

Keywords:
database, datalog, query languages, regular path queries, semistructured data