KIT | KIT-Bibliothek | Impressum | Datenschutz

Second-Order Queries for Rule-Based Data Access : Technical Report 3019

Krötzsch, Markus; Rudolph, Sebastian


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

Zugehörige Institution(en) am KIT Institut für Angewandte Informatik und Formale Beschreibungsverfahren (AIFB)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2011
Sprache Englisch
Identifikator KITopen-ID: 1000091501
Verlag Karlsruher Institut für Technologie (KIT)
Umfang 15 S.
Externe Relationen Abstract/Volltext
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page