Flag & Check: Data Access with Monadically Defined Queries

From korrekt.org

Sebastian Rudolph, Markus Krötzsch

Flag & Check: Data Access with Monadically Defined Queries

Abstract. 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). Moreover, (NE)MODEQ answering remains decidable in the presence of a 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.

Published at PODS 2013 (Conference paper)

Download PDF (last update: Feb 26 2013)

Citation details

  • Sebastian Rudolph, Markus Krötzsch. Flag & Check: Data Access with Monadically Defined Queries. In Richard Hull, Wenfei Fan, eds.: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2013), pp. 151–162. ACMProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2013.


The above PDF is still a preliminary version of this paper. It will be updated with a camera ready version in due course.


Query languages, Rule languages