×

Decomposing constraint satisfaction problems using database techniques. (English) Zbl 0803.68090

Summary: There is a very close relationship between constraint satisfaction problems and the satisfaction of join-dependencies in a relational database which is due to a common underlying structure, namely a hypergraph. By making that relationship explicit we are able to adapt techniques previously developed for the study of relational databases to obtain new results for constraint satisfaction problems. In particular, we prove that a constraint satisfaction problem may be decomposed into a number of subproblems precisely when the corresponding hypergraph satisfies a simple condition. We show that combining this decomposition approach with existing algorithms can lead to a significant improvement in efficiency.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
68P15 Database theory
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beeri, C.; Fagin, R.; Maier, D.; Mendelzon, A. O.; Ullman, J. D.; Yannakakis, M., Properties of acyclic database schemes, (Proceedings 13th Annual ACM Symposium on the Theory of Computing (1981)), 355-362
[2] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 479-513 (1983) · Zbl 0624.68087
[3] Berge, C., (Graphs and Hypergraphs (1976), North-Holland: North-Holland New York) · Zbl 0483.05029
[4] Bibel, W., Constraint satisfaction from a deductive viewpoint, Artif. Intell., 35, 401-413 (1988) · Zbl 0645.68112
[5] Codd, E. F., A relational model of data for large shared databanks, Commun. ACM, 13, 377-387 (1970) · Zbl 0207.18003
[6] Dechter, R., Decomposing a relation into a tree of binary relations, J. Comput. Syst. Sci., 41, 2-24 (1990) · Zbl 0694.68019
[7] Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artif. Intell., 34, 1-38 (1988) · Zbl 0643.68156
[8] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. Intell., 38, 353-366 (1989) · Zbl 0665.68084
[9] Dincbas, M.; Simonis, H.; Van Hentenryck, P., Solving a stock cutting problem in constraint logic programming, (Logic Programming: Proceeding Fifth International Conference and Symposium (1988), MIT Press: MIT Press Cambridge, MA), 42-58 · Zbl 0800.68287
[10] Fagin, R., Degrees of acyclicity for hypergraphs and relational database schemes, J. ACM, 30, 514-550 (1983) · Zbl 0624.68088
[11] Fagin, R.; Mendelzon, A. O.; Ullman, J. D., A simplified universal relation assumption and its properties, ACM Trans. Database Syst., 7, 343-360 (1982) · Zbl 0488.68069
[12] Freuder, E. C., Synthesising constraint expressions, Commun. ACM, 21, 958-966 (1978) · Zbl 0386.68065
[13] Freuder, E. C., A sufficient condition for backtrack-free search, J. ACM, 29, 24-32 (1982) · Zbl 0477.68063
[14] Freuder, E. C., A sufficient condition for backtrack-bounded search, J. ACM, 32, 755-761 (1985) · Zbl 0633.68096
[15] Grimson, W. E.L., The combinatorics of local constraints in model-based recognition and localization from sparse data, J. ACM, 33, 658-686 (1986)
[16] Grimson, W. E.L., The combinatorics of object recognition in cluttered environments using constrained search, Artif. Intell., 44, 121-165 (1990) · Zbl 0717.68084
[17] Gyssens, M., On the complexity of join dependencies, ACM Trans. Database Syst., 11, 81-108 (1986) · Zbl 0602.68097
[18] Gyssens, M.; Paredaens, J., A decomposition methodology for cyclic databases, (Advances in Database Theory, 2 (1984), Plenum Press: Plenum Press New York), 85-122
[19] Gyssens, M.; Paredaens, J., On the decomposition of join dependencies, (Proceedings Third Conference on Principles of Database Systems. Proceedings Third Conference on Principles of Database Systems, Waterloo, Ont. (1984)), 143-152
[20] Haralick, R. M.; Shapiro, L. G., The consistent labeling problem, IEEE Trans. Pattern Anal. Mach. Intell., 1, 173-184 (1979), Part I · Zbl 0418.68080
[21] Discrete Appl. Math., 47, 33-46 (1993) · Zbl 0792.05054
[22] Mackworth, A. K., Consistency in networks of relations, Artif. Intell., 8, 99-118 (1977) · Zbl 0341.68061
[23] Maier, D., (The Theory of Relational Databases (1983), Computer Science Press: Computer Science Press Rockville, MD) · Zbl 0519.68082
[24] Miller, L. L., Generating hinges from arbitrary subhypergraphs, Inf. Process. Lett., 41, 307-312 (1992) · Zbl 0764.68033
[25] Miller, L. L.; Leuchner, J. H.; Kothari, S.; Liu, K. C., Testing arbitrary subhypergraphs for the lossless join property, Inf. Sci., 51, 95-110 (1990) · Zbl 0706.68042
[26] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inf. Sci., 7, 95-132 (1974) · Zbl 0284.68074
[27] Paredaens, J.; De Bra, P.; Gyssens, M.; Van Gucht, D., The Relational Database Model, (EATCS Monographs on Computer Science, 17 (1989), Springer: Springer Berlin) · Zbl 0669.68060
[28] Rissanen, J., Theory of joins for relational databases—a tutorial survey, (Proceedings Seventh Symposium on Mathematical Foundations of Computer Science. Proceedings Seventh Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 64 (1978), Springer: Springer Berlin), 537-551
[29] Seidel, R., A new method for solving constraint satisfaction problems, (Proceedings IJCAI-81. Proceedings IJCAI-81, Vancouver, BC (1981)), 338-342
[30] Tarjan, R. E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 566-579 (1984) · Zbl 0545.68062
[31] Ullman, J. D., (Principles of Database and Knowledge Base Systems, Vol. 1 (1988), Computer Science Press: Computer Science Press Rockville, MD)
[32] Ullman, J. D., (Principles of Database and Knowledge Base Systems, Vol. 2 (1989), Computer Science Press: Computer Science Press Rockville, MD)
[33] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 77-79 (1981) · Zbl 0496.68033
[34] Zhang, Y.; Mackworth, A. K., Parallel and distributed algorithms for finite constraint satisfaction problems, (Proceedings Third IEEE Symposium on Parallel and Distributed Computing. Proceedings Third IEEE Symposium on Parallel and Distributed Computing, Dallas, TX (1991)), 394-397
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.