TY - GEN
T1 - Constraint-generating dependencies
AU - Baudinet, Marianne
AU - Chomicki, Jan
AU - Wolper, Pierre
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1994.
PY - 1994
Y1 - 1994
N2 - Traditionally, dependency theory has been developed for uninterpreted data. Specifically, the only assumption that is made about the data domains is that data. values can be compared for equality. However, data is often interpreted and there can be advantages in considering it as such, for instance obtaining more compact representations as done in constraint databases. This paper considers dependency theory in the context of interpreted data. Specifically, it studies constraint-generating dependencies. These are a generalization of equality-generating dependencies where equality requirements are replaced by constraints on an interpreted domain. The main technical results in the paper are decision procedures for the implication and consistency problems for constraintgenerating dependencies. These decision procedures proceed by reducing the dependency problem to a decision problem for the constraint theory of interest, and are applicable as soon as the underlying constraint theory is decidable. Furthermore, complexity results for specific constraint domains can be transferred quite directly to the dependency problem.
AB - Traditionally, dependency theory has been developed for uninterpreted data. Specifically, the only assumption that is made about the data domains is that data. values can be compared for equality. However, data is often interpreted and there can be advantages in considering it as such, for instance obtaining more compact representations as done in constraint databases. This paper considers dependency theory in the context of interpreted data. Specifically, it studies constraint-generating dependencies. These are a generalization of equality-generating dependencies where equality requirements are replaced by constraints on an interpreted domain. The main technical results in the paper are decision procedures for the implication and consistency problems for constraintgenerating dependencies. These decision procedures proceed by reducing the dependency problem to a decision problem for the constraint theory of interest, and are applicable as soon as the underlying constraint theory is decidable. Furthermore, complexity results for specific constraint domains can be transferred quite directly to the dependency problem.
UR - https://www.scopus.com/pages/publications/85028701200
U2 - 10.1007/3-540-58601-6_102
DO - 10.1007/3-540-58601-6_102
M3 - Conference contribution
AN - SCOPUS:85028701200
SN - 9783540586012
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 205
EP - 217
BT - Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings
A2 - Borning, Alan
PB - Springer Verlag
T2 - 2nd International Workshop on the Principles and Practice of Constraint Programming, PPCP 1994
Y2 - 2 May 1994 through 4 May 1994
ER -