Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2016 | OriginalPaper | Chapter

On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules

Authors : Meghyn Bienvenu, Michaël Thomazo

Published in: Web Reasoning and Rule Systems

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the setting of ontology-mediated query answering, a query is evaluated over a knowledge base consisting of a database instance and an ontology. While most work in the area focuses on conjunctive queries, navigational queries are gaining increasing attention. In this paper, we investigate the complexity of evaluating the standard form of navigational queries, namely two-way regular path queries, over knowledge bases whose ontology is expressed by means of linear existential rules. More specifically, we show how to extend an approach developed for DL-Lite\(_\mathcal {R}\) to obtain an exponential-time decision procedure for linear rules. We prove that this algorithm achieves optimal worst-case complexity by establishing a matching ExpTime lower bound.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter Towards Practical OBDA with Temporal Ontologies
Footnotes
1
As we only consider the two-way variant, we will use the abbreviation RPQ instead of the more traditional 2RPQ.
 
2
Note that x is required to determine the arity of \(\textit{conf}\).
 
Literature
1.
Baget, J., Leclère, M., Mugnier, M., Salvat, E.: Extending decidable cases for rules with existential variables. In: Proceedings of IJCAI, pp. 677–682 (2009)
2.
Baget, J., Bienvenu, M., Mugnier, M., Rocher, S.: Combining existential rules and transitivity: next steps. In: Proceedings of IJCAI, pp. 2720–2726 (2015)
3.
Bienvenu, M., Calvanese, D., Ortiz, M., Šimkus, M.: Nested regular path queries in description logics. In: Proceedings of KR (2014)
4.
Bienvenu, M., Ortiz, M.: Ontology-mediated query answering with data-tractable description logics. In: Faber, W., Paschke, A. (eds.) Reasoning Web 2015. LNCS, vol. 9203, pp. 218–307. Springer, Heidelberg (2015)CrossRef
5.
Bienvenu, M., Ortiz, M., Simkus, M.: Regular path queries in lightweight description logics: complexity and algorithms. J. Artif. Intell. Res. (JAIR) 53, 315–374 (2015)MathSciNetMATH
6.
Bourhis, P., Krötzsch, M., Rudolph, S.: How to best nest regular path queries. In: Proceedings of DL, pp. 404–415 (2014)
7.
Calì, A., Gottlob, G., Kifer, M.: Taming the infinite chase: query answering under expressive relational constraints. In: Proceedings of KR, pp. 70–80 (2008)
8.
Calvanese, D., Eiter, T., Ortiz, M.: Answering regular path queries in expressive description logics: an automata-theoretic approach. In: Proceedings of AAAI, pp. 391–396 (2007)
9.
Calvanese, D., Eiter, T., Ortiz, M.: Regular path queries in expressive description logics with nominals. In: Proceedings of IJCAI, pp. 714–720 (2009)
10.
Calvanese, D., Eiter, T., Ortiz, M.: Answering regular path queries in expressive description logics via alternating tree-automata. Inf. Comput. 237, 12–55 (2014)MathSciNetCrossRefMATH
11.
Florescu, D., Levy, A., Suciu, D.: Query containment for conjunctive queries with regular expressions. In: Proceedings of PODS (1998)
12.
13.
Grau, B.C., Horrocks, I., Krötzsch, M., Kupke, C., Magka, D., Motik, B., Wang, Z.: Acyclicity notions for existential rules and their application to query answering in ontologies. J. Artif. Intell. Res. (JAIR) 47, 741–808 (2013)MathSciNetMATH
14.
Johnson, D.S., Klug, A.C.: Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28(1), 167–189 (1984)MathSciNetCrossRefMATH
15.
Kostylev, E.V., Reutter, J.L., Vrgoc, D.: XPath for DL ontologies. In: Proceedings of AAAI (2015)
16.
Maier, D., Mendelzon, A.O., Sagiv, Y.: Testing implications of data dependencies. ACM Trans. Database Syst. 4(4), 455–469 (1979)CrossRef
17.
Marnette, B.: Generalized schema-mappings: from termination to tractability. In: Proceedings of PODS, pp. 13–22 (2009)
18.
Ortiz, M., Rudolph, S., Šimkus, M.: Query answering in the Horn fragments of the description logics \(\cal {SHOIQ}\) and \(\cal {SROIQ}\). In: Proceedings of IJCAI (2011)
19.
Stefanoni, G., Motik, B., Krötzsch, M., Rudolph, S.: The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases. J. Artif. Intell. Res. (JAIR) 51, 645–705 (2014)MathSciNetMATH
Metadata
Title
On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
Authors
Meghyn Bienvenu
Michaël Thomazo
Copyright Year
2016
Book
Web Reasoning and Rule Systems

Print ISBN: 978-3-319-45275-3

Electronic ISBN: 978-3-319-45276-0

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-45276-0_1

Premium Partner

    Image Credits