Diego Calvanese
Giuseppe De Giacomo
Skip Abstract Section
Abstract
Query containment and query answering are two important computational tasks in databases. While query answering amounts to computing the result of a query over a database, query containment is the problem of checking whether, for every database, the result of one query is a subset of the result of another query.
In this article, we deal with unions of conjunctive queries, and we address query containment and query answering under description logic constraints. Every such constraint is essentially an inclusion dependency between concepts and relations, and their expressive power is due to the possibility of using complex expressions in the specification of the dependencies, for example, intersection and difference of relations, special forms of quantification, regular expressions over binary relations. These types of constraints capture a great variety of data models, including the relational, the entity-relationship, and the object-oriented model, all extended with various forms of constraints. They also capture the basic features of the ontology languages used in the context of the Semantic Web.
We present the following results on both query containment and query answering. We provide a method for query containment under description logic constraints, thus showing that the problem is decidable, and analyze its computational complexity. We prove that query containment is undecidable in the case where we allow inequalities in the right-hand-side query, even for very simple constraints and queries. We show that query answering under description logic constraints can be reduced to query containment, and illustrate how such a reduction provides upper-bound results with respect to both combined and data complexity.
- Abiteboul, S. and Duschka, O. 1998. Complexity of answering queries using materialized views. In Proceedings of the 17th ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS'98). 254--265. Google Scholar
Digital Library
- Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley, Reading, MA. Google ScholarDigital Library
- Aho, A. V., Sagiv, Y., and Ullman, J. D. 1979a. Efficient optimization of a class of relational expressions. ACM Trans. Database Syst. 4, 297--314. Google ScholarDigital Library
- Aho, A. V., Sagiv, Y., and Ullman, J. D. 1979b. Equivalence among relational expressions. SIAM J. Comput. 8, 218--246.Google ScholarCross Ref
- Amir, K., Park, S., Tewari, R., and Padmanabhan, S. 2003. Scalable template-based query containment checking for Web semantic caches. In Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE 2003). 493--504.Google Scholar
- Baader, F., Calvanese, D., McGuinness, D., Nardi, D., and Patel-Schneider, P. F., Eds. 2003. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, Cambridge, U.K. Google ScholarDigital Library
- Berger, R. 1966. The undecidability of the dominoe problem. Mem. Amer. Math. Soc. 66, 1--72.Google Scholar
- Blackburn, P., de Rijke, M., and Venema, Y. 2001. Modal Logic. Cambridge Tracts in Theoretical Computer Science, vol. 53. Cambridge University Press, Cambridge, U.K. Google ScholarDigital Library
- Bonatti, P. A. 2004. On the decidability of containment of recursive datalog queries—preliminary report. In Proceedings of the 23rd ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS 2004). 297--306. Google ScholarDigital Library
- Borgida, A. and Brachman, R. J. 2003. Conceptual modeling with description logics. See [Baader et al. 2003], Chapter 10, 349--372. Google ScholarDigital Library
- Calvanese, D. and De Giacomo, G. 2003. Expressive description logics. See [Baader et al. 2003], Chapter 5, 178--218. Google ScholarDigital Library
- Calvanese, D., De Giacomo, G., and Lenzerini, M. 1995. Structured objects: Modeling and reasoning. In Proceedings of the 4th International Conference on Deductive and Object-Oriented Databases (DOOD'95). Lecture Notes in Computer Science, vol. 1013. Springer, Berlin, Germany, 229--246. Google ScholarDigital Library
- Calvanese, D., De Giacomo, G., and Lenzerini, M. 1998a. On the decidability of query containment under constraints. In Proceedings of the 17th ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS'98). 149--158. Google ScholarDigital Library
- Calvanese, D., De Giacomo, G., and Lenzerini, M. 2001a. Identification constraints and functional dependencies in description logics. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001). 155--160. Google ScholarDigital Library
- Calvanese, D., De Giacomo, G., Lenzerini, M., and Nardi, D. 2001b. Reasoning in expressive description logics. In Handbook of Automated Reasoning, A. Robinson and A. Voronkov, Eds. Vol. II. Elsevier Science Publishers, Amsterdam, The Netherlands, Chapter 23, 1581--1634. Google ScholarDigital Library
- Calvanese, D., De Giacomo, G., Lenzerini, M., Nardi, D., and Rosati, R. 1998b. Description logic framework for information integration. In Proceedings of the 6th International Conference on the Principles of Knowledge Representation and Reasoning (KR'98). 2--13.Google Scholar
- Calvanese, D., De Giacomo, G., Lenzerini, M., and Vardi, M. Y. 2000. Containment of conjunctive regular path queries with inverse. In Proceedings of the 7th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2000). 176--185.Google Scholar
- Calvanese, D., De Giacomo, G., Lenzerini, M., and Vardi, M. Y. 2002. View-based query answering and query containment over semistructured data. In Revised Papers of the 8th International Workshop on Database Programming Languages (DBPL 2001), G. Ghelli and G. Grahne, Eds. Lecture Notes in Computer Science, vol. 2397. Springer, Berlin, Germany, 40--61. Google ScholarDigital Library
- Calvanese, D., De Giacomo, G., and Vardi, M. Y. 2003. Decidable containment of recursive queries. In Proceedings of the 9th International Conference on Database Theory (ICDT 2003). Lecture Notes in Computer Science, vol. 2572. Springer, Berlin, Germany, 330--345. Google ScholarDigital Library
- Calvanese, D., Lenzerini, M., and Nardi, D. 1999. Unifying class-based representation formalisms. J. Artific. Intell. Res. 11, 199--240.Google ScholarDigital Library
- Calvanese, D. and Rosati, R. 2003. Answering recursive queries under keys and foreign keys is undecidable. In Proceedings of the 10th International Workshop on Knowledge Representation meets Databases (KRDB 2003). CEUR Electronic Workshop Proceedings. Available online at http://ceur-ws.org/Vol-79/.Google Scholar
- Catarci, T. and Lenzerini, M. 1993. Representing and using interschema knowledge in cooperative information systems. J. Intell. Coop. Informat. Syst. 2, 4, 375--398.Google ScholarCross Ref
- Chan, E. P. F. 1992. Containment and minimization of positive conjunctive queries in OODB's. In Proceedings of the 11th ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS'92). 202--211. Google ScholarDigital Library
- Chandra, A. K. and Merlin, P. M. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th ACM Symposium on Theory of Computing (STOC'77). 77--90. Google ScholarDigital Library
- Chandra, A. K. and Vardi, M. Y. 1985. The implication problem for functional and inclusion dependencies is undecidable. SIAM J. Comput. 14, 3, 671--677.Google ScholarDigital Library
- Chaudhuri, S. and Vardi, M. Y. 1992. On the equivalence of recursive and nonrecursive Datalog programs. In Proceedings of the 11th ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS'92). 55--66. Google ScholarDigital Library
- Chekuri, C. and Rajaraman, A. 1997. Conjunctive query containment revisited. In Proceedings of the 6th International Conference on Database Theory (ICDT'97). 56--70. Google ScholarDigital Library
- De Giacomo, G. and Lenzerini, M. 1994. Boosting the correspondence between description logics and propositional dynamic logics. In Proceedings of the 12th National Conference on Artificial Intelligence (AAAI'94). 205--212. Google ScholarDigital Library
- De Giacomo, G. and Lenzerini, M. 1995. What's in an aggregate: Foundations for description logics with tuples and sets. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI'95). 801--807. Google ScholarDigital Library
- De Giacomo, G. and Lenzerini, M. 1996. TBox and ABox reasoning in expressive description logics. In Proceedings of the 5th International Conference on the Principles of Knowledge Representation and Reasoning (KR'96). 316--327.Google Scholar
- Dong, G. and Su, J. 1996. Conjunctive query containment with respect to views and constraints. Informat. Process. Lett. 57, 2, 95--102. Google ScholarDigital Library
- Donini, F. M., Lenzerini, M., Nardi, D., and Schaerf, A. 1998. AL-log: Integrating Datalog and description logics. J. Intell. Informat. Syst. 10, 3, 227--252. Google ScholarDigital Library
- Enderton, H. B. 1972. A Mathematical Introduction to Logic. Academic Press, New York, NY.Google Scholar
- Fattorosi-Barnaba, M. and De Caro, F. 1985. Graded modalities I. Studia Logica 44, 197--221.Google ScholarCross Ref
- Fischer, M. J. and Ladner, R. E. 1979. Propositional dynamic logic of regular programs. J. Comput. Syst. Sci. 18, 194--211.Google ScholarCross Ref
- Gruber, T. R. 1993. Towards principles for the design of ontologies used for knowledge sharing. In Formal Ontology in Conceptual Analysis and Knowledge Representation, N. Guarino and R. Poli, Eds. Kluwer Academic Publishers, Dordrecht, The Netherlands.Google Scholar
- Gupta, A. and Mumick, I. S. 1995. Maintenance of materialized views: Problems, techniques, and applications. Bull. IEEE Comput. Soc. Tech. Comm. Data Eng. 18, 2, 3--18.Google Scholar
- Gupta, A., Sagiv, Y., Ullman, J. D., and Widom, J. 1994. Constraint checking with partial information. In Proceedings of the 13th ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS'94). Google ScholarDigital Library
- Halevy, A. Y. 2001. Answering queries using views: A survey. Very Large Database J. 10, 4, 270--294. Google ScholarDigital Library
- Harel, D. 1985. Recurring dominoes: Making the highly undecidable highly understandable. Ann. Discr. Math. 24, 51--72. Google ScholarDigital Library
- Horrocks, I., Sattler, U., Tessaris, S., and Tobies, S. 2000. How to decide query containment under constraints using a description logic. In Proceedings of the 7th International Conference on Logic for Programming and Automated Reasoning (LPAR 2000). Lecture Notes in Computer Science, vol. 1955. Springer, Berlin, Germany, 326--343.Google ScholarCross Ref
- Hull, R. 1997. Managing semantic heterogeneity in databases: A theoretical perspective. In Proceedings of the 16th ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS'97). 51--61. Google ScholarDigital Library
- Ioannidis, Y. E. and Ramakrishnan, R. 1995. Containment of conjunctive queries: Beyond relations as sets. ACM Trans. Database Syst. 20, 3, 288--324. Google ScholarDigital Library
- Johnson, D. S. and Klug, A. C. 1984. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28, 1, 167--189.Google ScholarCross Ref
- Klug, A. C. 1988. On conjunctive queries containing inequalities. J. ACM 35, 1, 146--160. Google ScholarDigital Library
- Kozen, D. and Tiuryn, J. 1990. Logics of programs. In Handbook of Theoretical Computer Science—Formal Models and Semantics, J. van Leeuwen, Ed. Elsevier Science Publishers, Amsterdam, The Netherlands, 789--840. Google ScholarDigital Library
- Lenzerini, M. 2002. Data integration: A theoretical perspective. In Proceedings of the 21st ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS 2002). 233--246. Google ScholarDigital Library
- Levy, A. Y. and Rousset, M.-C. 1996. CARIN: A representation language combining Horn rules and description logics. In Proceedings of the 12th Eurpoean Conference on Artificial Intelligence (ECAI'96). 323--327.Google Scholar
- Levy, A. Y., Srivastava, D., and Kirk, T. 1995. Data model and query evaluation in global information systems. J. Intell. Informat. Syst. 5, 121--143. Google ScholarDigital Library
- Levy, A. Y. and Suciu, D. 1997. Deciding containment for queries with complex objects. In Proceedings of the 16th ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems (PODS'97). 20--31. Google ScholarDigital Library
- Mitchell, J. C. 1983. The implication problem for functional and inclusion dependencies. Informat. Contr. 56, 154--173. Google ScholarDigital Library
- Neven, F. and Schwentick, T. 2003. XPath containment in the presence of disjunction, DTDs, and variables. In Proceedings of the 9th International Conference on Database Theory (ICDT 2003). 315--329. Google ScholarDigital Library
- Patel-Schneider, P., Hayes, P., and Horrocks, I. 2004. OWL Web Ontology Language semantics and abstract syntax. W3C Recommendation. Available online at http://www.w3.org/TR/owl-semantics/.Google Scholar
- Sagiv, Y. and Yannakakis, M. 1980. Equivalences among relational expressions with the union and difference operators. J. ACM 27, 4, 633--655. Google ScholarDigital Library
- Schild, K. 1991. A correspondence theory for terminological logics: Preliminary report. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI'91). 466--471.Google ScholarDigital Library
- Ullman, J. D. 1997. Information integration using logical views. In Proceedings of the 6th International Conference on Database Theory (ICDT'97). Lecture Notes in Computer Science, vol. 1186. Springer, Berlin, Germany, 19--40. Google ScholarDigital Library
- van der Meyden, R. 1998. Logical approaches to incomplete information. In Logics for Databases and Information Systems, J. Chomicki and G. Saake, Eds. Kluwer Academic Publishers, Dordrecht, The Netherlands, 307--356. Google ScholarDigital Library
- van Emde Boas, P. 1997. The convenience of tilings. In Complexity, Logic, and Recursion Theory, A. Sorbi, Ed. Lecture Notes in Pure and Applied Mathematics, vol. 187. Marcel Dekker Inc., New York, NY, 331--363.Google Scholar
- Widom, J. Ed. 1995. Special issue on materialized views and data warehousing. Bull. IEEE Comput. Soc. Tech. Comm. Data Eng. 18, 2.Google Scholar
- Wood, P. T. 2003. Containment for XPath fragments under DTD constraints. In Proceedings of the 9th International Conference on Database Theory (ICDT 2003). 300--314. Google ScholarDigital Library
Index Terms
- Conjunctive query containment and answering under description logic constraints
Recommendations
View-based query answering in Description Logics: Semantics and complexity
View-based query answering is the problem of answering a query based only on the precomputed answers to a set of views. While this problem has been widely investigated in databases, it is largely unexplored in the context of Description Logic ...
Query containment under bag and bag-set semantics
Conjunctive queries (CQs) are at the core of query languages encountered in many logic-based research fields such as AI, or database systems. The majority of existing work assumes set semantics but often in real applications the manipulation of ...
Conjunctive query answering in the description logic SH using knots
Answering conjunctive queries (CQs) has been recognized as an important task for the widening use of Description Logics (DLs) in a number of applications. The problem has been studied by many authors, who developed a number of different techniques for ...
Comments