Flag & Check: Data Access with Monadically Defined Queries

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

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:Other info: Link
  • Forschungsgruppe:Research Group: Computational LogicWissensbasierte Systeme
@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}
}