Flag & Check: Data Access with Monadically Defined Queries
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.
author = {Sebastian Rudolph and Markus Kr{\"o}tzsch},
title = {Flag \& Check: {Data} Access with
Monadically Defined Queries},
editor = {Richard Hull and Wenfei Fan},
booktitle = {Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART
Symposium on Principles of Database Systems
(PODS'13)},
publisher = {ACM},
year = {2013},
pages = {151-162}
}
Remarks
The above PDF is still a preliminary version of this paper. It will be updated with a camera ready version in due course.
