research-article

Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP

Authors:

Meghyn Bienvenu,

Balder Ten Cate,

Frank WolterAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 39, Issue 4

Article No.: 33, Pages 1 - 44

https://doi.org/10.1145/2661643

Published: 30 December 2014 Publication History

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 article, 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 article are threefold. First, we show that popular ontology-mediated query languages have the same expressive power as natural fragments of disjunctive datalog, and we study the relative succinctness of ontology-mediated queries and disjunctive datalog queries. 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.

Supplementary Material

a33-bienvenu-apndx.pdf (bienvenu.zip)

Supplemental movie, appendix, image and software files for, Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP

Download
204.76 KB

References

[1]

Bogdan Alexe, Balder Ten Cate, Phokion G. Kolaitis, and Wang Chiew Tan. 2011. Characterizing schema mappings via data examples. ACM Trans. Database Syst. 36, 4.

Digital Library

[2]

Albert Atserias. 2005. On digraph coloring problems and treewidth duality. In Proceedings of the 20^th Annual IEEE Symposium on Logic in Computer Science (LICS'05). 106--115.

Digital Library

[3]

Franz Baader, Meghyn Bienvenu, Carsten Lutz, and Frank Wolter. 2010. Query and predicate emptiness in description logics. In Proceedings of the 12^th International Conference on the Principles of Knowledge Representation and Reasoning (KR'10).

[4]

Franz Baader, Sebastian Brandt, and Carsten Lutz. 2005. Pushing the E L envelope. In Proceedings of the 19^th International Joint Conference on Artificial Intelligence (IJCAI'05). 364--369.

Digital Library

[5]

Franz Baader, Deborah, Diego Calvanese, Deborah L. McGuiness, Daniele Nardi, and Peter F. Patel-Schneider, Eds. 2003. The Description Logic Handbook. Cambridge University Press.

Digital Library

[6]

Jean-Francois Baget, Marie-Laure Mugnier, Sebastian Rudolph, and Michael Thomazo. 2011. Walking the complexity lines for generalized guarded existential rules. In Proceedings of the 22^nd International Joint Conference on Artificial Intelligence (IJCAI'11).

Digital Library

[7]

Vince Bárány, Michael Benedikt, and Balder Ten Cate. 2013. Rewriting guarded negation queries. In Proceedings of the 38^th International Symposium on Mathematical Foundations of Computer Science (MFCS'13). Springer, 98--110.

[8]

Vince Barany, Georg Gottlob, and Martin Otto. 2010. Querying the guarded fragment. In Proceedings of the 25^th Annual IEEE Symposium on Logic in Computer Science (LICS'110). 1--10.

Digital Library

[9]

Vince Barany, Balder Ten Cate, and Martin Otto. 2012. Queries with guarded negation. Proc. VLDB Endow. 5, 11, 1328--1339.

Digital Library

[10]

Vince Barany, Balder Ten Cate, and Luc Segoufin. 2011. Guarded negation. In Proceedings of the 38^th International Colloquium on Automata, Languages, and Programming (ICALP'11). 356--367.

Digital Library

[11]

Libor Barto and Marcin Kozik. 2009. Constraint satisfaction problems of bounded width. In Proceedings of the 50^th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09). 595--603.

Digital Library

[12]

Meghyn Bienvenu, Carsten Lutz, and Frank Wolter. 2012. Query containment in description logics reconsidered. In Proceedings of the 13^th International Conference on the Principles of Knowledge Representation and Reasoning (KR'12).

[13]

Meghyn Bienvenu, Carsten Lutz, and Frank Wolter. 2013a. First-order rewritability of atomic queries in horn description logics. In Proceedings of the 23^rd International Joint Conference on Artificial Intelligence (IJCAI'13). 754--760.

Digital Library

[14]

Meghyn Bienvenu, Balder Ten Cate, Carsten Lutz, and Frank Wolter. 2013b. Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP. In Proceedings of the Symposium on Principles of Database Systems (PODS'13). ACM Press, New York, 213--224.

Digital Library

[15]

Manuel Bodirsky, Hubie Chen, and Tomás Feder. 2012. On the complexity of MMSNP. SIAM J. Discr. Math. 26, 1, 404--414.

Digital Library

[16]

Andrei A. Bulatov. 2009. Bounded relational width. http://www.cs.sfu.ca/&sim;abulatov/papers/relwidth.pdf.

[17]

Andrei A. Bulatov. 2011. On the CSP dichotomy conjecture. In Proceedings of the 6^th International Conference on Computer Science: Theory and Applications (CSR'11). 331--344.

Digital Library

[18]

Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. 2009. A general datalog-based framework for tractable query answering over ontologies. In Proceedings of the Symposium on Principles of Database Systems (PODS'09). 77--86.

Digital Library

[19]

Andrea Calì, Georg Gottlob, and Andreas Pieris. 2012. Towards more expressive ontology languages: The query answering problem. Artif. Intell. 193, 87--128.

Digital Library

[20]

Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. 2006. Data complexity of query answering in description logics. In Proceedings of the International Conference on the Principles of Knowledge Representation and Reasoning (KR'06). 260--270.

[21]

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.

Digital Library

[22]

Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. 1998. On the decidability of query containment under constraints. In Proceedings of the 17^th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'98). 149--158.

Digital Library

[23]

Balder Ten Cate and Luc Segoufin. 2011. Unary negation. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS'11). 344--355.

[24]

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 (CADE'11). 192--206.

Digital Library

[25]

Giuseppe De Giacomo and Maurizio Lenzerini. 1994. Boosting the correspondence between description logics and propositional dynamic logics. In Proceedings of the 12^th National Conference on Artificial Intelligence (AAAI'94). 205--212.

Digital Library

[26]

Thomas Eiter, Wolfgang Faber, Michael Fink, and Stefan Woltran. 2007. Complexity results for answer set programming with bounded predicate arities and implications. Ann. Math. Artif. Intell. 51, 2--4, 123--165.

Digital Library

[27]

Thomas Eiter, Georg Gottlob, and Heikki Mannila. 1997. Disjunctive datalog. ACM Trans. Database Syst. 22, 3, 364--418.

Digital Library

[28]

Thomas Eiter, Magdalena Ortiz, Mantas Simkus, Trung-Kien Tran, and Guohui Xiao. 2012. Query rewriting for horn-shiq plus rules. In Proceedings of the National Conference on Artificial Intelligence (AAAI'12).

[29]

Tomás Feder, Florent R. Madelaine, and Iain A. Stewart. 2004. Dichotomies for classes of homomorphism problems involving unary functions. Theor. Comput. Sci. 314, 1--2, 1--43.

Digital Library

[30]

Tomás Feder and Moshe Y. Vardi. 1998. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28, 1, 57--104.

Digital Library

[31]

Jan Foniok, Jaroslav Nesetril, and Claude Tardif. 2008. Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. Euro. J. Combinator. 29, 4, 881--899.

Digital Library

[32]

Ralph Freese, Marcin Kozik, Andrei Krokhin, Miklós Maróti, Ralph Mckenzie, and Ross Willard. 2009. On maltsev conditions associated with omitting certain types of local structures. http://www.math.hawaii.edu/&sim;ralph/Classes/619/OmittingTypesMaltsev.pdf.

[33]

Georg Gottlob, Erich Grädel, and Helmut Veith. 2002. Datalog lite: A deductive query language with linear time model checking. ACM Trans. Comput. Logics 3, 1, 42--79.

Digital Library

[34]

Georg Gottlob and Thomas Schwentick. 2012. Rewriting ontological queries into small nonrecursive datalog programs. In Proceedings of the International Conference on the Principles of Knowledge Representation and Reasoning (KR'12).

[35]

Bernardo Cuenca Grau, Boris Motik, Giorgos Stoilos, and Ian Horrocks. 2013. Computing datalog rewritings beyond horn ontologies. In Proceedings of the 23^rd International Joint Conference on Artificial Intelligence (IJCAI'13). 832--838.

Digital Library

[36]

Pavol Hell, Jaroslav Nešetřil, and X. Zhu. 1996. Duality and polynomial testing of tree homomorphisms. Trans. Amer. Math. Soc. 348, 4, 1281--1297.

[37]

André Hernich, Clemens Kupke, Thomas Lukasiewicz, and Georg Gottlob. 2013. Well-founded semantics for extended datalog and ontological reasoning. In Proceedings of the 32^nd Symposium on Principles of Database Systems (PODS'13). Richard Hull and Wenfei Fan, Eds., ACM Press, New York, 225--236.

Digital Library

[38]

Ian Horrocks and Ulrike Sattler. 1999. A description logic with transitive and inverse roles and role hierarchies. J. Logic Comput. 9, 3, 385--410.

[39]

Ullrich Hustadt, Boris Motik, and Ulrike Sattler. 2007. Reasoning in description logics by a reduction to disjunctive datalog. J. Autom. Reason. 39, 3, 351--384.

Digital Library

[40]

David S. Johnson. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Science, MIT Press, 67--161.

Digital Library

[41]

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 (KR'12).

[42]

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 of Automata, Languages, and Programming (ICALP'12). 263--274.

Digital Library

[43]

Roman Kontchakov, Carsten Lutz, David Toman, Frank Wolter, and Michael Zakharyaschev. 2010. The combined approach to query answering in DL-lite. In Proceedings of the 12^th International Conference on Principles of Knowledge Representation and Reasoning (KR'12).

[44]

Adila Krisnadhi and Carsten Lutz. 2007. Data complexity in the EL family of DLS. In Proceedings of the 14^th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR'07). 333--347.

Digital Library

[45]

Gábor Kun. 2007. Constraints, MMSNP, and expander structures. http://arxiv.org/abs/0706.1701v1.

Digital Library

[46]

Gábor Kun and Jaroslav Nesetril. 2008. Forbidden lifts (NP and CSP for combinatorialists). Euro. J. Comb. 29, 4, 930--945.

Digital Library

[47]

Benoit Larose, Cynthia Loten, and Claude Tardif. 2007. A characterisation of first-order constraint satisfaction problems. Logical Methods Comput. Sci. 3, 4.

[48]

Carsten Lutz. 2007. Inverse roles make conjunctive queries hard. In Proceedings of the International Workshop on Description Logics (DL'07).

[49]

Carsten Lutz. 2008. The complexity of conjunctive query answering in expressive description logics. In Proceedings of the 4^th International Joint Conference on Automated Reasoning (IJCAR'08). 179--193.

Digital Library

[50]

Carsten Lutz and Frank Wolter. 2012. Non-uniform data complexity of query answering in description logics. In Proceedings of the 13^th International Conference on Principles of Knowledge Representation and Reasoning (KR'12).

[51]

Florent R. Madelaine. 2009. Universal structures and the logic of forbidden patterns. Logical Methods Comput. Sci. 5, 2.

[52]

Florent R. Madelaine and Iain A. Stewart. 2007. Constraint satisfaction, logic and forbidden patterns. SIAM J. Comput. 37, 1, 132--163.

Digital Library

[53]

Boris Motik. 2006. Reasoning in description logics using resolution and deductive databases. https://www.cs.ox.ac.uk/boris.motik/pubs/motik06PhD.pdf.

[54]

Héctor Pérez-Urbina, Boris Motik, and Ian Horrocks. 2010. Tractable query answering and rewriting under description logic constraints. J. Appl. Logic 8, 2,186--209.

[55]

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.

[56]

Mariano Rodriguez-Muro and Diego Calvanese. 2012. High performance query answering over DL-lite ontologies. In Proceedings of the 13^th International Conference on Principles of Knowledge Representation and Reasoning (KR'12). 308--318.

[57]

Riccardo Rosati and Alessandro Almatelli. 2010. Improving query answering over DL-lite ontologies. In Proceedings of the 12^th International Conference on thePrinciples of Knowledge Representation and Reasoning (KR'10). 290--300.

[58]

Benjamin Rossman. 2008. Homomorphism preservation theorems. J. ACM 55, 3.

Digital Library

[59]

Sebastian Rudolph, Markus Krotzsch, and Pascal Hitzler. 2012. Type-elimination-based reasoning for the description logic shiqbs using decision diagrams and disjunctive datalog. Logical Methods Comput. Sci. 8, 1.

[60]

Frantisek Simancik. 2012. Elimination of complex RIAS without automata. In Proceedings of the 25^th International Workshop on Description Logics (DL'12).

[61]

W3C. 2009. OWL 2 web ontology language: Document overview. W3C recommendation. http://www.w3.org/TR/owl2-overview/.

Cited By

Mottet APinsker M(2024)Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structuresJournal of the ACM10.1145/368920771:5(1-47)Online publication date: 17-Aug-2024
https://dl.acm.org/doi/10.1145/3689207
Bodirsky MJonsson PMartin BMottet ASemanišinová Ž(2024)Complexity Classification Transfer for CSPs via Algebraic ProductsSIAM Journal on Computing10.1137/22M153430453:5(1293-1353)Online publication date: 12-Sep-2024
https://doi.org/10.1137/22M1534304
Lukumbuzya SOrtiz MŠimkus M(2024)Datalog rewritability and data complexity of ALCHOIQ with closed predicatesArtificial Intelligence10.1016/j.artint.2024.104099330:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104099
Show More Cited By

Index Terms

Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
1. Information systems
  1. Data management systems
    1. Query languages

Recommendations

Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP
PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

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 ...
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity

We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs) and the complexity ...
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries
PODS '17: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Our concern is the overhead of answering OWL 2 QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and, more generally, bounded treewidth conjunctive queries (CQs). We show that OMQs with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 39, Issue 4

Invited Articles Issue, SIGMOD 2013, PODS 2013 and ICDT 2013

December 2014

341 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/2691190

Editor:
Christian S. Jensen
Aalborg University, Denmark

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 December 2014

Accepted: 01 August 2014

Revised: 01 June 2014

Received: 01 October 2013

Published in TODS Volume 39, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
652
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mottet APinsker M(2024)Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structuresJournal of the ACM10.1145/368920771:5(1-47)Online publication date: 17-Aug-2024
https://dl.acm.org/doi/10.1145/3689207
Bodirsky MJonsson PMartin BMottet ASemanišinová Ž(2024)Complexity Classification Transfer for CSPs via Algebraic ProductsSIAM Journal on Computing10.1137/22M153430453:5(1293-1353)Online publication date: 12-Sep-2024
https://doi.org/10.1137/22M1534304
Lukumbuzya SOrtiz MŠimkus M(2024)Datalog rewritability and data complexity of ALCHOIQ with closed predicatesArtificial Intelligence10.1016/j.artint.2024.104099330:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104099
Leclère MMugnier MPérution-Kihli GMarquis PSon TKern-Isberner G(2023)Query rewriting with disjunctive existential rules and mappingsProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/42(429-439)Online publication date: 2-Sep-2023
https://dl.acm.org/doi/10.24963/kr.2023/42
Lutz CPrzybyłko MWilliams BChen YNeville J(2023)Efficient answer enumeration in description logics with functional rolesProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25797(6483-6490)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25797
Taglino FCumbo FAntognoli GArisi ID’Onofrio MPerazzoni FVoyat RFiscon GConte FCanevelli MBruno GMecocci PBertolazzi P(2023)An ontology-based approach for modelling and querying Alzheimer’s disease dataBMC Medical Informatics and Decision Making10.1186/s12911-023-02211-623:1Online publication date: 8-Aug-2023
https://doi.org/10.1186/s12911-023-02211-6
Ten Cate BDalmau VFunk MLutz CGeerts FNgo HSintos S(2023)Extremal Fitting Problems for Conjunctive QueriesProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588655(89-98)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3584372.3588655
Barsukov AMadelaine F(2023)On Guarded Extensions of MMSNPUnity of Logic and Computation10.1007/978-3-031-36978-0_17(202-213)Online publication date: 19-Jul-2023
https://doi.org/10.1007/978-3-031-36978-0_17
Nguyen T(2022)Toward Human Digital Twins for Cybersecurity Simulations on the Metaverse: Ontological and Network Science ApproachJMIRx Med10.2196/335023:2(e33502)Online publication date: 20-Apr-2022
https://doi.org/10.2196/33502
Mottet APinsker M(2022)Smooth approximations and CSPs over finitely bounded homogeneous structuresProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533353(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533353
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents