KIT | KIT-Bibliothek | Impressum | Datenschutz

Flag & Check - Data Access with Monadically Defined Queries (Extended Technical Report)

Rudolph, Sebastian; Krötzsch, Markus

We introduce monadically defined queries (MODEQs) and nested monadically defined queries (NEMODEQs), two querying formalisms that extend conjunctive queries, conjunctive two-way regular path queries, and monadic Datalog queries. Both can be expressed as Datalog queries and in monadic second-order logic, yet they have a decidable query containment problem and favorable query answering complexities: a data complexity of P, and a combined complexity of NP (MODEQs) and PSpace (NEMODEQs). We show that (NE)MODEQ answering remains decidable in the presence of a well-known generic class of tuple-generating dependencies. In addition, techniques to rewrite queries under dependencies into (NE)MODEQs are introduced. Rewriting can be applied partially, and (NE)MODEQ answering is still decidable if the non-rewritable part of the TGDs permits decidable (NE)MODEQ answering on other grounds.

Open Access Logo

Zugehörige Institution(en) am KIT Institut für Angewandte Informatik und Formale Beschreibungsverfahren (AIFB)
Publikationstyp Forschungsbericht
Jahr 2013
Sprache Englisch
Identifikator KITopen-ID: 1000091507
Verlag KIT, Karlsruhe
Umfang 18 S.
Externe Relationen Abstract/Volltext
Schlagworte query containment; tuple-generating dependencies; Datalog
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page