Stage-oe-small.jpg

Techreport3030

Aus Aifbportal
Version vom 31. Juli 2013, 21:46 Uhr von Sru (Diskussion | Beiträge)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
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


Forschungsgebiet