Techreport3030: Unterschied zwischen den Versionen
Sru (Diskussion | Beiträge) |
Sru (Diskussion | Beiträge) |
||
Zeile 8: | Zeile 8: | ||
}} | }} | ||
{{Techreport | {{Techreport | ||
− | |Title=Flag & Check - Data | + | |Title=Flag & Check - Data Access with Monadically Defined Queries (Extended Technical Report) |
− | |Year= | + | |Year=2013 |
− | |Month= | + | |Month=Februar |
|Institution=Institut AIFB, KIT | |Institution=Institut AIFB, KIT | ||
|Address=Karlsruhe | |Address=Karlsruhe | ||
Zeile 17: | Zeile 17: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
− | |Abstract=We | + | |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). 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=TR-NEMODEQs.pdf, | |Download=TR-NEMODEQs.pdf, | ||
|Projekt=ExpresST | |Projekt=ExpresST | ||
|Forschungsgruppe=Wissensmanagement | |Forschungsgruppe=Wissensmanagement | ||
}} | }} |
Version vom 26. Februar 2013, 21:54 Uhr
Published: 2013
Februar
Type: Technical Report
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe
Archivierungsnummer:3030
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:TR-NEMODEQs.pdf