Article

A Practical Acyclicity Notion for Query Answering Over Horn- Ontologies

Authors:

Cristina Feier,

Pascal HitzlerAuthors Info & Claims

The Semantic Web – ISWC 2016: 15th International Semantic Web Conference, Kobe, Japan, October 17–21, 2016, Proceedings, Part I

Pages 70 - 85

https://doi.org/10.1007/978-3-319-46523-4_5

Published: 17 October 2016 Publication History

Abstract

Conjunctive query answering over expressive Horn Description Logic ontologies is a relevant and challenging problem which, in some cases, can be addressed by application of the chase algorithm. In this paper, we define a novel acyclicity notion which provides a sufficient condition for termination of the restricted chase over Horn- TBoxes. We show that this notion generalizes most of the existing acyclicity conditions (both theoretically and empirically). Furthermore, this new acyclicity notion gives rise to a very efficient reasoning procedure. We provide evidence for this by providing a materialization based reasoner for acyclic ontologies which outperforms other state-of-the-art systems.

References

[1]

Baader F, Calvanese D, McGuinness D, Nardi D, and Patel-Schneider P The Description Logic Handbook: Theory, Implementation, and Applications 2007 2 New York Cambridge University Press

[2]

Baget, J., Garreau, F., Mugnier, M., Rocher, S.: Extending acyclicity notions for existential rules. In: ECAI 2014, Frontiers in Artificial Intelligence and Applications, vol. 263, pp. 39–44. IOS Press (2014)

[3]

Calì, A., Gottlob, G., Kifer, M.: Taming the infinite chase. In: Brewka, G., Lang, J. (eds.) Proceedings of 11th International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), pp. 70–80. AAAI Press (2008)

[4]

Calvanese D, Eiter T, and Ortiz M Answering regular path queries in expressive dls via alternating tree-automata Inf. Comput. 2014 237 12-55

[5]

Carral Martínez D and Hitzler P Simperl E, Cimiano P, Polleres A, Corcho O, and Presutti V Extending description logic rules The Semantic Web: Research and Applications 2012 Heidelberg Springer 345-359

[6]

Grau BC, Horrocks I, Krötzsch M, Kupke C, Magka D, Motik B, and Wang Z Acyclicity notions for existential rules and their application to query answering in ontologies JAIR 2013 47 741-808

[7]

Fagin R, Kolaitis PG, Miller RJ, and Popa L Data exchange: semantics and query answering Theor. Comput. Sci. 2005 336 1 89-124

[8]

Glimm B, Lutz C, Horrocks I, and Sattler U Conjunctive query answering for the description logic SHIQ J. Artif. Intell. Res. (JAIR) 2008 31 157-204

[9]

Hitzler, P., Krötzsch, M., Parsia, B., Patel-Schneider, P.F., Rudolph, S. (eds.): OWL 2 Web Ontology Language: Primer. W3C Recommendation (27 October 2009). http://www.w3.org/TR/owl2-primer/

[10]

Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible SROIQ. In: Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, United Kingdom, June 2–5, 2006, pp. 57–67. AAAI Press (2006)

[11]

Kontchakov, R., Lutz, C., Toman, D., Wolter, F., Zakharyaschev, M.: The combined approach to query answering in dl-lite. In: Lin, F., Sattler, U., Truszczynski, M. (eds.) KR 2010. AAAI Press (2010)

[12]

Krötzsch, M., Rudolph, S.: Extending decidable existential rules by joining acyclicity and guardedness. In: IJCAI, pp. 963–968 (2011)

[13]

Krötzsch M, Rudolph S, and Hitzler P Complexities of horn description logics ACM Trans. Comp. Log. 2013 14 1 2:1-2:36

[14]

Marnette, B.: Generalized schema-mappings: from termination to tractability. In: PODS, pp. 13–22 (2009)

[15]

Nenov Y, Piro R, Motik B, Horrocks I, Wu Z, Banerjee J, et al. Arenas M et al. RDFox: a highly-scalable RDF store The Semantic Web - ISWC 2015 2015 Heidelberg Springer 3-20

[16]

Rudolph, S., Glimm, B.: Nominals, inverses, counting, and conjunctive queries or: Why infinity is your friend! CoRR abs/1401.3849 (2014)

[17]

Stefanoni, G., Motik, B., Horrocks, I.: Introducing nominals to the combined query answering approaches for . In: AAAI (2013)

[18]

Stefanoni G, Motik B, Krötzsch M, and Rudolph S The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases J. Artif. Intell. Res. (JAIR) 2014 51 645-705

[19]

Steigmiller A, Liebig T, and Glimm B Konclude: system description J. Web Sem. 2014 27 78-85

[20]

Zhou Y, Grau BC, Nenov Y, Kaminski M, and Horrocks I Pagoda: pay-as-you-go ontology query answering with a datalog reasoner J. Artif. Intell. Res. (JAIR) 2015 54 309-367

Cited By

Sun LRen TZhang XFeng ZHou Y(2023)CECR: Collaborative Semantic Reasoning on the Cloud and EdgeDatabase Systems for Advanced Applications. DASFAA 2023 International Workshops10.1007/978-3-031-35415-1_21(300-313)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-35415-1_21
Carral DDragoste IGonzález LJacobs CKrötzsch MUrbani J(2019)VLog: A Rule Engine for Knowledge GraphsThe Semantic Web – ISWC 201910.1007/978-3-030-30796-7_2(19-35)Online publication date: 26-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-30796-7_2
Carral DDragoste IKrötzsch M(2017)Tractable Query Answering for Expressive Ontologies and Existential RulesThe Semantic Web – ISWC 201710.1007/978-3-319-68288-4_10(156-172)Online publication date: 21-Oct-2017
https://dl.acm.org/doi/10.1007/978-3-319-68288-4_10

Index Terms

A Practical Acyclicity Notion for Query Answering Over Horn- Ontologies

Index terms have been assigned to the content through auto-classification.

Recommendations

Paraconsistent query answering over DL-Lite ontologies

Consistent query answering over description logic based ontologies is an important topic in ontology engineering as it can provide meaningful answers to queries posed over inconsistent ontologies. Current approaches for dealing with this problem usually ...
Acyclicity notions for existential rules and their application to query answering in ontologies

Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with ...
Reformulation-Based Query Answering for RDF Graphs with RDFS Ontologies
The Semantic Web
Abstract
Query answering in RDF knowledge bases has traditionally been performed either through graph saturation, i.e., adding all implicit triples to the graph, or through query reformulation, i.e., modifying the query to look for the explicit triples ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

The Semantic Web – ISWC 2016: 15th International Semantic Web Conference, Kobe, Japan, October 17–21, 2016, Proceedings, Part I

Oct 2016

665 pages

ISBN:978-3-319-46522-7

DOI:10.1007/978-3-319-46523-4

Editors:
Paul Groth
Elsevier Labs, Amsterdam, The Netherlands
,
Elena Simperl
University of Southampton , Southampton, United Kingdom
,
Alasdair Gray
Heriot-Watt University , Edinburgh, United Kingdom
,
Marta Sabou
Vienna University of Technology , Vienna, Austria
,
Markus Krötzsch
Technische Universität Dresden , Dresden, Germany
,
Freddy Lecue
Accenture Technology Labs, Dublin, Ireland and Inria, Sophia Antipolis, France
,
Fabian Flöck
GESIS-Leibniz Institute for the Social Sciences, Cologne, Germany
,
Yolanda Gil
University of Southern California , Marina del Rey, California, USA

© Springer International Publishing AG 2016.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 October 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun LRen TZhang XFeng ZHou Y(2023)CECR: Collaborative Semantic Reasoning on the Cloud and EdgeDatabase Systems for Advanced Applications. DASFAA 2023 International Workshops10.1007/978-3-031-35415-1_21(300-313)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-35415-1_21
Carral DDragoste IGonzález LJacobs CKrötzsch MUrbani J(2019)VLog: A Rule Engine for Knowledge GraphsThe Semantic Web – ISWC 201910.1007/978-3-030-30796-7_2(19-35)Online publication date: 26-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-30796-7_2
Carral DDragoste IKrötzsch M(2017)Tractable Query Answering for Expressive Ontologies and Existential RulesThe Semantic Web – ISWC 201710.1007/978-3-319-68288-4_10(156-172)Online publication date: 21-Oct-2017
https://dl.acm.org/doi/10.1007/978-3-319-68288-4_10

View Options

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

Media

Figures

Other

Tables

View Table of Contents