View publication
| Title | Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries |
| Authors | Marcelo Arenas, Pablo Barceló, Juan Reutter |
| Publication date | 2009 |
| Abstract | The class of unions of conjunctive queries ($\ucq$) has been shown to be particularly well-behaved for data exchange; its certain answers can be computed in polynomial time (in terms of data complexity). However, this is not the only class with this property; the certain answers to any $\udat$ program can also can be computed in polynomial time. The problem is that both $\ucq$ and $\udat$ do not allow negated atoms, as adding an unrestricted form of negation to these languages yields to intractability. \n\n In this paper, we propose a language called $\dat$ that extends $\udat$ with a restricted form of negation, and study some of its fundamental properties. In particular, we show that the certain answers to a $\dat$ program can be computed in polynomial time (in terms of data complexity), and that every union of conjunctive queries with at most one inequality or negated relational atom per disjunct, can be efficiently rewritten as a $\dat$ program in the context of data exchange. Furthermore, we show that this is also the case for a syntactic restriction of the class of unions of conjunctive queries with at most two inequalities per disjunct. This syntactic restriction is given by two conditions that are optimal, in the sense that computing certain answers becomes intractable if one removes any of them. Finally, we provide a thorough analysis of the combined complexity of computing certain answers to $\dat$ programs and other related query languages. In particular, we show that this problem is $\exptime$-complete for $\dat$, even if one restricts to conjunctive queries with single inequalities, which is a fragment of $\dat$ by the result mentioned above. Furthermore, we show that the combined complexity is $\conexptime$-complete for the case of conjunctive queries with $k$ inequalities, for every $k \geq 2$. |
| Pages | 73-83 |
| Conference name | International Conference on Database Theory |
| Publisher | ACM Press (New York, NY, USA) |
| Reference URL |
|