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:
On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Query Rewriting under Linear \(\mathcal {EL}\) Knowledge Bases

Authors : Mirko M. Dimartino, Andrea Calì, Alexandra Poulovassilis, Peter T. Wood

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

With the adoption of the recent SPARQL 1.1 standard, RDF databases are capable of directly answering more expressive queries than simple conjunctive queries. In this paper we exploit such capabilities to answer conjunctive queries (CQs) under ontologies expressed in the description logic called linear \(\mathcal {EL}^ {\ell }in \), a restricted form of \(\mathcal {EL}\). In particular, we show a query answering algorithm that rewrites a given CQ into a conjunctive regular path query (CRPQ) which, evaluated on the given instance, returns the correct answer. Our technique is based on the representation of infinite unions of CQs by non-deterministic finite-state automata. Our results achieve optimal data complexity, as well as producing rewritings straightforwardly implementable in SPARQL 1.1.

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
previous chapter Revisiting Grounded Circumscription in Description Logics
next chapter Scalable Reasoning by Abstraction Beyond DL-Lite
Literature
1.
Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: IJCAI (2005)
2.
Baader, F., Nutt, W.: Basic description logics. In: Description Logic Handbook. pp. 43–95 (2003)
3.
Baget, J.F., Leclre, M., Mugnier, M.L., Salvat, E.: On rules with existential variables: walking the decidability line. Artif. Intell. 175(9), 1620–1654 (2011)MathSciNetCrossRefMATH
4.
Barcelo, P., Libkin, L., Lin, A.W., Wood, P.T.: Expressive languages for path queries over graph-structured data. TODS 37(4), 31 (2012)CrossRef
5.
Bienvenu, M., Hansen, P., Lutz, C., Wolter, F.: First order-rewritability and containment of conjunctive queries in horn description logics. In: DLOG (2016)
6.
Bienvenu, M., Lutz, C., Wolter, F.: First-order rewritability of atomic queries in horn description logics. In: IJCAI (2013)
7.
Bienvenu, M., Ortiz, M., Simkus, M.: Conjunctive regular path queries in lightweight description logics. In: IJCAI (2013)
8.
Bourhis, P., Krötzsch, M., Rudolph, S.: Reasonable highly expressive query languages. In: IJCAI (2015)
9.
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-lite family. J. Autom. Reason. 39(3), 385–429 (2007)MathSciNetCrossRefMATH
10.
Gottlob, G., Orsi, G., Pieris, A.: ontological queries: rewriting and optimization. In: ICDE (2011)
11.
Hansen, P., Lutz, C., Seylan, I., Wolter, F.: Query rewriting under EL TBoxes: efficient algorithms. In: Description Logics (2014)
12.
Hansen, P., Lutz, C., Seylan, I., Wolter, F.: Efficient query rewriting in the description logic EL and beyond. In: IJCAI (2015)
13.
Kikot, S., Kontchakov, R., Zakharyaschev, M.: Conjunctive query answering with OWL 2 QL. In: KR (2012)
14.
Kontchakov, R., Zakharyaschev, M.: An introduction to description logics and query rewriting. In: Koubarakis, M., Stamou, G., Stoilos, G., Horrocks, I., Kolaitis, P., Lausen, G., Weikum, G. (eds.) Reasoning Web. LNCS, vol. 8714, pp. 195–244. Springer, Heidelberg (2014)
15.
Mosurovic, M., Krdzavac, N., Graves, H., Zakharyaschev, M.: A decidable extension of SROIQ with complex role chains and unions. JAIR 47, 809–851 (2013)MathSciNetMATH
16.
Pérez-Urbina, H., Horrocks, I., Motik, B.: Efficient query answering for OWL 2. In: Bernstein, A., Karger, D.R., Heath, T., Feigenbaum, L., Maynard, D., Motta, E., Thirunarayan, K. (eds.) ISWC 2009. LNCS, vol. 5823, pp. 489–504. Springer, Heidelberg (2009)CrossRef
17.
Schewe, K.-D., Thalheim, B.: Semantics in data and knowledge bases. In: Schewe, K.-D., Thalheim, B. (eds.) SDKB 2008. LNCS, vol. 4925, pp. 1–25. Springer, Heidelberg (2008)CrossRef
18.
Rosati, R.: On conjunctive query answering in EL. In: DL (2007)
Metadata
Title
Query Rewriting under Linear Knowledge Bases
Authors
Mirko M. Dimartino
Andrea Calì
Alexandra Poulovassilis
Peter T. Wood
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_6

Premium Partner

    Image Credits