ComputingComputer ScienceAlgorithmsData StructuresDatabasesConstraint SatisfactionData Structure AlgorithmsDatabase DesignDependency ParsingRelational AlgebraRelational Data ModelConstraintsDecompositionsHypergraph DecompositionsIntegrity ConstraintsSchema Mapping
Data Exchange is the problem of inserting data structured under a source schema into a target schema of different structure (possibly with integrity constraints), while reflecting the source data as accurately as possible. We study computational issues related to data exchange in the setting of Fagin, Kolaitis, and Popa(PODS'03). We use the technique of hypertree decompositions to derive improved algorithms for computing the core of a relational instance with labeled nulls, a problem we show to be fixed-parameter intractable with respect to the block size of the input instances. We show that computing the core of a data exchange problem is tractable for two large and useful classes of target constraints. The first class includes functional dependencies and weakly acyclic inclusion dependencies. The second class consists of full tuple generating dependencies and arbitrary equation generating dependencies. Finally, we show that computing cores is NP-hard in presence of a system-predicate NULL(x), which is true iff x is a null value.
36
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
Principles of database and knowledge-base systems
Choice Reviews Online · 1989 · 2.7K citations
Maurizio Lenzerini · 2002 · 2.5K citations
Graph minors. II. Algorithmic aspects of tree-width
Neil Robertson, Paul Seymour · Journal of Algorithms · 1986 · 1.5K citations
Optimal implementation of conjunctive queries in relational data bases
Ashok K. Chandra, Philip M. Merlin · 1977 · 1.2K citations · Full text