Stage-oe-small.jpg

Techreport3030: Unterschied zwischen den Versionen

Aus Aifbportal
Wechseln zu:Navigation, Suche
Zeile 8: Zeile 8:
 
}}
 
}}
 
{{Techreport
 
{{Techreport
|Title=Flag & Check - Data-Tractable Expressive Queries for Intelligent Databases (Extended Technical Report)
+
|Title=Flag & Check - Data Access with Monadically Defined Queries (Extended Technical Report)
|Year=2012
+
|Year=2013
|Month=August
+
|Month=Februar
 
|Institution=Institut AIFB, KIT
 
|Institution=Institut AIFB, KIT
 
|Address=Karlsruhe
 
|Address=Karlsruhe
Zeile 17: Zeile 17:
 
}}
 
}}
 
{{Publikation Details
 
{{Publikation Details
|Abstract=We propose two novel querying formalisms: monadically defined queries (MODEQs) and the more expressive nested monadically defined queries (NEMODEQs). Both subsume and go beyond conjunctive queries, conjunctive two-way regular path queries, and monadic Datalog queries. Moreover, MODEQs and NEMODEQs can be expressed as Datalog queries but also in monadic second-order logic, but, unlike those formalisms, they have a decidable query subsumption problem and favorable query answering complexities: they both exhibit P data complexity, whereas the combined complexity is NP for MODEQs and PSpace for NEMODEQs. We show that MODEQ answering remains decidable in the presence tuple-generating dependencies (TGDs) of a certain type known as bounded-treewidth sets. We then investigate the popular topic of query rewriting under TGD constraints. To this end, we extend the notion of first-order rewritability to (NE)MODEQ rewritability and show that this extended notion can cope with a large variety of TGDs. We devise
+
|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.
methods for rewriting rule sets to queries in this new formalism. Finally, we show that rewriting techniques can also be applied partially, and (NE)MODEQ answering is still decidable, if the non-rewritable part of the TGDs allows for 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


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:TR-NEMODEQs.pdf

Projekt

ExpresST



Forschungsgruppe

Wissensmanagement


Forschungsgebiet