Locally consistent transformations and query answering in data exchange

ABSTRACT

Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema. Given a source instance, there may be many solutions - target instances that satisfy the constraints of the data exchange problem. Previous work has identified two classes of desirable solutions: canonical universal solutions, and their cores. Query answering in data exchange amounts to rewriting a query over the target schema to another query that, over a materialized target instance, gives the result that is semantically consistent with the source. A basic question is then whether there exists a transformation sending a source instance into a solution over which target queries can be answered.We show that the answer is negative for many data exchange transformations that have structural properties similar to canonical universal solutions and cores. Namely, we prove that many such transformations preserve the local structure of the data. Using this notion, we further show that every target query rewritable over such a transformation cannot distinguish tuples whose neighborhoods in the source are similar. This gives us a first tool that helps check whether a query is rewritable, We also show that these results are robust: they hold for an extension of relational calculus with grouping and aggregates, and for two different semantics of query answering.

REFERENCES

• 1: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Journal of the ACM (JACM), v.45 n.5, p.798-842, Sept. 1998 [doi>10.1145/290179.290182]
• 4: 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]
• 5: O. Duschka and A. Levy. Recursive plans for information gathering. In IJCAI 1997. pages 778--784.
• 6: H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer Verlag, 1995.
• 7: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 8: R. Fagin. Probabilities on finite models. Journal of Symbolic Logic 41(1), pages 50--58, 1976.
• 9: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 10: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.90-101, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773163]
• 11: Ronald Fagin , Larry J. Stockmeyer , Moshe Y. Vardi, On a monadic NP vs monadic co-NP, Information and Computation, v.120 n.1, p.78-92, July 1995 [doi>10.1006/inco.1995.1100]
• 12: H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium '81, North Holland, 1982.
• 13: Erich Grädel , Yuri Gurevich, Metafinite model theory, Information and Computation, v.140 n.1, p.26-81, Jan. 10, 1998 [doi>10.1006/inco.1997.2675]
• 14: Alon Y. Halevy, Theory of answering queries using views, ACM SIGMOD Record, v.29 n.4, p.40-47, Dec. 2000 [doi>10.1145/369275.369284]
• 15: W. Hanf. Model-theoretic methods in the study of elementary logic. In J. W. Addison et al. eds, The Theory of Models, North Holland. pages 132--145, 1965.
• 16: Pavol Hell , Jaroslav Nešetřil, The core of a graph, Discrete Mathematics, v.109 n.1-3, p.117-126, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90282-K]
• 17: Lauri Hella, Logical hierarchies in PTIME, Information and Computation, v.129 n.1, p.1-19, Aug. 25, 1996 [doi>10.1006/inco.1996.0070]
• 18: Lauri Hella , Leonid Libkin , Juha Nurmonen , Limsoon Wong, Logics with aggregate operators, Journal of the ACM (JACM), v.48 n.4, p.880-907, July 2001 [doi>10.1145/502090.502100]
• 19: Richard Hull , Masatoshi Yoshikawa, ILOG: Declarative Creation and Manipulation of Object Identifiers, Proceedings of the 16th International Conference on Very Large Data Bases, p.455-468, August 13-16, 1990
• 20: 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]
• 21: Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
• 22: K. Larsen. On grouping in relational algebra. International Journal of Foundations of Computer Science 10(3), pages 301--311. 1999.
• 23: 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]
• 24: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 25: Leonid Libkin, Logics with counting and local properties, ACM Transactions on Computational Logic (TOCL), v.1 n.1, p.33-59, July 2000 [doi>10.1145/343369.343376]
• 26: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 27: N. C. Shu , B. C. Housel , R. W. Taylor , S. P. Ghosh , V. Y. Lum, EXPRESS: a data EXtraction, Processing, and Restructuring System, ACM Transactions on Database Systems (TODS), v.2 n.2, p.134-174, June 1977 [doi>10.1145/320544.320549]
• 28: Jan Van Den Bussche , Dirk Van Gucht , Marc Andries , Marc Gyssens, On the completeness of object-creating database transformation languages, Journal of the ACM (JACM), v.44 n.2, p.272-319, March 1997 [doi>10.1145/256303.256311]