Techreport3030: Unterschied zwischen den Versionen
Sru (Diskussion | Beiträge) |
Sru (Diskussion | Beiträge) |
||
Zeile 19: | Zeile 19: | ||
|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 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 | ||
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. | 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- | + | |Download=TR-NEMODEQs.pdf, |
|Projekt=ExpresST | |Projekt=ExpresST | ||
|Forschungsgruppe=Wissensmanagement | |Forschungsgruppe=Wissensmanagement | ||
}} | }} |
Version vom 21. September 2012, 20:31 Uhr
Published: 2012
August
Type: Technical Report
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe
Archivierungsnummer:3030
Kurzfassung
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
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: Media:TR-NEMODEQs.pdf