Flag & Check: Data Access with Monadically Defined Queries

Sebastian RudolphSebastian Rudolph, Markus KrötzschMarkus Krötzsch

ISBN: 978-1-4503-2066-5
Download
DOI Link

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

Details
Bibtex

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, Wissensbasierte SystemeKnowledge-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}
}