Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Reducing the Degradation of Sentiment Analysis for Text Collections Spread over a Period of Time Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom

verfasst von : Olga Gerasimova, Stanislav Kikot, Vladimir Podolskii, Michael Zakharyaschev

Erschienen in: Knowledge Engineering and Semantic Web

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We report on our recent results in the ongoing attempts to classify conjunctive queries (CQs) \({\varvec{q}}\) according to the data complexity of answering ontology-mediated queries of the form \((\{A \sqsubseteq F \sqcup T\},{\varvec{q}})\). In particular, we present new families of path CQs for which this problem is NL-, P- or coNP-complete.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Temporal Reasoning with Non-convex Intervals
Nächstes Kapitel QSMat: Query-Based Materialization for Efficient RDF Stream Processing
Fußnoten
2
The OMQ \({{\varvec{Q}}= (\mathcal {D}{is}_\top , {\varvec{q}})}\) with this CQ \({\varvec{q}}\) can be interpreted as follows, assuming that F stands for ‘female’, T for ‘male’, \(\top \) for all the individuals of the domain in question, and R for the ‘follows’ relation: given a graph of Twitter users, in which the gender may be specified for some nodes and missing for the other ones, check whether there certainly exist two people (nodes) in the graph of different gender who follow each other.
 
Literatur
1.
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Menlo Park (1995)MATH
2.
3.
Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. Artif. Intell. Res. (JAIR) 36, 1–69 (2009)MathSciNetMATH
4.
Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press, Cambridge (2017)CrossRefMATH
5.
Bienvenu, M., ten Cate, B., Lutz, C., Wolter, F.: Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP. ACM Trans. Database Syst. 39(4), 33:1–44 (2014)MathSciNetCrossRef
6.
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, Cham (2015). doi:10.​1007/​978-3-319-21768-0_​9 CrossRef
7.
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. Reasoning 39(3), 385–429 (2007)MathSciNetCrossRefMATH
8.
9.
10.
Gerasimova, O., Kikot, S., Podolskii, V., Zakharyaschev, M.: On the data complexity of ontology-mediated queries with a covering axiom. In: Proceedings of the 30th International Workshop on Description Logics (2017)
11.
12.
13.
Hernich, A., Lutz, C., Ozaki, A., Wolter, F.: Schema.org as a description logic. In: Calvanese, D., Konev, B. (eds.) Proceedings of the 28th International Workshop on Description Logics, Athens, Greece, June 7–10, 2015, CEUR Workshop Proceedings, vol. 1350. CEUR-WS.org (2015). http://​ceur-ws.​org/​Vol-1350/​paper-24.​pdf
14.
15.
Kontchakov, R., Rodríguez-Muro, M., Zakharyaschev, M.: Ontology-based data access with databases: a short course. In: Rudolph, S., Gottlob, G., Horrocks, I., van Harmelen, F. (eds.) Reasoning Web 2013. LNCS, vol. 8067, pp. 194–229. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-39784-4_​5 CrossRef
16.
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 2014. LNCS, vol. 8714, pp. 195–244. Springer, Cham (2014). doi:10.​1007/​978-3-319-10587-1_​5 CrossRef
17.
Krisnadhi, A., Lutz, C.: Data complexity in the \(\cal{EL}\) family of description logics. In: Dershowitz, N., Voronkov, A. (eds.) LPAR 2007. LNCS, vol. 4790, pp. 333–347. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-75560-9_​25 CrossRef
18.
Lutz, C., Sabellek, L.: Ontology-mediated querying with \(\cal{EL}\): Trichotomy and linear datalog rewritabvility. In: Proceedings of the 30th International Workshop on Description Logics (2017)
19.
Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. Data Semant. X 4900, 133–173 (2008)CrossRefMATH
20.
21.
Schaerf, A.: On the complexity of the instance checking problem in concept languages with existential quantification. J. Intell. Inf. Syst. 2, 265–278 (1993)CrossRef
Metadaten
Titel
More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom
verfasst von
Olga Gerasimova
Stanislav Kikot
Vladimir Podolskii
Michael Zakharyaschev
Copyright-Jahr
2017
Buch
Knowledge Engineering and Semantic Web

Print ISBN: 978-3-319-69547-1

Electronic ISBN: 978-3-319-69548-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-69548-8_11

Neuer Inhalt

    Bildnachweise