Data exchange in the presence of arithmetic comparisons

ABSTRACT

Data exchange is the problem of transforming data structured under a schema (called source) into data structured under a different schema (called target). The emphasis of data exchange is to materialize a target instance (called solution) that satisfies the relationship between the schemas. Universal solutions were shown to be the most suitable solutions, mainly because they can be used to answer conjunctive queries posed over the target schema. Trying to extend this result to more expressive query languages fails, even if we only add inequalities (≠) to conjunctive queries.

In this work we study data exchange in the presence of general arithmetic comparisons (<, ≤, >, ≥, =, ≠): (a) We consider queries posed over the target schema that belong to the class of unions of conjunctive queries with arithmetic comparisons (in short CQACs). (b) We exploit arithmetic comparisons to define more expressive data exchange settings, called DEAC settings. In particular, DEAC settings consist of constraints that involve arithmetic comparisons. For that, two new classes of dependencies (tgd-ACs and acgds) are introduced, to capture the need of arithmetic comparisons in source-to-target and target constraints.

We show that in DEAC settings the existence of solution problem is in NP. We define a novel chase procedure called AC-chase which is a tree and we prove that it produces a universal solution (appropriately defined to deal with arithmetic comparisons). We show that the new concept of universal solution is the right tool for query answering in the case of unions of CQACs. The complexity of computing certain answers for unions of CQACs is shown to be coNP-complete. Moreover, we identify polynomial cases for a) computing a universal solution and b) computing certain answers. For that, we introduce the succinct AC-chase which is a sequence instead of a tree, but its result is not necessarily a solution. We identify cases where succinct AC-chase returns indeed a universal solution and we investigate the syntactic conditions of the query under which query answering takes polynomial time. We show that the latter is feasible even in cases where the result of chase is not a universal solution.

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: F. Afrati, C. Li, and P. Mitra. On containment of conjunctive queries with arithmetic comparisons. In EDBT, 2004.
• 3: Foto Afrati , Chen Li , Prasenjit Mitra, Rewriting queries using views in the presence of arithmetic comparisons, Theoretical Computer Science, v.368 n.1-2, p.88-123, December, 2006 [doi>10.1016/j.tcs.2006.08.020]
• 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: Marcelo Arenas , Leonid Libkin, XML data exchange: consistency and query answering, 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.1065171]
• 6: Marianne Baudinet , Jan Chomicki , Pierre Wolper, Constraint-generating dependencies, Journal of Computer and System Sciences, v.59 n.1, p.94-115, Aug. 1999 [doi>10.1006/jcss.1999.1632]
• 7: C. Beeri and M. Y. Vardi. Formal systems for tuple and equality generating dependencies. SIAM J. on Computing, 13(1):76--98, 1984.
• 8: 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]
• 9: P. A. Bernstein. Generic model management: A database infrastructure for schema manipulation. In IDM 2003 Workshop, 2003.
• 10: P. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. Conditional functional dependencies for data cleaning. In ICDE, 2007.
• 11: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 12: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 13: 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]
• 14: 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]
• 15: 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]
• 16: Georg Gottlob, Computing cores for data exchange: new algorithms and practical solutions, 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.1065187]
• 17: Georg Gottlob , Alan Nash, Data exchange: computing cores in polynomial time, 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.1142358]
• 18: G. Grahne, Problem of Incomplete Information in Relational Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 19: Ashish Gupta, Partial information based integrity constraint checking, Stanford University, Stanford, CA, 1995
• 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: Naci Ishakbeyoglu , Z. Meral Özsoyoglu, On the Maintenance of Implication Integrity Constraints, Proceedings of the 4th International Conference on Database and Expert Systems Applications, p.221-232, September 06-08, 1993
• 22: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 23: 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]
• 24: 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]
• 25: 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]
• 26: Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman, Answering queries using limited external query processors (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-237, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237716]
• 27: 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]
• 28: 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]
• 29: Michael J. Maher, Constrained dependencies, Theoretical Computer Science, v.173 n.1, p.113-149, Feb. 1997 [doi>10.1016/S0304-3975(96)00193-4]
• 30: Michael J. Maher , Divesh Srivastava, Chasing constrained tuple-generating dependencies, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.128-138, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237693]
• 31: 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]
• 32: R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]
• 33: Ron van der Meyden, Logical approaches to incomplete information: a survey, Logics for databases and information systems, Kluwer Academic Publishers, Norwell, MA, 1998
• 34: Renée J. Miller , Laura M. Haas , Mauricio A. Hernández, Schema Mapping as Query Discovery, Proceedings of the 26th International Conference on Very Large Data Bases, p.77-88, September 10-14, 2000
• 35: Lucian Popa , Yannis Velegrakis , Mauricio A. Hernández , Renée J. Miller , Ronald Fagin, Translating web data, Proceedings of the 28th international conference on Very Large Data Bases, p.598-609, August 20-23, 2002, Hong Kong, China
• 36: 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]
• 37: A. Vieilleribiere and M. D. Rougemont. Approximate data exchange. In ICDT, 2007.
• 38: Junhu Wang , Rodney W. Topor , Michael J. Maher, Reasoning with Disjunctive Constrained Tuple-Generating Dependencies, Proceedings of the 12th International Conference on Database and Expert Systems Applications, p.963-973, September 03-05, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema