Skip to main content

2016 | OriginalPaper | Buchkapitel

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

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

Erschienen in: Web Reasoning and Rule Systems

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: IJCAI (2005) Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: IJCAI (2005)
2.
Zurück zum Zitat Baader, F., Nutt, W.: Basic description logics. In: Description Logic Handbook. pp. 43–95 (2003) Baader, F., Nutt, W.: Basic description logics. In: Description Logic Handbook. pp. 43–95 (2003)
3.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Bienvenu, M., Hansen, P., Lutz, C., Wolter, F.: First order-rewritability and containment of conjunctive queries in horn description logics. In: DLOG (2016) Bienvenu, M., Hansen, P., Lutz, C., Wolter, F.: First order-rewritability and containment of conjunctive queries in horn description logics. In: DLOG (2016)
6.
Zurück zum Zitat Bienvenu, M., Lutz, C., Wolter, F.: First-order rewritability of atomic queries in horn description logics. In: IJCAI (2013) Bienvenu, M., Lutz, C., Wolter, F.: First-order rewritability of atomic queries in horn description logics. In: IJCAI (2013)
7.
Zurück zum Zitat Bienvenu, M., Ortiz, M., Simkus, M.: Conjunctive regular path queries in lightweight description logics. In: IJCAI (2013) Bienvenu, M., Ortiz, M., Simkus, M.: Conjunctive regular path queries in lightweight description logics. In: IJCAI (2013)
8.
Zurück zum Zitat Bourhis, P., Krötzsch, M., Rudolph, S.: Reasonable highly expressive query languages. In: IJCAI (2015) Bourhis, P., Krötzsch, M., Rudolph, S.: Reasonable highly expressive query languages. In: IJCAI (2015)
9.
Zurück zum Zitat 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 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.
Zurück zum Zitat Gottlob, G., Orsi, G., Pieris, A.: ontological queries: rewriting and optimization. In: ICDE (2011) Gottlob, G., Orsi, G., Pieris, A.: ontological queries: rewriting and optimization. In: ICDE (2011)
11.
Zurück zum Zitat Hansen, P., Lutz, C., Seylan, I., Wolter, F.: Query rewriting under EL TBoxes: efficient algorithms. In: Description Logics (2014) Hansen, P., Lutz, C., Seylan, I., Wolter, F.: Query rewriting under EL TBoxes: efficient algorithms. In: Description Logics (2014)
12.
Zurück zum Zitat Hansen, P., Lutz, C., Seylan, I., Wolter, F.: Efficient query rewriting in the description logic EL and beyond. In: IJCAI (2015) Hansen, P., Lutz, C., Seylan, I., Wolter, F.: Efficient query rewriting in the description logic EL and beyond. In: IJCAI (2015)
13.
Zurück zum Zitat Kikot, S., Kontchakov, R., Zakharyaschev, M.: Conjunctive query answering with OWL 2 QL. In: KR (2012) Kikot, S., Kontchakov, R., Zakharyaschev, M.: Conjunctive query answering with OWL 2 QL. In: KR (2012)
14.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Rosati, R.: On conjunctive query answering in EL. In: DL (2007) Rosati, R.: On conjunctive query answering in EL. In: DL (2007)
Metadaten
Titel
Query Rewriting under Linear Knowledge Bases
verfasst von
Mirko M. Dimartino
Andrea Calì
Alexandra Poulovassilis
Peter T. Wood
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-45276-0_6