Data Exchange, Data Integration, and Chase
Skip to main content
Open Access Publications from the University of California

Data Exchange, Data Integration, and Chase


We study the problem of computing certain answers to a query over a target schema for a source instance under constraints which relate the source and target schemas. Prior work has shown that, for restricted constraints (source-to-target and target-to-target embedded dependencies) and unions of conjunctive queries, there is a special instance, known as a universal solution, such that running the query on it essentially yields the certain answers. Such a universal solution does not always exist for even slight extensions of these classes of constraints and queries. We show that there may be a finite set of instances, which we call a universal set solution, which suffices to compute the certain answers. We also introduce the notion of a k-universal set solution, which is sufficient to compute the certain answers to queries with at most k variables, even when no universal set solution exists. We show how to compute such universal and k-universal set solutions for universal-existential constraints and existential queries. The main algorithm for computing the universal set solution is an extended chase. We provide a completeness result for this chase and sufficient conditions for termination, which strictly extend the best previously known conditions (such as weak acyclicity). We also introduce a new kind of chase to compute k-universal set solutions.

Pre-2018 CSE ID: CS2006-0859

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View