×

zbMATH — the first resource for mathematics

Local and global relational consistency. (English) Zbl 0902.68043
Summary: Local consistency has proven to be an important concept in the theory and practice of constraint networks. In this paper, we present a new definition of local consistency, called relational consistency. The new definition is relation-based, in contrast with the previous definition of local consistency, which we characterize as variable-based. We show the conceptual power of the new definition by showing how it unifies known elimination operators such as resolution in theorem proving, joins in relational databases, and variable elimination for solving linear inequalities. Algorithms for enforcing various levels of relational consistency are introduced and analyzed. We also show the usefulness of the new definition in characterizing relationships between properties of constraint networks and the level of local consistency needed to ensure global consistency.

MSC:
68P15 Database theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability —a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018
[2] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding an embedding in k-trees, SIAM J. algebraic discrete methods, 8, 177-184, (1987)
[3] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete appl. math., 23, 11-24, (1989) · Zbl 0666.68067
[4] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 479-513, (1983) · Zbl 0624.68087
[5] Bertele, U.; Brioschi, F., Nonserial dynamic programming, (1972), Academic Press New York · Zbl 0187.17801
[6] Cooper, M.C., An optimal k-consistency algorithm, Artif. intell., 41, 89-95, (1989) · Zbl 0678.68058
[7] Cooper, M.C.; Cohen, D.A.; Jeavons, P.G., Characterizing tractable constraints, Artif. intell., 65, 347-361, (1994) · Zbl 0803.68053
[8] Davis, M.; Putnam, H., A computing procedure for quantification theory, J. ACM, 7, 201-215, (1960) · Zbl 0212.34203
[9] Dechter, R., Enhancement schemes for constraint processing incorporating, backjumping, learning and cutset decomposition, Artif. intell., 41, 273-312, (1990)
[10] Dechter, R., From local to global consistency, Artif. intell., 55, 87-107, (1992) · Zbl 0762.68053
[11] Dechter, R., Bucket elimination: a unifying framework for probabilistic inference, () · Zbl 0910.68209
[12] Dechter, R., Topological properties of time-space tradeoff, () · Zbl 0969.68149
[13] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artif. intell., 49, 61-95, (1991) · Zbl 0737.68070
[14] Dechter, R.; Pearl, J., Network-based heuristics for constraint satisfaction problems, Artif. intell., 34, 1-38, (1988) · Zbl 0643.68156
[15] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. intell., 38, 353-366, (1989) · Zbl 0665.68084
[16] Dechter, R.; Pearl, J., Directed constraint networks: a relational framework for causal modeling, (), 1164-1170 · Zbl 0761.68087
[17] Dechter, R.; Rish, I., Directional resolution: the Davis-Putnam procedure, revisited, (), 134-145
[18] Freuder, E.C., Synthesizing constraint expressions, Comm. ACM, 21, 958-966, (1978) · Zbl 0386.68065
[19] Freuder, E.C., A sufficient condition for backtrack-free search, J. ACM, 29, 24-32, (1982) · Zbl 0477.68063
[20] Ginsberg, M.L.; Frank, M.; Halpin, M.P.; Torrance, M.C., Search lessons learned from crossword puzzles, (), 210-215
[21] Goldin, D.Q.; Kanellakis, P.C., Constraint query algebras, (), 1-41
[22] Hochbaum, D.S.; Naor, J., Simple and fast algorithms for linear integer programs with two variables per inequality, SIAM J. comput., 23, 6, 1179-1192, (1994) · Zbl 0831.90089
[23] Jégou, P., On the consistency of general constraint satisfaction problems, (), 114-119
[24] Kanellakis, P., (), Ch. 7
[25] Kanellakis, P.C.; Kuper, G.M.; Revesz, P.Z., Constraint query languages, (), 299-313
[26] Kirousis, L.M., Fast parallel constraint satisfaction, Artif. intell., 64, 147-160, (1993) · Zbl 0787.68091
[27] Lagarias, J.C., The computational complexity of simultaneous Diophantine approximation problems, SIAM J. comput., 14, 1, 196-209, (1985) · Zbl 0563.10025
[28] Lassez, J.-L.; Mahler, M., On Fourier’s algorithm for linear constraints, J. autom. reasoning, 9, (1992)
[29] Mackworth, A.K., Consistency in networks of relations, Artif. intell., 8, 99-118, (1977) · Zbl 0341.68061
[30] Mackworth, A.K., On Reading sketch maps, (), 587-606
[31] Mackworth, A.K.; Freuder, E.C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artif. intell., 25, 65-74, (1985)
[32] Maier, D., The theory of relational databases, (1983), Computer Science Press Rockville, MD · Zbl 0519.68082
[33] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inform. sci., 7, 95-132, (1974) · Zbl 0284.68074
[34] Ullman, J.D., ()
[35] van Beek, P., On the minimality and decomposability of constraint networks, (), 447-452
[36] van Beek, P., On the inherent level of local consistency in constraint networks, (), 368-373
[37] van Beek, P.; Dechter, R., Constraint tightness versus global consistency, (), 572-582
[38] van Beek, P.; Dechter, R., On the minimality and global consistency of row-convex constraint networks, J. ACM, 42, 543-561, (1995) · Zbl 0885.68087
[39] Van Hentenryck, P.; Deville, Y.; Teng, C.-M., A generic arc consistency algorithm and its specializations, Artif. intell., 57, 291-321, (1992) · Zbl 0763.68059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.