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:
On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Negative Knowledge for Certain Query Answers

verfasst von : Leonid Libkin

Erschienen in: Web Reasoning and Rule Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Querying incomplete data usually amounts to finding answers we are certain about. Standard approaches concentrate on positive information about query answers, and miss negative knowledge, which can be useful for two reasons. First, sometimes it is the only type of knowledge one can infer with certainty, and second, it may help one find good and efficient approximations of positive certain answers. Our goal is to consider a framework for defining both positive and negative certain knowledge about query answers and to show two applications of it. First, we demonstrate that it naturally leads to a way of representing certain information that has hitherto not been used in querying incomplete databases. Second, we show that approximations of such certain information can be computed efficiently for all first-order queries over relational databases.

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 The Impact of Active Domain Predicates on Guarded Existential Rules
Nächstes Kapitel Extending Weakly-Sticky Datalog: Query-Answering Tractability and Optimizations
Literatur
1.
Abiteboul, S., Kanellakis, P., Grahne, G.: On the representation and querying of sets of possible worlds. Theoret. Comput. Sci. 78(1), 158–187 (1991)MathSciNetMATH
2.
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)MATH
3.
Abiteboul, S., Segoufin, L., Vianu, V.: Representing and querying XML with incomplete information. ACM TODS 31(1), 208–254 (2006)CrossRef
4.
Arenas, M., Barceló, P., Libkin, L., Murlak, F.: Foundations of Data Exchange. Cambridge University Press, Cambridge (2014)MATH
5.
6.
7.
Bertossi, L.: Database Repairing and Consistent Query Answering. Morgan & Claypool Publishers, San Rafael (2011)
8.
Bienvenu, M., ten Cate, B., Lutz, C., Wolter, F.: Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP. ACM TODS 39(4), 1–44 (2014)MathSciNetCrossRef
9.
Buneman, P., Jung, A., Ohori, A.: Using power domains to generalize relational databases. Theoret. Comput. Sci. 91(1), 23–55 (1991)MathSciNetCrossRefMATH
10.
Calì, A., Lembo, D., Rosati, R.: On the decidability and complexity of query answering over inconsistent and incomplete databases. In: PODS, pp. 260–271 (2003)
11.
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
12.
13.
Console, M., Guagliardo, P., Libkin, L.: Approximations and refinements of certain answers via many-valued logics. In: KR 2016, pp. 349–358 (2016)
14.
Date, C.J., Darwen, H.: A Guide to the SQL Standard. Addison-Wesley, Reading (1996)
15.
Fink, R., Olteanu, D.: On the optimal approximation of queries using tractable propositional languages. In: ICDT, pp. 174–185 (2011)
16.
Garofalakis, M., Gibbons, P.: Approximate query processing: taming the terabytes. In: VLDB (2001)
17.
Gheerbrant, A., Libkin, L., Sirangelo, C.: Naïve evaluation of queries over incomplete databases. ACM TODS 39(4), 231 (2014)MathSciNetCrossRef
18.
Gheerbrant, A., Libkin, L.: Certain answers over incomplete XML documents: extending tractability boundary. Theory Comput. Syst. 57(4), 892–926 (2015)MathSciNetCrossRefMATH
19.
Guagliardo, P., Libkin, L.: Making SQL queries correct on incomplete databases: a feasibility study. In: PODS 2016, pp. 211–223 (2016)
20.
Gunter, C.: Semantics of Programming Languages. The MIT Press, Cambridge (1992)MATH
21.
Herschel, M., Hernández, M.: Explaining missing answers to SPJUA queries. PVLDB 3(1), 185–196 (2010)
22.
23.
Ioannidis, Y.: Approximations in database systems. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 16–30. Springer, Heidelberg (2002)CrossRef
24.
Klein, H.: On the use of marked nulls for the evaluation of queries against incomplete relational databases. In: Polle, T., Ripke, T., Schewe, K. (eds.) Fundamentals of Information Systems, pp. 81–98. Springer, New York (1999)CrossRef
25.
Kontchakov, R., Lutz, C., Toman, D., Wolter, F., Zakharyaschev, M.: The combined approach to ontology-based data access. In: IJCAI, pp. 2656–2661 (2011)
26.
Lenzerini, M.: Data integration: a theoretical perspective. In: ACM Symposium on Principles of Database Systems (PODS), pp. 233–246 (2002)
27.
Levesque, H.: A completeness result for reasoning with incomplete first-order knowledge bases. In: KR, pp. 14–23 (1998)
28.
29.
30.
Lipski, W.: On semantic issues connected with incomplete information databases. ACM TODS 4(3), 262–296 (1979)CrossRef
31.
Lipski, W.: On relational algebra with marked nulls. In: PODS 1984, pp. 201–203 (1984)
32.
Liu, Y., Levesque, H.: A tractability result for reasoning with incomplete first-order knowledge bases. In: IJCAI, pp. 83–88 (2003)
33.
Reiter, R.: Towards a logical reconstruction of relational database theory. In: Brodie, M.L., Mylopoulos, J., Schmidt, J.W. (eds.) On Conceptual Modelling, pp. 191–233. Springer, New York (1982)
34.
Reiter, R.: A sound and sometimes complete query evaluation algorithm for relational databases with null values. J. ACM 33(2), 349–370 (1986)MathSciNetCrossRef
35.
Rosati, R.: On the decidability and finite controllability of query processing in databases with incomplete information. In: PODS, pp. 356–365 (2006)
36.
Shmueli, O., Tsur, S.: Logical diagnosis of LDL programs. In: ICLP, pp. 112–129 (1990)
Metadaten
Titel
Negative Knowledge for Certain Query Answers
verfasst von
Leonid Libkin
Copyright-Jahr
2016
Buch
Web Reasoning and Rule Systems

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

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

Copyright-Jahr: 2016

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

Premium Partner

    Bildnachweise