Published: 2012 August
Type: Technical Report
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe
We propose two novel querying formalisms: monadically defined queries (MODEQs) and the more expressive nested monadically defined queries (NEMODEQs). Both subsume and go beyond conjunctive queries, conjunctive two-way regular path queries, and monadic Datalog queries. Moreover, MODEQs and NEMODEQs can be expressed as Datalog queries but also in monadic second-order logic, but, unlike those formalisms, they have a decidable query subsumption problem and favorable query answering complexities: they both exhibit P data complexity, whereas the combined complexity is NP for MODEQs and PSpace for NEMODEQs. We show that MODEQ answering remains decidable in the presence tuple-generating dependencies (TGDs) of a certain type known as bounded-treewidth sets. We then investigate the popular topic of query rewriting under TGD constraints. To this end, we extend the notion of first-order rewritability to (NE)MODEQ rewritability and show that this extended notion can cope with a large variety of TGDs. We devise methods for rewriting rule sets to queries in this new formalism. Finally, we show that rewriting techniques can also be applied partially, and (NE)MODEQ answering is still decidable, if the non-rewritable part of the TGDs allows for decidable (NE)MODEQ answering on other grounds.