Inproceedings4010: Unterschied zwischen den Versionen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
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
{{Publikation Author
|Rank=2
|Author=Markus Krötzsch
}}
}}
{{Inproceedings
{{Inproceedings

Version vom 24. Oktober 2014, 17:51 Uhr

Toggle side column

Flag & Check: Data Access with Monadically Defined Queries

Sebastian RudolphSebastian Rudolph,  Markus KrötzschMarkus Krötzsch
Flag & Check: Data Access with Monadically Defined Queries


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
  • 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 LogicKnowledge 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}
}