TY - GEN
T1 - Data exchange in datalog is mainly a matter of choice
AU - Saccà, Domenico
AU - Serra, Edoardo
PY - 2012
Y1 - 2012
N2 - Data exchange is the problem of migrating a data instance from a source schema to a target schema such that the materialized data on the target schema satisfies the integrity constraints specified by: TGDs (Tuple Generating Dependencies), which are universal quantified formulas with additional existential quantifiers, and EGDs (Equality Generating Dependencies), which are universal quantified formulas enforcing the equality of two variables. This paper presents a formulation of the data exchange problem using DATALOG with choice, which is a non deterministic construct based on stable model semantics. TGDs are represented by rules and a choice predicate is used to non-deterministically select values for the existential variables. Every EGD can be naturally represented by a goal rule. However, as in general it expresses a functional dependency, in this case the goal rule can be replaced by a choice predicate defining the functional dependency inside one of TGD rules. Although classical certainty semantics for query answering in a data exchange setting can be also defined for DATALOG with choice, this paper explores another direction: searching for a solution for which a number of given "sensible" queries have uncertainty-guaranteed answers. The paper discusses properties of privacy-preserving data exchange and illustrates its complexity. Finally, EGDs are extended to express count constraints (e.g, an employee may manage at most k departments instead of only one) and the choice construct is therefore extended to implement count constraints. The resulting setting can be used to define the exchange of aggregate data.
AB - Data exchange is the problem of migrating a data instance from a source schema to a target schema such that the materialized data on the target schema satisfies the integrity constraints specified by: TGDs (Tuple Generating Dependencies), which are universal quantified formulas with additional existential quantifiers, and EGDs (Equality Generating Dependencies), which are universal quantified formulas enforcing the equality of two variables. This paper presents a formulation of the data exchange problem using DATALOG with choice, which is a non deterministic construct based on stable model semantics. TGDs are represented by rules and a choice predicate is used to non-deterministically select values for the existential variables. Every EGD can be naturally represented by a goal rule. However, as in general it expresses a functional dependency, in this case the goal rule can be replaced by a choice predicate defining the functional dependency inside one of TGD rules. Although classical certainty semantics for query answering in a data exchange setting can be also defined for DATALOG with choice, this paper explores another direction: searching for a solution for which a number of given "sensible" queries have uncertainty-guaranteed answers. The paper discusses properties of privacy-preserving data exchange and illustrates its complexity. Finally, EGDs are extended to express count constraints (e.g, an employee may manage at most k departments instead of only one) and the choice construct is therefore extended to implement count constraints. The resulting setting can be used to define the exchange of aggregate data.
KW - Aggregate Terms
KW - Choice
KW - Data Exchange
KW - Datalog
KW - Nondeterminism
KW - Privacy
UR - http://www.scopus.com/inward/record.url?scp=84867134057&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32925-8_16
DO - 10.1007/978-3-642-32925-8_16
M3 - Conference contribution
AN - SCOPUS:84867134057
SN - 9783642329241
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 153
EP - 164
BT - Datalog in Academia and Industry - Second International Workshop, Datalog 2.0, Proceedings
T2 - 2nd International Workshop on Datalog in Academia and Industry, Datalog 2.0
Y2 - 11 September 2012 through 13 September 2012
ER -