Query languages for data exchange: beyond unions of conjunctive queries

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 Datalog program can also can be computed in polynomial time. The problem is that both UCQ and Datalog do not allow negated atoms, as adding an unrestricted form of negation to these languages yields to intractability.

In this paper, we propose a language called Datalog^C(≠) that extends Datalog with a restricted form of negation, and study some of its fundamental properties. In particular, we show that the certain answers to a Datalog^C(≠) 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 Datalog^C(≠) 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 Datalog^C(≠) programs and other related query languages. In particular, we show that this problem is Exptime-complete for Datalog^C(≠), even if one restricts to conjunctive queries with single inequalities, which is a fragment of Datalog^C(≠) 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 ≥ 2.

REFERENCES

• 1: S. Abiteboul, and O. Duschka. Answering queries using materialized views. Gemo report 383.
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: Foto Afrati , Chen Li , Vassia Pavlaki, Data exchange in the presence of arithmetic comparisons, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353403]
• 4: Marcelo Arenas , Pablo Barceló , Ronald Fagin , Leonid Libkin, Locally consistent transformations and query answering in data exchange, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055592]
• 5: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 6: Alin Deutsch , Alan Nash , Jeff Remmel, The chase revisited, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376938]
• 7: Ronald Fagin , Phokion G. Kolaitis , Wang-Chiew Tan , Lucian Popa, Composing schema mappings: second-order dependencies to the rescue, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055572]
• 8: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 9: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, ACM Transactions on Database Systems (TODS), v.30 n.1, p.174-210, March 2005 [doi>10.1145/1061318.1061323]
• 10: Georg Gottlob , Christos Papadimitriou, On the complexity of single-rule datalog queries, Information and Computation, v.183 n.1, p.104-122, May 25, 2003 [doi>10.1016/S0890-5401(03)00012-9]
• 11: Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065176]
• 12: Phokion G. Kolaitis , Jonathan Panttaja , Wang-Chiew Tan, The complexity of data exchange, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142357]
• 13: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 14: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 15: Leonid Libkin, Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series), SpringerVerlag, 2004
• 16: Leonid Libkin, Data exchange and incomplete information, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142360]
• 17: Leonid Libkin , Cristina Sirangelo, Data exchange and schema mappings in open and closed worlds, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376937]
• 18: Aleksander Madry, Data exchange: on the complexity of answering queries with inequalities, Information Processing Letters, v.94 n.6, p.253-257, 30 June 2005 [doi>10.1016/j.ipl.2005.03.001]
• 19: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]