Queries determined by views: pack your views

ABSTRACT

A query Q is determined by a set of views V if, whenever V (I1) = V (I2) for two database instances I1, I2 then also Q(I1) = Q(I2). Does this imply that Q can be rewritten as a query Q0 that only uses the views V?.

For first-order (FO) queries and view definitions over possibly infinite databases, the answer is yes, as follows from old results of Beth and Craig. We say that FO is complete for FO-to-FO rewritings. However, Nash, Segoufin and Vianu (2007) prove that if the query and the view definitions are given by conjunctive queries, then it might not be possible to formulate Q' as a conjunctive query. In other words, CQ is not complete for CQ-to-CQ rewritings.

Here we consider queries and view definitions in the packed fragment (PF) of first-order logic. This is a generalization of the guarded fragment, a fragment of particular interest to database theory. Gottlob et.al. 2002 show that the guarded conjunctive queries are exactly the acyclic queries. Leinders et.al. 2005 characterize the entire guarded fragment by the semijoin algebra.

We show that for both finite and unrestricted databases, PF is complete for PF-to-PF rewritings. The same holds for packed (unions of) conjunctive queries. In both cases, we provide algorithms for testing whether a query is determined by a set of views, and for actually rewriting Q to Q'. To compare: these problems are undecidable for full FO, and still open for conjunctive queries.

REFERENCES

• 1: H. Andréka, J. van Benthem, and I. Németi. Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27(3):217--274, 1998.
• 2: Franz Baader , Werner Nutt, Basic description logics, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 3: E. Beth. On Padoa's method in the theory of definition. Indagationes Mathematicae, 15:330--339, 1953.
• 4: E. Beth. Formal methods, An introduction to symbolic logic and to the study of effective operations in arithmetic and logic. Number 4 in Synthese Library. Reidel, Dordrecht, 1962.
• 5: 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]
• 6: C. Chang and H. Keisler. Model Theory. North-Holland, 1973.
• 7: W. Craig. Three uses of the Herbrand-Gentzen theorem in relation to model theory and proof theory. Journal of Symbolic Logic, 22:269--285, 1957.
• 8: K. Doets. Basic Model Theory. CSLI Publications, Stanford, 1996.
• 9: Melvin Fitting, First-order logic and automated theorem proving (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 10: Jörg Flum , Markus Frick , Martin Grohe, Query Evaluation via Tree-Decompositions, Proceedings of the 8th International Conference on Database Theory, p.22-38, January 04-06, 2001
• 11: H. Friedman. The complexity of explicit definitions. Advances in Mathematics, 20(1):18--29, 1976.
• 12: Georg Gottlob , Nicola Leone , Francesco Scarcello, Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width, Journal of Computer and System Sciences, v.66 n.4, p.775-808, 1 June 2003 [doi>10.1016/S0022-0000(03)00030-8]
• 13: E. Grädel. On the restraining power of guards. Journal of Symbolic Logic, 64(4):1719--1742, 1999.
• 14: Erich Grädel, Guarded fixed point logics and the monadic theory of countable trees, Theoretical Computer Science, v.288 n.1, p.129-152, 9 October 2002 [doi>10.1016/S0304-3975(01)00151-7 ]
• 15: Stéphane Grumbach , Leonardo Tininini, On the content of materialized aggregate views, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.47-57, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335174]
• 16: I. Hodkinson. Loosely guarded fragment of first-order logic has the finite model property. Studia Logica, 70(2):205--240, 2002.
• 17: E. Hoogland. Algebraic characterizations of various beth definability properties. Studia Logica, 65(1):91--112, 2000.
• 18: E. Hoogland and M. Marx. Interpolation in the guarded fragment. Studia Logica, 70(3):273--409, 2002.
• 19: Eva Hoogland , Maarten Marx , Martin Otto, Beth Definability for the Guarded Fragment, Proceedings of the 6th International Conference on Logic Programming and Automated Reasoning, p.273-285, September 06-10, 1999
• 20: Dirk Leinders , Maarten Marx , Jerzy Tyszkiewicz , Jan Bussche, The Semijoin Algebra and the Guarded Fragment, Journal of Logic, Language and Information, v.14 n.3, p.331-343, June 2005 [doi>10.1007/s10849-005-5789-8]
• 21: M. Marx and Y. Venema. Local variations on a loose theme: modal logic and decidability. In E. Grädel, P. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, Y. Venema, and S. Weinstein, editors, Finite Model Theory and its Applications. Springer-Verlag, 2007.
• 22: A. Nash, L. Segoufin, and V. Vianu. Determinacy and rewriting of conjunctive queries using views: a progress report. In Proceedings ICDT 2007, to appear.
• 23: D. Pigozzi. Amalgamation, congruence extension and interpolation properties in algebras. Algebra Universalis, 1:269--349, 1972.
• 24: Luc Segoufin , Victor Vianu, Views and queries: determinacy and rewriting, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065174]
• 25: A. Tarski. Einige methodologische Untersuchungen über die Definierbarkeit der Begriffe. Erkenntnis, 5:80--100, 1935.
• 26: A. Tarski. Logic, semantics and metamathematics. Clarendon, Oxford, 1956.
• 27: B. ten Cate. Interpolation for extended modal languages. Journal of Symbolic Logic, 70(1):223--234, 2005.
• 28: B. ten Cate, W. Conradi, M. Marx, and Y. Venema. Definitorially complete description logics. In Proceedings KR 2006, pages 79--89, 2006.
• 29: Jan Van den Bussche, Applications of Alfred Tarski's Ideas in Database Theory, Proceedings of the 15th International Workshop on Computer Science Logic, p.20-37, September 10-13, 2001
• 30: P. van Ulsen. E. W. Beth als logicus. PhD thesis, University of Amsterdam, 2000.
• 31: A. Visser. Uniform interpolation and layered bisimulation. In Gädel '96 (Brno, 1996), volume 6 of Lecture Notes Logic, pages 139--164. Springer, Berlin, 1996.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

General Terms:
Languages, Theory

Keywords:
definability, guarded fragment, query rewriting, views