Query Rewriting and Optimization for Ontological Databases

Abstract

Ontological queries are evaluated against a knowledge base consisting of an extensional database and an ontology (i.e., a set of logical assertions and constraints that derive new intensional knowledge from the extensional database), rather than directly on the extensional database. The evaluation and optimization of such queries is an intriguing new problem for database research. In this article, we discuss two important aspects of this problem: query rewriting and query optimization. Query rewriting consists of the compilation of an ontological query into an equivalent first-order query against the underlying extensional database. We present a novel query rewriting algorithm for rather general types of ontological constraints that is well suited for practical implementations. In particular, we show how a conjunctive query against a knowledge base, expressed using linear and sticky existential rules, that is, members of the recently introduced Datalog± family of ontology languages, can be compiled into a union of conjunctive queries (UCQ) against the underlying database. Ontological query optimization, in this context, attempts to improve this rewriting process soas to produce possibly small and cost-effective UCQ rewritings for an input query.

References

1. Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley.
2. Andrea Acciarri, Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Mattia Palmieri, and Riccardo Rosati. 2005. QuOnto: Querying ontologies. In Proceedings of the 20^th National Conference on Artificial Intelligence and the 17^th Innovative Applications of Artificial Intelligence Conference. 1670--1671.
3. Miklos Ajtai and Yuri Gurevich. 1989. Datalog vs. first-order logic. In Proceedings of the 30^th Annual Symposium on Foundations of Computer Science. 142--147.
4. Hajnal Andreka, Johan van Benthem, and Istvan Nemeti. 1998. Modal languages and bounded fragments of predicate logic. J. Philos. Logic 27, 217--274.
5. Franz Baader. 2003. Least common subsumers and most specific concepts in a description logic with existential restrictions and terminological cycles. In Proceedings of the 18^th International Joint Conference on Artificial Intelligence. 319--324.
6. Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, Eds. 2003. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press.
7. Jean-Francois Baget, Michel Leclere, Marie-Laure Mugnier, and Eric Salvat. 2011. On rules with existential variables: Walking the decidability line. Artif. Intell. 175, 9--10, 1620--1654.
8. Catriel Beeri and Moshe Y. Vardi. 1981. The implication problem for data dependencies. In Proceedings of the 8^th International Colloquium on Automata, Languages and Programming. 73--85.
9. Michael Benedikt, Balder Ten Cate, and Efthymia Tsamoura. 2014. Generating low-cost plans from proofs. In Proceedings of the 33^rd ACM Symposium on Principles of Database Systems. 200--211.
10. Barry Bishop and Florian Fischer. 2008. IRIS - Integrated rule inference system. In Proceedings of the International Workshop on Advancing Reasoning on the Web: Scalability and Commonsense.
11. Philip Bohannon, Eiman Elnahrawy, Wenfei Fan, and Michael Flaster. 2006. Putting context into schema matching. In Proceedings of the 32^nd International Conference on Very Large Data Bases. 307--318.
12. Loreto Bravo, Wenfei Fan, and Shuai Ma. 2007. Extending dependencies with conditions. In Proceedings of the 33^rd International Conference on Very Large Data Bases. 243--254.
13. Andrea Cali, Domenico Lembo, and Riccardo Rosati. 2003. Decidability and complexity of query answering over incosistent and incomplete databases. In Proceedings of the 22^nd ACM Symposium on Principles of Database Systems. 260--271.
14. Andrea Cali, Georg Gottlob, and Michael Kifer. 2008. Taming the infinite chase: Query answering under expressive relational constraints. In Proceedings of the 11^th International Conference on Principles of Knowledge Representation and Reasoning. 70--80.
15. Andrea Cali, Georg Gottlob, Thomas Lukasiewicz, and Andreas Pieris. 2011. A logical toolbox for ontological reasoning. SIGMOD Rec. 40, 3, 5--14.
16. Andrea Cali, Georg Gottlob, and Thomas Lukasiewicz. 2012a. A general Datalog-based framework for tractable query answering over ontologies. J. Web Semant. 14, 57--83.
17. Andrea Cali, Georg Gottlob, and Andreas Pieris. 2012b. Towards more expressive ontology languages: The query answering problem. Artif. Intell. 193, 87--128.
18. Andrea Cali, Georg Gottlob, and Michael Kifer. 2013. Taming the infinite chase: Query answering under expressive relational constraints. J. Artif. Intell. Res. 48, 115--174.
19. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. 2007. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reason. 39, 3, 385--429.
20. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. 2013a. Data complexity of query answering in description logics. Artif. Intell. 195, 335--360.
21. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. 2013b. Data complexity of query answering in description logics. Artif. Intell. 195, 335--360.
22. Ashok K. Chandra and Philip M. Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9^th Annual ACM Symposium on Theory of Computing. 77--90.
23. Ashok K. Chandra and Moshe Y. Vardi. 1985. The implication problem for functional and inclusion dependencies. SIAM J. Comput. 14, 671--677.
24. Chandra Chekuri and Anand Rajaraman. 2000. Conjunctive query containment revisited. Theor. Comput. Sci. 239, 2, 211--229.
25. Alexandros Chortaras, Despoina Trivela, and Giorgos B. Stamou. 2011. Optimized query rewriting for owl 2 ql. In Proceedings of the 23^rd International Conference on Automated Deduction. 192--206.
26. Carlo Curino, Hyun Jin Moon, Alin Deutsch, and Carlo Zaniolo. 2013. Automating the database schema evolution process. VLDB J. 22, 1, 73--98.
27. Alin Deutsch, Alan Nash, and Jeff B. Remmel. 2008. The chase revisisted. In Proceedings of the 27^th ACM Symposium on Principles of Database Systems. 149--158.
28. Alin Deutsch, Lucian Popa, and Val Tannen. 1999. Physical data independence, constraints, and optimization with universal plans. In Proceedings of the 25^th International Conference on Very Large Data Bases. 459--470.
29. Alin Deutsch and Val Tannen. 2003. MARS: A system for publishing xml from mixed and redundant storage. In Proceedings of the 29^th International Conference on Very Large Data Bases. 201--212.
30. Ronald Fagin, Phokion G. Kolaitis, Renee J. Miller, and Lucian Popa. 2005. Data exchange: Semantics and query answering. Theor. Comput. Sci. 336, 1, 89--124.
31. Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, and Moshe Y. Vardi. 1993. Undecidable optimization problems for database logic programs. J. ACM 40, 3, 683--713.
32. Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, Thomas Schwentick, and Michael Zakharyaschev. 2014. The price of query rewriting in ontology-based data access. Artif. Intell. 213, 42--59.
33. Georg Gottlob, Nicola Leone, and Francesco Scarcello. 2002. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64, 3, 579--627.
34. Georg Gottlob, Giorgio Orsi, and Andreas Pieris. 2011. Ontological queries: Rewriting and optimization. In Proceedings of the 27^th International Conference on Data Engineering. 2--13.
35. Georg Gottlob and Thomas Schwentick. 2012. Rewriting ontological queries into small nonrecursive datalog programs. In Proceedings of the 13^th International Conference on Principles of Knowledge Representation and Reasoning.
36. Alon Y. Halevy. 2001. Answering queries using views: A survey. VLDB J. 10, 4, 270--294.
37. Martha Imprialou, Giorgos Stoilos, and Bernardo Cuenca Grau. 2012. Benchmarking ontology-based query rewriting systems. In Proceedings of the 26^th AAAI Conference on Artificial Intelligence. 779--785.
38. David S. Johnson and Anthony C. Klug. 1984. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28, 1, 167--189.
39. Stanislav Kikot, Roman Kontchakov, and Michael Zakharyaschev. 2012a. Conjunctive query answering with OWL 2 QL. In Proceedings of the 13^th International Conference on Principles of Knowledge Representation and Reasoning.
40. Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, and Michael Zakharyaschev. 2012b. Exponential lower bounds and separation for query rewriting. In Proceedings of the 39^th International Colloquium on Automata, Languages and Programming. 263--274.
41. Melanie Konig, Michel LeClere, Marie-Laure Mugnier, and Michael Thomazo. 2012. A sound and complete backward chaining algorithm for existential rules. In Proceedings of the 6^th International Conference on Web Reasoning and Rule Systems. 122--138.
42. Melanie Konig, Michel LeClere, Marie-Laure Mugnier, and Michael Thomazo. 2013. On the exploration of the query rewriting space with existential rules. In Proceedings of the 7^th International Conference on Web Reasoning and Rule Systems. 123--137.
43. Markus Krotzsch and Sebastian Rudolph. 2011. Extending decidable existential rules by joining acyclicity and guardedness. In Proceedings of the 22^nd International Joint Conference on Artificial Intelligence. 963--968.
44. David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv. 1979. Testing implications of data dependencies. ACM Trans. Database Syst. 4, 4, 455--469.
45. Giorgio Orsi and Andreas Pieris. 2011. Optimizing query answering under ontological constraints. Proc. VLDB Endow. 4, 11, 1004--1015.
46. Christos. H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley.
47. Hector Perez-Urbina, Boris Motik, and Ian Horrocks. 2010. Tractable query answering and rewriting under description logic constraints. J. Appl. Logic 8, 2, 186--209.
48. Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati. 2008. Linking data to ontologies. J. Data Semant. 10, 133--173.
49. Mariano Rodriguez-Muro and Diego Calvanese. 2012. Quest, an OWL 2 QL reasoner for ontology-based data access. In Proceedings of the OWL: Experiences and Directions Workshop.
50. Riccardo Rosati and Alessandro Almatelli. 2010. Improving query answering over dl-lite ontologies. In Proceedings of the 12^th International Conference on Principles of Knowledge Representation and Reasoning.
51. Sebastian Rudolph, Markus Krotzsch, and Pascal Hitzler. 2008. All elephants are bigger than all mice. In Proceedings of the 21^st International Workshop on Description Logics.
52. Balder Ten Cate and Phokion G. Kolaitis. 2009. Structural characterizations of schema-mapping languages. In Proceedings of the 12^th International Conference on Database Theory. 63--72.
53. Michael Thomazo. 2013. Compact rewritings for existential rules. In Proceedings of the 23^rd International Joint Conference on Artificial Intelligence.
54. Moshe Y. Vardi. 1995. On the complexity of bounded-variable queries. In Proceedings of the 14^th ACM Symposium on Principles of Database Systems. 266--276.
55. Tassos Venetis, Giorgos Stoilos, and Giorgos Stamou. 2013. Query extensions and incremental query rewriting for OWL 2 QL ontologies. J. Data Semant. 3, 1, 1--23.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Logic programming and answer set programming

• Information systems

  • Data management systems

    • Database design and models

      • Relational database model

    • Database management system engines

      • Database query processing

      • Triggers and rules

    • Query languages

      • Relational database query languages

• Theory of computation

  • Logic

    • Constraint and logic programming

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)

    • Machine learning theory

      • Inductive inference