Second-Order Queries for Rule-Based Data Access
Markus Krötzsch, Sebastian Rudolph
Second-Order Queries for Rule-Based Data Access
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.
Published at Karlsruhe Institute of Technology (Technical report)
Download PDF (last update: Dec 1 2011)
Citation details
- Markus Krötzsch, Sebastian Rudolph. Second-Order Queries for Rule-Based Data Access. In Institute AIFB Technical Report 3019. Karlsruhe Institute of TechnologyProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2011.
author = {Markus Kr{\"o}tzsch and Sebastian Rudolph},
title = {Second-Order Queries for Rule-Based Data Access},
year = {2011},
number = {3019},
institution = {Institute AIFB, Karlsruhe Institute of
Technology},,
note = {Available online at
\url{http://korrekt.org/papers/KroetzschRudolph_MSO-Queries_2011.pdf}}
}
Remarks
This is an early precursor of the work Flag & Check: Data Access with Monadically Defined Queries. It is suggested to consult the newer version.
