KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Rudolph, Sebastian; Krötzsch, Markus

Abstract:
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


Seitenaufrufe: 5
seit 01.03.2019
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