Semantisches Browsen
Aus International Center for Computational Logic
Existential rules (also known as Datalog+/ … Existential rules (also known as Datalog+/- or tuple-generating dependencies) have been intensively studied in recent years as a prominent formalism in knowledge representation and database systems. We consider them here as a querying formalism, extending classical Datalog, the language of deductive databases. It is well known that the classes of databases recognized by (Boolean) existential rule queries are closed under homomorphisms. Also, due to the existence of a semi-decision procedure (the chase), these database classes are recursively enumerable. We show that, conversely, every homomorphism-closed recursively enumerable query can be expressed as an existential rule query, thus arriving at a precise characterization of existential rules by model-theoretic and computational properties. Although the result is very intuitive, the proof turns out to be non-trivial. This result can be seen as a very expressive counterpart of the prominent Lyndon-Los-Tarski-Theorem characterizing the homomorphism-closed fragment of first-order logic. Notably, our result does not presume the existence of any additional built-in structure on the queried data, such as a linear order on the domain, which is a typical requirement for other characterizations in the spirit of descriptive complexity.s in the spirit of descriptive complexity. +
@inproceedings{RT2015,
author = {Sebastian Rudolph and Micha{\"{e}}l Thomazo},
title = {Characterization of the Expressivity of Existential Rule Queries},
editor = {Qiang Yang and Michael Wooldridge},
booktitle = {Proc. 24th International Joint Conference on Artificial
Intelligence (IJCAI'15)},
publisher = {AAAI Press},
year = {2015},
pages = {3193-3199}
}
author = {Sebastian Rudolph and Micha{\"{e}}l Thomazo},
title = {Characterization of the Expressivity of Existential Rule Queries},
editor = {Qiang Yang and Michael Wooldridge},
booktitle = {Proc. 24th International Joint Conference on Artificial
Intelligence (IJCAI'15)},
publisher = {AAAI Press},
year = {2015},
pages = {3193-3199}
}
Rudolph +
Sebastian +
Sebastian Rudolph, Michaël Thomazo<br/& … Sebastian Rudolph, Michaël Thomazo<br/> '''[[Inproceedings3018|<b>Characterization of the Expressivity of Existential Rule Queries</b>]]''' <br/>__NOTOC__In Qiang Yang, Michael Wooldridge, eds., <i>Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI'15)</i>, 3193-3199, 2015. AAAI Press<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Inproceedings3018|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:Ijcai-15-rt.pdf|Download]]:Ijcai-15-rt.pdf|Download]] +
Sebastian Rudolph, Michaël Thomazo<br/& … Sebastian Rudolph, Michaël Thomazo<br/> '''[[Inproceedings3018/en|<b>Characterization of the Expressivity of Existential Rule Queries</b>]]''' <br/>__NOTOC__In Qiang Yang, Michael Wooldridge, eds., <i>Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI'15)</i>, 3193-3199, 2015. AAAI Press<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Inproceedings3018|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:Ijcai-15-rt.pdf|Download]]:Ijcai-15-rt.pdf|Download]] +
Anzeigetitel„Anzeigetitel <span style="font-size:small;">(Display title of)</span>“ ist ein softwareseitig fest definiertes Attribut, das einen eindeutigen Anzeigetitel zu einem Objekt speichert und ihm zuweist. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
Characterization of the Expressivity of Existential Rule Queries +
Zuletzt geändert„Zuletzt geändert <span style="font-size:small;">(Modification date)</span>“ ist ein softwareseitig fest definiertes Attribut, das das Datum der letzten Änderung einer Seite speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
28. Mai 2016, 20:17:13 +
Hat Abfrage„Hat Abfrage <span style="font-size:small;">(Has query)</span>“ ist ein softwareseitig fest definiertes Attribut, das die Metainformationen einer Abfrage als <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Subobject">Subobjekt</a> speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
Characterization of the Expressivity of Existential Rule Queries +, Characterization of the Expressivity of Existential Rule Queries +, Characterization of the Expressivity of Existential Rule Queries +, Characterization of the Expressivity of Existential Rule Queries +, Characterization of the Expressivity of Existential Rule Queries + und Characterization of the Expressivity of Existential Rule Queries +
