Flag and check: data access with monadically defined queries.
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 lo...
| প্রধান লেখক: | , |
|---|---|
| অন্যান্য লেখক: | |
| বিন্যাস: | Conference item |
| প্রকাশিত: |
ACM
2013
|
| _version_ | 1826280609977204736 |
|---|---|
| author | Rudolph, S Krötzsch, M |
| author2 | Hull, R |
| author_facet | Hull, R Rudolph, S Krötzsch, M |
| author_sort | Rudolph, S |
| collection | OXFORD |
| description | 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. Copyright 2013 ACM. |
| first_indexed | 2024-03-07T00:16:16Z |
| format | Conference item |
| id | oxford-uuid:7af1d974-72fc-4a68-9cb1-22a00549a08d |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:16:16Z |
| publishDate | 2013 |
| publisher | ACM |
| record_format | dspace |
| spelling | oxford-uuid:7af1d974-72fc-4a68-9cb1-22a00549a08d2022-03-26T20:47:21ZFlag and check: data access with monadically defined queries.Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:7af1d974-72fc-4a68-9cb1-22a00549a08dSymplectic Elements at OxfordACM2013Rudolph, SKrötzsch, MHull, RFan, WWe 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. Copyright 2013 ACM. |
| spellingShingle | Rudolph, S Krötzsch, M Flag and check: data access with monadically defined queries. |
| title | Flag and check: data access with monadically defined queries. |
| title_full | Flag and check: data access with monadically defined queries. |
| title_fullStr | Flag and check: data access with monadically defined queries. |
| title_full_unstemmed | Flag and check: data access with monadically defined queries. |
| title_short | Flag and check: data access with monadically defined queries. |
| title_sort | flag and check data access with monadically defined queries |
| work_keys_str_mv | AT rudolphs flagandcheckdataaccesswithmonadicallydefinedqueries AT krotzschm flagandcheckdataaccesswithmonadicallydefinedqueries |