Foto Afrati
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.
- S. Abiteboul and O. M. Duschka. Complexity of answering queries using materialized views. In PODS, 1998. Google Scholar
Digital Library
- F. Afrati, C. Li, and P. Mitra. On containment of conjunctive queries with arithmetic comparisons. In EDBT, 2004.Google ScholarCross Ref
- F. Afrati, C. Li, and P. Mitra. Rewriting queries using views in the presence of arithmetic comparisons. TCS, 368(1--2):88--123, 2006. Google ScholarDigital Library
- M. Arenas, P. Barcel, R. Fagin, and L. Libkin. Locally consistent transformations and query answering in data exchange. In PODS, 2004. Google ScholarDigital Library
- M. Arenas and L. Libkin. XML data exchange: Consistency and query answering. In PODS, 2005. Google ScholarDigital Library
- M. Baudinet, J. Chomicki, and P. Wolper. Constraint-generating dependencies. J. Comput. Syst. Sci., 59(1):94--115, 1999. Google ScholarDigital Library
- C. Beeri and M. Y. Vardi. Formal systems for tuple and equality generating dependencies. SIAM J. on Computing, 13(1):76--98, 1984.Google ScholarCross Ref
- C. Beeri and M. Y. Vardi. A proof procedure for data dependencies. J. ACM, 31(4):718--741, 1984. Google ScholarDigital Library
- P. A. Bernstein. Generic model management: A database infrastructure for schema manipulation. In IDM 2003 Workshop, 2003.Google Scholar
- P. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. Conditional functional dependencies for data cleaning. In ICDE, 2007.Google ScholarCross Ref
- A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational databases. In STOC, 1977. Google ScholarDigital Library
- A. Deutsch and V. Tannen. Reformulation of XML queries and constraints. In ICDT, 2003. Google ScholarDigital Library
- R. Fagin. Horn clauses and database dependencies. J. ACM, 29(4):952--985, 1982. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. In ICDT, 2003. Full version: TCS 336(1): 89--124, 2005. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, and L. Popa. Data exchange: Getting to the core. In PODS, 2003. Full version: ACM TODS 30(1): 174--210, 2005. Google ScholarDigital Library
- G. Gottlob. Computing cores for data exchange: New algorithms and practical solutions. In PODS, 2005. Google ScholarDigital Library
- G. Gottlob and A. Nash. Data exchange: Computing cores in polynomial time. In PODS, 2006. Google ScholarDigital Library
- G. Grahne. The problem of incomplete information in relational databases, volume 554. Spring-Verlag, Berlin, Lecture Notes in Computer Science, 1991. Google ScholarDigital Library
- A. Gupta. Partial Information Based Integrity Constraint Checking. PhD thesis, Stanford, 1994. Google ScholarDigital Library
- T. Imielinski and W. Lipski. Incomplete information in relational databases. J. ACM, 31(4):761--791, 1984. Google ScholarDigital Library
- N. Ishakbeyoglu and Z. M. Ozsoyoglu. On the maintenance of implication integrity constraints. In DEXA, 1993. Google ScholarDigital Library
- A. Klug. On conjunctive queries containing inequalities. J. ACM, 35(1):146--160, 1988. Google ScholarDigital Library
- P. G. Kolaitis. Schema Mappings, Data Exchange, and Metadata Management. In PODS, 2005. Google ScholarDigital Library
- P. G. Kolaitis, J. Panttaja, and W.-C. Tan. The complexity of data exchange. In PODS, 2006. Google ScholarDigital Library
- M. Lenzerini. Data integration: A theoretical perspective. In PODS, 2002. Google ScholarDigital Library
- A. Levy, A. Rajaraman, and J. Ullman. Answering queries using limited external query processors. In PODS, 1996. Google ScholarDigital Library
- L. Libkin. Data exchange and incomplete information. In PODS, 2006. Google ScholarDigital Library
- A. Madry. Data exchange: on complexity of answering queries with inequalities. Information Processing Letters, 94(6):253--257, 2005.Google ScholarDigital Library
- M. J. Maher. Constrained dependencies. Theoretical Computer Science, 173(1):113--149, 1997. Google ScholarDigital Library
- M. J. Maher and D. Srivastava. Chasing constrained tuple-generating dependencies. In PODS, 1996. Google ScholarDigital Library
- D. Maier, A. O. Mendelzon, and Y. Sagiv. Testing implications of data dependencies. ACM TODS, 4(4):455--469, 1979. Google ScholarDigital Library
- R. v. d. Meyden. The complexity of querying indefinite data about linearly ordered domains. In PODS, 1992. Google ScholarDigital Library
- R. v. d. Meyden. Logical approaches to incomplete information: A survey. In Logics for Databases and Information Systems, pages 307--356, 1998. Google ScholarDigital Library
- R. J. Miller, L. M. Haas, and M. Hernández. Schema mapping as query discovery. In VLDB, 2000. Google ScholarDigital Library
- L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernández, and R. Fagin. Translating web data. In VLDB, 2002. Google ScholarDigital Library
- N. C. Shu, B. C. Housel, R. W. Taylor, S. P. Ghosh, and V. Y. Lum. Express: A data EXtraction, processing, amd REStructuring System. ACM TODS, 2(2):134--174, 1977. Google ScholarDigital Library
- A. Vieilleribiere and M. D. Rougemont. Approximate data exchange. In ICDT, 2007. Google ScholarDigital Library
- J. Wang, R. W. Topor, and M. J. Maher. Reasoning with disjunctive constrained tuple-generating dependencies. In DEXA, 2001. Google ScholarDigital Library
Index Terms
- Data exchange in the presence of arithmetic comparisons
Recommendations
Data exchange with arithmetic operations
EDBT '13: Proceedings of the 16th International Conference on Extending Database TechnologyData exchange is the problem of transforming data structured under a source schema into data structured under a target schema, taking into account structural relationships between the two schemas, which are described by a schema mapping. Existing schema-...
Rewriting queries using views in the presence of arithmetic comparisons
We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. ...
XML data exchange: consistency and query answering
PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsData exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target. Theoretical foundations of data exchange have recently been ...
Comments