More Web Proxy on the site http://driver.im/

research-article

The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries

Authors:

Meghyn Bienvenu,

Stanislav Kikot,

Roman Kontchakov,

Vladimir V. Podolskii,

Vladislav Ryzhikov,

Michael ZakharyaschevAuthors Info & Claims

PODS '17: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Pages 201 - 216

https://doi.org/10.1145/3034786.3034791

Published: 09 May 2017 Publication History

Abstract

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 bounded depth ontologies have nonrecursive datalog (NDL) rewritings that can be constructed and evaluated in LOGCFL for combined complexity, and even in NL if their CQs are tree-shaped with a bounded number of leaves. Thus, such OMQs incur no overhead in complexity-theoretic terms. For OMQs with arbitrary ontologies and bounded-leaf tree-shaped CQs, NDL-rewritings are constructed and evaluated in LOGCFL. We experimentally demonstrate feasibility and scalability of our rewritings compared to previously proposed NDL-rewritings. On the negative side, we prove that answering OMQs with tree-shaped CQs is not fixed-parameter tractable if the ontology depth or the number of leaves in the CQs is regarded as the parameter, and that answering OMQs with a fixed ontology (of infinite depth) is NP-complete for tree-shaped CQs and LOGCFL-complete for bounded-leaf CQs.

References

[1]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.

Digital Library

[2]

M. Arenas, P. Barceló, L. Libkin, and F. Murlak. Foundations of Data Exchange. Cambridge University Press, 2014.

Digital Library

[3]

F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2003.

Digital Library

[4]

M. Bienvenu, S. Kikot, R. Kontchakov, V. Podolskii, V. Ryzhikov, and M. Zakharyaschev. The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries. CoRR, 2017.

Digital Library

[5]

M. Bienvenu, S. Kikot, and V. V. Podolskii. Tree-like queries in OWL 2 QL: succinctness and complexity results. In Proc. of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, pages 317--328. IEEE Computer Society, 2015.

Digital Library

[6]

M. Bienvenu, M. Ortiz, M. Simkus, and G. Xiao. Tractable queries for lightweight description logics. In Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence, IJCAI 2013, pages 768--774. IJCAI/AAAI, 2013.

Digital Library

[7]

D. Bursztyn, F. Goasdoué, and I. Manolescu. Teaching an RDBMS about ontological constraints. PVLDB, 9(12):1161--1172, 2016.

Digital Library

[8]

M. Calautti, G. Gottlob, and A. Pieris. Chase termination for guarded existential rules. In Proc. of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, pages 91--103, 2015.

Digital Library

[9]

A. Calí, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under expressive relational constraints. Journal of Artificial Intelligence Research (JAIR), 48:115--174, 2013.

Digital Library

[10]

A. Calí, G. Gottlob, and T. Lukasiewicz. A general datalog-based framework for tractable query answering over ontologies. Journal of Web Semantics, 14:57--83, 2012.

Digital Library

[11]

A. Calí, G. Gottlob, and A. Pieris. Towards more expressive ontology languages: The query answering problem. Artificial Intelligence, 193:87--128, 2012.

Digital Library

[12]

D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, M. Rodriguez-Muro, R. Rosati, M. Ruzzi, and D. F. Savo. The MASTRO system for ontology-based data access. Semantic Web, 2(1):43--53, 2011.

Digital Library

[13]

D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: thetextitDL-Lite family. Journal of Automated Reasoning, 39(3):385--429, 2007.

Digital Library

[14]

C. Chekuri and A. Rajaraman. Conjunctive query containment revisited. Theoretical Computer Science, 239(2):211--229, 2000.

Digital Library

[15]

A. Chortaras, D. Trivela, and G. Stamou. Optimized query rewriting for OWL 2 QL. In Proc. of CADE-23, volume 6803 of LNCS, pages 192--206. Springer, 2011.

Digital Library

[16]

S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the ACM, 18(1):4--18, 1971.

Digital Library

[17]

B. Cuenca Grau, I. Horrocks, M. Krötzsch, C. Kupke, D. Magka, B. Motik, and Z. Wang. Acyclicity notions for existential rules and their application to query answering in ontologies. Journal of Artificial Intelligence Research (JAIR), 47:741--808, 2013.

Digital Library

[18]

E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374--425, 2001.

Digital Library

[19]

F. Di Pinto, D. Lembo, M. Lenzerini, R. Mancini, A. Poggi, R. Rosati, M. Ruzzi, and D. F. Savo. Optimizing query rewriting in ontology-based data access. In Proc. of the 16th Int. Conf. on Extending Database Technology, EDBT 2013, pages 561--572. ACM, 2013.

Digital Library

[20]

A. Doan, A. Y. Halevy, and Z. G. Ives. Principles of Data Integration. Morgan Kaufmann, 2012.

Digital Library

[21]

T. Eiter, M. Ortiz, M.vSimkus, T.-K. Tran, and G. Xiao. Query rewriting for Horn-SHIQ plus rules. In Proc. of the 26th AAAI Conf. on Artificial Intelligence, AAAI 2012, pages 726--733. AAAI, 2012.

Digital Library

[22]

M. R. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53--61, 2009.

Digital Library

[23]

J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006.

Digital Library

[24]

M. Giese, A. Soylu, G. Vega-Gorgojo, A. Waaler, P. Haase, E. Jiménez-Ruiz, D. Lanti, M. Rezk, G. Xiao, Ö. Özçep, and R. Rosati. Optique: Zooming in on big data. IEEE Computer, 48(3):60--67, 2015.

Digital Library

[25]

T. Gogacz and J. Marcinkowski. All-instances termination of chase is undecidable. In Proc. of the 41st Int. Colloquium on Automata, Languages, and Programming, ICALP 2014, Part II, volume 8573 of Lecture Notes in Computer Science, pages 293--304. Springer, 2014.

[26]

G. Gottlob, S. Kikot, R. Kontchakov, V. V. Podolskii, T. Schwentick, and M. Zakharyaschev. The price of query rewriting in ontology-based data access. Artificial Intelligence, 213:42--59, 2014.

Digital Library

[27]

G. Gottlob, N. Leone, and F. Scarcello. Computing LOGCFL certificates. In Proc. of the 26th Int. Colloquium on Automata, Languages and Programming, ICALP-99, volume 1644 of Lecture Notes in Computer Science, pages 361--371. Springer, 1999.

Digital Library

[28]

G. Gottlob, G. Orsi, and A. Pieris. Ontological queries: Rewriting and optimization. In Proc. of ICDE 2011, pages 2--13. IEEE Computer Society, 2011.

Digital Library

[29]

G. Gottlob, G. Orsi, and A. Pieris. Query rewriting and optimization for ontological databases. ACM Transactions on Database Systems (TODS), 39(3):25, 2014.

Digital Library

[30]

S. A. Greibach. The hardest context-free language. SIAM J. Comput., 2(4):304--310, 1973.

Digital Library

[31]

D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the Institute of Radio Engineers, 40(9):1098--1101, 1952.

[32]

E. Jiménez-Ruiz, E. Kharlamov, D. Zheleznyakov, I. Horrocks, C. Pinkel, M. G. Skjæveland, E. Thorstensen, and J. Mora. BootOX: Bootstrapping OWL 2 ontologies and R2RML mappings from relational databases. In Proc. of the ISWC 2015 Posters & Demonstrations Track at the 14th Int. Semantic Web Conf., volume 1486 of CEUR Workshop Proceedings. CEUR-WS, 2015.

[33]

M. Kaminski, Y. Nenov, and B. Cuenca Grau. Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies. Artificial Intelligence, 236:90--118, 2016.

Digital Library

[34]

E. Kharlamov, D. Hovland, E. Jiménez-Ruiz, D. Lanti, H. Lie, C. Pinkel, M. Rezk, M. G. Skjæveland, E. Thorstensen, G. Xiao, D. Zheleznyakov, and I. Horrocks. Ontology based access to exploration data at Statoil. In Proc. of the 14th Int. Semantic Web Conf., ISWC 2015, Part II, volume 9367 of Lecture Notes in Computer Science, pages 93--112. Springer, 2015.

Digital Library

[35]

S. Kikot, R. Kontchakov, V. Podolskii, and M. Zakharyaschev. On the succinctness of query rewriting over shallow ontologies. In Proc. of the Joint Meeting of the 23rd EACSL Annual Conf. on Computer Science Logic (CSL 2014) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2014), pages 57:1--57:10. ACM, 2014.

Digital Library

[36]

S. Kikot, R. Kontchakov, V. V. Podolskii, and M. Zakharyaschev. Exponential lower bounds and separation for query rewriting. In Proc. of the 39th Int. Colloquium on Automata, Languages and Programming, ICALP 2012, volume 7392 of Lecture Notes in Computer Science, pages 263--274. Springer, 2012.

Digital Library

[37]

S. Kikot, R. Kontchakov, and M. Zakharyaschev. On (in)tractability of OBDA with OWL 2 QL. In Proc. of the 24th Int. Workshop on Description Logics, DL 2011, volume 745, pages 224--234. CEUR-WS, 2011.

[38]

S. Kikot, R. Kontchakov, and M. Zakharyaschev. Conjunctive query answering with OWL 2 QL. In Proc. of the 13th Int. Conf. on Principles of Knowledge Representation and Reasoning, KR 2012, pages 275--285. AAAI, 2012.

Digital Library

[39]

C. Koch. Processing queries on tree-structured data efficiently. In Proc. of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2006, pages 213--224. ACM, 2006.

Digital Library

[40]

M. König, M. Leclère, M.-L. Mugnier, and M. Thomazo. Sound, complete and minimal UCQ-rewriting for existential rules. Semantic Web, 6(5):451--475, 2015.

[41]

R. Kontchakov, C. Lutz, D. Toman, F. Wolter, and M. Zakharyaschev. The combined approach to query answering in DL-Lite. In Proc. of the 12th Int. Conf. on Principles of Knowledge Representation and Reasoning, KR 2010, pages 247--257. AAAI Press, 2010.

Digital Library

[42]

R. Kontchakov, M. Rezk, M. Rodriguez-Muro, G. Xiao, and M. Zakharyaschev. Answering SPARQL queries over databases under OWL 2 QL entailment regime. In Proc. of the 13th Int. Semantic Web Conf., ISWC 2014, Part I, volume 8796 of Lecture Notes in Computer Science, pages 552--567. Springer, 2014.

Digital Library

[43]

M. Lenzerini. Ontology-based data management. ACM SIGMOD Blog, May 2013.

[44]

J. Mora, R. Rosati, and Ó. Corcho. Kyrie2: query rewriting under extensional constraints in ELHIO. In Proc. of the 13th Int. Semantic Web Conf., ISWC 2014, volume 8796 of Lecture Notes in Computer Science, pages 568--583. Springer, 2014.

Digital Library

[45]

B. Motik, B. Cuenca Grau, I. Horrocks, Z. Wu, A. Fokoue, and C. Lutz. OWL 2 Web Ontology Language Profiles. W3C Recommendation, 2012. Available at http://www.w3.org/TR/owl2-profiles.

[46]

Y. Nenov, R. Piro, B. Motik, I. Horrocks, Z. Wu, and J. Banerjee. RDFox: A highly-scalable RDF store. In Proc. of the 14th Int. Semantic Web Conf., ISWC 2015, Part II, volume 9367 of Lecture Notes in Computer Science, pages 3--20. Springer, 2015.

Digital Library

[47]

H. Pérez-Urbina, B. Motik, and I. Horrocks. A comparison of query rewriting techniques for DL-Lite. In Proc. of the 22nd Int. Workshop on Description Logics, DL 2009, volume 477 of CEUR Workshop Proceedings. CEUR-WS, 2009.

[48]

H. Pérez-Urbina, E. Rodríguez-Díaz, M. Grove, G. Konstantinidis, and E. Sirin. Evaluation of query rewriting approaches for OWL 2. In Proc. of SSWS

[49]

HPCSW 2012, volume 943 of CEUR Workshop Proceedings. CEUR-WS, 2012.

[50]

F. Picalausa and S. Vansummeren. What are real SPARQL queries like? In Proc. of the Int. Workshop on Semantic Web Information Management (SWIM). ACM, 2011.

Digital Library

[51]

A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati. Linking data to ontologies. Journal on Data Semantics, X:133--173, 2008.

Digital Library

[52]

M. Rodriguez-Muro, R. Kontchakov, and M. Zakharyaschev. Ontology-based data access: Ontop of databases. In Proc. of the 12th Int. Semantic Web Conf., ISWC 2013, Part I, volume 8218 of Lecture Notes in Computer Science, pages 558--573. Springer, 2013.

Digital Library

[53]

M. Rodriguez-Muro, R. Kontchakov, and M. Zakharyaschev. Query rewriting and optimisation with database dependencies in Ontop. In Informal Proc. of the 26th Int. Workshop on Description Logics, DL 2013, volume 1014 of CEUR Workshop Proceedings, pages 917--929. CEUR-WS, 2013.

[54]

R. Rosati. Prexto: Query rewriting under extensional constraints in DL-Lite. In Proc. of the 9th Extended Semantic Web Conf., ESWC 2012, volume 7295 of Lecture Notes in Computer Science, pages 360--374. Springer, 2012.

Digital Library

[55]

R. Rosati and A. Almatelli. Improving query answering over DL-Lite ontologies. In Proc. of the 12th Int. Conf. on Principles of Knowledge Representation and Reasoning, KR 2010, pages 290--300. AAAI Press, 2010.

Digital Library

[56]

J. F. Sequeda, M. Arenas, and D. P. Miranker. OBDA: query rewriting or materialization? In practice, both! In Proc. of the 13th Int. Semantic Web Conf., ISWC 2014, Part I, volume 8796 of Lecture Notes in Computer Science, pages 535--551. Springer, 2014.

Digital Library

[57]

A. Soylu, M. Giese, E. Jimenez-Ruiz, G. Vega-Gorgojo, and I. Horrocks. Experiencing optiquevqs: A multi-paradigm and ontology-based visual query system for end users. Universal Access in the Information Society, 15(1):129--152, 2016.

Digital Library

[58]

I. H. Sudborough. A note on tape-bounded complexity classes and linear context-free languages. Journal of the ACM, 22(4):499--500, Oct. 1975.

Digital Library

[59]

I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the ACM, 25(3):405--414, 1978.

Digital Library

[60]

M. Thomazo. Compact rewritings for existential rules. In Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence, IJCAI 2013, pages 1125--1131. IJCAI/AAAI, 2013.

Digital Library

[61]

T. Venetis, G. Stoilos, and V. Vassalos. Rewriting minimisations for efficient ontology-based query answering. In Proc. of the 28th Int. Conf. on Tools with Artificial Intelligence, ICTAI 2016, pages 1095--1102. IEEE, 2016.

[62]

H. Venkateswaran. Properties that characterize LOGCFL. Journal of Computer and System Sciences, 43(2):380--404, 1991.

Digital Library

[63]

M. Yannakakis. Algorithms for acyclic database schemes. In Proc. of the 7th Int. Conf. on Very Large Data Bases, VLDB'81, pages 82--94. IEEE Computer Society, 1981.

Digital Library

Cited By

Wang ZXiao PWang KZhuang ZWan H(2021)Efficient Datalog Rewriting for Query Answering in TGD OntologiesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.3111011(1-1)Online publication date: 2021
https://doi.org/10.1109/TKDE.2021.3111011
Ryzhikov VWałęga PZakharyaschev M(2020)Temporal Ontology-Mediated Queries and First-Order Rewritability: A Short CourseReasoning Web. Declarative Artificial Intelligence10.1007/978-3-030-60067-9_5(109-148)Online publication date: 24-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-60067-9_5
Barceló PFeier CLutz CPieris ABouyer P(2019)When is ontology-mediated querying efficient?Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470205(1-13)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470205
Show More Cited By

Index Terms

The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries

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 ...
Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
Invited Articles Issue, SIGMOD 2013, PODS 2013 and ICDT 2013

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '17: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

May 2017

458 pages

ISBN:9781450341981

DOI:10.1145/3034786

Conference Chair:
Emanuel Sallinger
University of Oxford, United Kingdom
,
General Chair:
Jan Van den Bussche
Hasselt University, Belgium
,
Program Chair:
Floris Geerts
University of Antwerp, Belgium

Copyright © 2017 ACM.

© 2017 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 May 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SIGMOD/PODS'17

Sponsor:

SIGMOD

SIGMOD/PODS'17: International Conference on Management of Data

May 14 - 19, 2017

Illinois, Chicago, USA

Acceptance Rates

PODS '17 Paper Acceptance Rate 29 of 101 submissions, 29%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
208
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)4

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang ZXiao PWang KZhuang ZWan H(2021)Efficient Datalog Rewriting for Query Answering in TGD OntologiesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.3111011(1-1)Online publication date: 2021
https://doi.org/10.1109/TKDE.2021.3111011
Ryzhikov VWałęga PZakharyaschev M(2020)Temporal Ontology-Mediated Queries and First-Order Rewritability: A Short CourseReasoning Web. Declarative Artificial Intelligence10.1007/978-3-030-60067-9_5(109-148)Online publication date: 24-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-60067-9_5
Barceló PFeier CLutz CPieris ABouyer P(2019)When is ontology-mediated querying efficient?Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470205(1-13)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470205
Barcelo PFeier CLutz CPieris A(2019)When is Ontology-Mediated Querying Efficient?2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS.2019.8785823(1-13)Online publication date: Jun-2019
https://doi.org/10.1109/LICS.2019.8785823
Bienvenu MKikot SKontchakov RPodolskii VZakharyaschev M(2018)Ontology-Mediated QueriesJournal of the ACM10.1145/319183265:5(1-51)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/3191832
David JEuzenat JGenevès PLayaïda NChampin PGandon FMédini LLalmas MIpeirotis P(2018)Evaluation of Query Transformations without DataCompanion Proceedings of the The Web Conference 201810.1145/3184558.3191617(1599-1602)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3184558.3191617
Kikot SKontchakov RRapisarda SZakharyaschev M(2018)STypeS: Nonrecursive Datalog Rewriter for Linear TGDs and Conjunctive QueriesOn the Move to Meaningful Internet Systems. OTM 2018 Conferences10.1007/978-3-030-02671-4_27(441-460)Online publication date: 22-Oct-2018
https://dl.acm.org/doi/10.1007/978-3-030-02671-4_27

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents