Inproceedings4010: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Markus Krötzsch (Diskussion | Beiträge) K (Textersetzung - „Information Systems“ durch „Knowledge Systems“) |
Markus Krötzsch (Diskussion | Beiträge) K (Textersetzung - „}} {{Publikation Author |Rank=2 |Author=“ durch „|FurtherAuthors=“) |
||
Zeile 2: | Zeile 2: | ||
|ErsterAutorNachname=Rudolph | |ErsterAutorNachname=Rudolph | ||
|ErsterAutorVorname=Sebastian | |ErsterAutorVorname=Sebastian | ||
|FurtherAuthors=Markus Krötzsch | |||
| | |||
}} | }} | ||
{{Inproceedings | {{Inproceedings |
Version vom 24. Oktober 2014, 17:51 Uhr
Flag & Check: Data Access with Monadically Defined Queries
Sebastian RudolphSebastian Rudolph, Markus KrötzschMarkus Krötzsch
Sebastian Rudolph, Markus Krötzsch
Flag & Check: Data Access with Monadically Defined Queries
Proc. 32nd Symposium on Principles of Database Systems (PODS'13), 151-162, June 2013. ACM
Flag & Check: Data Access with Monadically Defined Queries
Proc. 32nd Symposium on Principles of Database Systems (PODS'13), 151-162, June 2013. ACM
- KurzfassungAbstract
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). We show that (NE)MODEQ answering remains decidable in the presence of a well-known 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. - Weitere Informationen unter:Further Information: Link
- Forschungsgruppe:Research Group: Computational LogicComputational Logic, Knowledge SystemsKnowledge-Based Systems
@inproceedings{RK2013,
author = {Sebastian Rudolph and Markus Kr{\"{o}}tzsch},
title = {Flag \& Check: Data Access with Monadically Defined Queries},
booktitle = {Proc. 32nd Symposium on Principles of Database Systems (PODS'13)},
publisher = {ACM},
year = {2013},
month = {June},
pages = {151-162},
doi = {10.1145/2463664.2465227}
}