Abstract
In this paper we investigate which constraints may be derived from a given set of constraints. We show that, given a set of relations \(\mathcal{R}\), all of which are invariant under some set of permutations P, it is possible to derive any other relation which is invariant under P, using only the projection, Cartesian product, and selection operators, together with the effective domain of \(\mathcal{R}\), provided that the effective domain contains at least three elements. Furthermore, we show that the condition imposed on the effective domain cannot be removed. This result sharpens an earlier result of Paredaens [13], in that the union operator turns out to be superfluous. In the context of constraint satisfaction problems, this result shows that a constraint may be derived from a given set of constraints containing the binary disequality constraint if and only if it is closed under the same permutations as the given set of constraints.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Bancilhon. On the completeness of query languages for relational data bases. In Proceedings 7th International Symposium on Mathematical Foundations of Computer Science (Zakopane, Poland), Lecture Notes in Computer Science, 64, Springer-Verlag, Berlin/New York, 1978, pp. 112–123.
W. Bibel. Constraint satisfaction from a deductive viewpoint. Artificial Intelligence, 35, 1988, pp. 401–413.
D. Cohen, P. Jeavons, M. Gyssens. Derivation of constraints and database relations. Technical Report CSD-TR-96-01, Royal Holloway, Univ. of London, January 1996.
R. Dechter. Decomposing a relation into a tree of binary relations. Journal of Computer and System Sciences, 41, 1990, pp. 2–24.
E.C. Freuder. A sufficient condition for backtrack-bounded search. Journal of the ACM, 32, 1985, pp. 755–761.
M. Gyssens, P.G. Jeavons, and D.A. Cohen. Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence, 66, 1994, pp. 57–89.
R.M. Haralick and L.G. Shapiro. The consistent labeling problem: Part I. IEEE Trans. Pattern. Anal. Mach. Intell., 1, 1979, pp. 173–184.
P.G. Jeavons. On the algebraic structure of combinatorial problems. Technical Report CSD-TR-95-15, Royal Holloway, Univ. of London, October 1995.
P. Jeavons, D. Cohen, and M. Gyssens. A structural decomposition for hypergraphs. In Proceedings Jerusalem Combinatorics '93, H. Barcelo and G. Kalai, eds. Contemporary Mathematics, 178, 1994, pp. 161–177.
P. Jeavons, D. Cohen, and M. Gyssens. A unifying framework for tractable constraints. In Proceedings CP '95, Lecture Notes in Computer Science, 976, Springer-Verlag, Berlin/New York, 1995, pp. 276–291.
A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8, 1977, pp. 99–118.
U. Montanari. Networks of constraints: fundamental properties and applications to picture processing. Information Sciences, 7, 1974, pp. 95–132.
J. Paredaens. On the expressive power of the relational algebra. Information Processing Letters, 7:2, 1978, pp. 107–111.
J.D. Ullman. Principles of Database and Knowledge Base Systems, Vols. I and II. Computer Science Press, Rockville, Maryland, 1988 and 1989.
Y. Zhang and A.K. Mackworth. Parallel and distributed algorithms for finite constraint satisfaction problems. In Proceedings 3rd IEEE Symposium on Parallel and Distributed Computing (Dallas, Texas), 1991, pp. 394–397.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cohen, D., Gyssens, M., Jeavons, P. (1996). Derivation of constraints and database relations. In: Freuder, E.C. (eds) Principles and Practice of Constraint Programming — CP96. CP 1996. Lecture Notes in Computer Science, vol 1118. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61551-2_71
Download citation
DOI: https://doi.org/10.1007/3-540-61551-2_71
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61551-4
Online ISBN: 978-3-540-70620-5
eBook Packages: Springer Book Archive