Techreport3019: Unterschied zwischen den Versionen
Sru (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorNachname=Krötzsch |ErsterAutorVorname=Markus }} {{Publikation Author |Rank=2 |Author=Sebastian Rudolph }} {{Techreport |Ti…“) |
Sru (Diskussion | Beiträge) |
||
| Zeile 18: | Zeile 18: | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Rules and ontologies can be used to enrich a database system with advanced data access capabilities. The success of this paradigm has led to a number of languages such as DL-Lite, Datalog+/- and OWL RL. The two major approaches to answering queries under constraints expressed in such languages are forward-chaining (materialization) and backward-chaining (query rewriting). The latter is typically focused on first-order queries that have only limited expressivity. We propose a querying formalism based on monadic second-order logic which subsumes and goes beyond conjunctive queries and regular path queries, but still has a decidable query subsumption problem. We devise methods for rewriting rule sets to queries in this new formalism and we show that query entailment in most of the established rule-based approaches can be decided by combining two methods: (i) bottom-up forward-chaining computation w.r.t. a rule set with the bounded treewidth model property and (ii) top-down second-order query rewriting w.r.t. a rewritable rule set. | |Abstract=Rules and ontologies can be used to enrich a database system with advanced data access capabilities. The success of this paradigm has led to a number of languages such as DL-Lite, Datalog+/- and OWL RL. The two major approaches to answering queries under constraints expressed in such languages are forward-chaining (materialization) and backward-chaining (query rewriting). The latter is typically focused on first-order queries that have only limited expressivity. We propose a querying formalism based on monadic second-order logic which subsumes and goes beyond conjunctive queries and regular path queries, but still has a decidable query subsumption problem. We devise methods for rewriting rule sets to queries in this new formalism and we show that query entailment in most of the established rule-based approaches can be decided by combining two methods: (i) bottom-up forward-chaining computation w.r.t. a rule set with the bounded treewidth model property and (ii) top-down second-order query rewriting w.r.t. a rewritable rule set. | ||
| + | |Download=Paper.pdf, | ||
|Projekt=ExpresST | |Projekt=ExpresST | ||
|Forschungsgruppe=Wissensmanagement | |Forschungsgruppe=Wissensmanagement | ||
| + | }} | ||
| + | {{Forschungsgebiet Auswahl | ||
| + | |Forschungsgebiet=Deduktive Datenbanken | ||
| + | }} | ||
| + | {{Forschungsgebiet Auswahl | ||
| + | |Forschungsgebiet=Informationssysteme | ||
| + | }} | ||
| + | {{Forschungsgebiet Auswahl | ||
| + | |Forschungsgebiet=Logik | ||
| + | }} | ||
| + | {{Forschungsgebiet Auswahl | ||
| + | |Forschungsgebiet=Semantische Technologien | ||
}} | }} | ||
Version vom 1. Dezember 2011, 15:32 Uhr
Published: 2011
November
Type: Technical Report
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe
Archivierungsnummer:3019
Kurzfassung
Rules and ontologies can be used to enrich a database system with advanced data access capabilities. The success of this paradigm has led to a number of languages such as DL-Lite, Datalog+/- and OWL RL. The two major approaches to answering queries under constraints expressed in such languages are forward-chaining (materialization) and backward-chaining (query rewriting). The latter is typically focused on first-order queries that have only limited expressivity. We propose a querying formalism based on monadic second-order logic which subsumes and goes beyond conjunctive queries and regular path queries, but still has a decidable query subsumption problem. We devise methods for rewriting rule sets to queries in this new formalism and we show that query entailment in most of the established rule-based approaches can be decided by combining two methods: (i) bottom-up forward-chaining computation w.r.t. a rule set with the bounded treewidth model property and (ii) top-down second-order query rewriting w.r.t. a rewritable rule set.
Download: Media:Paper.pdf
Semantische Technologien, Informationssysteme, Deduktive Datenbanken, Logik