Home |  ENGLISH |  Kontakt |  Impressum |  Anmelden |  KIT

Techreport3030

Aus Aifbportal

Wechseln zu: Navigation, Suche


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




Published: 2013 Februar
Type: Technical Report
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe
Archivierungsnummer:3030

BibTeX
Kurzfassung
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). Moreover, (NE)MODEQ answering remains decidable in the presence of a 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.

Download: Media:RK-pods2013-TR.pdf

Projekt

ExpresST



Forschungsgruppe

Wissensmanagement