Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP

ABSTRACT

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled with an ontology. In this paper, we study several classes of ontology-mediated queries, where the database queries are given as some form of conjunctive query and the ontologies are formulated in description logics or other relevant fragments of first-order logic, such as the guarded fragment and the unary-negation fragment. The contributions of the paper are three-fold. First, we characterize the expressive power of ontology-mediated queries in terms of fragments of disjunctive datalog. Second, we establish intimate connections between ontology-mediated queries and constraint satisfaction problems (CSPs) and their logical generalization, MMSNP formulas. Third, we exploit these connections to obtain new results regarding (i) first-order rewritability and datalog-rewritability of ontology-mediated queries, (ii) P/NP dichotomies for ontology-mediated queries, and (iii) the query containment problem for ontology-mediated queries.

References

1. B. Alexe, B. ten Cate, P. G. Kolaitis, and W. C. Tan. Characterizing schema mappings via data examples. ACM Trans. Database Syst., 36(4), 2011.
2. A. Atserias. On digraph coloring problems and treewidth duality. In LICS, 2005.
3. F. Baader, M. Bienvenu, C. Lutz, and F. Wolter. Query and predicate emptiness in description logics. In KR, 2010.
4. F. Baader, D. Calvanese, D. L. McGuiness, D. Nardi, and P. Patel-Schneider, editors. The Description Logic Handbook. Cambridge University Press, 2003.
5. J.-F. Baget, M.-L. Mugnier, S. Rudolph, and M. Thomazo. Walking the complexity lines for generalized guarded existential rules. In IJCAI, 2011.
6. V. Bárány, G. Gottlob, and M. Otto. Querying the guarded fragment. In LICS, 2010.
7. V. Bárány, B. ten Cate, and M. Otto. Queries with guarded negation. PVLDB, 5(11), 2012.
8. V. Bárány, B. ten Cate, and L. Segoufin. Guarded negation. In ICALP, 2011.
9. L. Barto and M. Kozik. Constraint satisfaction problems of bounded width. In FOCS, 2009.
10. M. Bienvenu, C. Lutz, and F. Wolter. Query containment in description logics reconsidered. In KR, 2012.
11. P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic. Cambridge University Press, 2001.
12. M. Bodirsky, H. Chen, and T. Feder. On the complexity of MMSNP. SIAM J. Discrete Math., 26(1):404--414, 2012.
13. A. Bulatov. Bounded relational width. In preparation. %Manuscript available from http://www.cs.sfu.ca/abulatov/mpapers.html.
14. A. A. Bulatov. On the CSP dichotomy conjecture. In CSR, 2011.
15. A. Calì, G. Gottlob, and T. Lukasiewicz. A general datalog-based framework for tractable query answering over ontologies. In PODS, 2009.
16. A. Calì, G. Gottlob, and A. Pieris. Towards more expressive ontology languages: The query answering problem. Artif. Intell., 193, 2012.
17. D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Data complexity of query answering in description logics. In KR, 2006.
18. D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning, 39(3), 2007.
19. D. Calvanese, G. D. Giacomo, and M. Lenzerini. On the decidability of query containment under constraints. In PODS, 1998.
20. B. Cuenca Grau, M. Kaminski, and B. Motik Computing Datalog Rewritings Beyond Horn Ontologies. In IJCAI, 2013
21. T. Eiter, G. Gottlob, and H. Mannila. Disjunctive datalog. ACM Trans. Database Syst., 22(3), 1997.
22. T. Eiter, M. Ortiz, M. Simkus, T.-K. Tran, and G. Xiao. Towards practical query answering for Horn-SHIQ. In DL, 2012.
23. T. Feder, F. R. Madelaine, and I. A. Stewart. Dichotomies for classes of homomorphism problems involving unary functions. Theor. Comput. Sci., 314(1--2), 2004.
24. T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1), 1998.
25. J. Foniok, J. Nesetril, and C. Tardif. Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. Eur. J. Comb., 29(4), 2008.
26. R. Freese, M. Kozik, A. Krokhin, M. Maróti, R. KcKenzie, and R. Willard. On Maltsev conditions associated with omitting certain types of local structures. In preparation. http://www.math.hawaii.edu/~ralph/Classes/619/OmittingTypesMaltsev.pdf
27. G. Gottlob, E. Grädel, and H. Veith. Datalog LITE: a deductive query language with linear time model checking. ACM Trans. Comput. Log., 3(1), 2002.
28. G. Gottlob and T. Schwentick. Rewriting ontological queries into small nonrecursive datalog programs. In KR, 2012.
29. U. Hustadt, B. Motik, and U. Sattler. Reasoning in description logics by a reduction to disjunctive datalog. J. Autom. Reasoning, 39(3), 2007.
30. S. Kikot, R. Kontchakov, V. V. Podolskii, and M. Zakharyaschev. Exponential lower bounds and separation for query rewriting. In ICALP, 2012.
31. R. Kontchakov, C. Lutz, D. Toman, F. Wolter, and M. Zakharyaschev. The combined approach to query answering in DL-Lite. In KR, 2010.
32. A. Krisnadhi and C. Lutz. Data complexity in the EL family of DLs. In LPAR, 2007.
33. G. Kun. Constraints, MMSNP, and Expander Structures. http://arxiv.org/abs/0706.1701v1, 2007.
34. G. Kun and J. Nesetril. Forbidden lifts (NP and CSP for combinatorialists). Eur. J. Comb., 29(4), 2008.
35. B. Larose, C. Loten, and C. Tardif. A characterisation of first-order constraint satisfaction problems. Logical Methods in Comp. Sci., 3(4), 2007.
36. C. Lutz and F. Wolter. Non-uniform data complexity of query answering in description logics. In KR, 2012.
37. F. R. Madelaine. Universal structures and the logic of forbidden patterns. Logical Methods in Comp. Sci., 5(2), 2009.
38. F. R. Madelaine and I. A. Stewart. Constraint satisfaction, logic and forbidden patterns. SIAM J. Comput., 37(1), 2007.
39. B. Motik. Reasoning in description logics using resolution and deductive databases. PhD thesis, 2006.
40. A. Poggi, D. Lembo, D. Calvanese, G. D. Giacomo, M. Lenzerini, and R. Rosati. Linking data to ontologies. J. Data Semantics, 10, 2008.
41. V. R. Pratt. Models of program logics. In FoCS, 1979.
42. R. Rosati and A. Almatelli. Improving Query Answering over DL-Lite Ontologies. In KR, 2010.
43. B. Rossman. Homomorphism preservation theorems. J. ACM, 55(3), 2008.
44. S. Rudolph, M. Krötzsch, and P. Hitzler. Type-elimination-based reasoning for the description logic SHIQ using decision diagrams and disjunctive datalog. Logical Methods in Comp. Sci., 8(1), 2012.
45. F. Simancik. Elimination of complex RIAs without automata. In DL, 2012.
46. B. ten Cate and L. Segoufin. Unary negation. In STACS, 2011.
47. W3C OWL Working Group. OWL 2 Web Ontology Language. http://www.w3.org/TR/owl2-overview/, 2012.

Index Terms

• Computer systems organization

  • Architectures

    • Other architectures

      • Heterogeneous (hybrid) systems

• Information systems

  • Data management systems

    • Database design and models

    • Database management system engines

    • Information integration

      • Extraction, transformation and loading

    • Query languages