Constraint Satisfaction and Database Theory: a Tutorial

Summary: Tutorial that recasts CSPs as conjunctive queries/homomorphisms and vice versa, formalizing the intimate CSP–database correspondence. Draws consequences for tractability and algorithms—structural and algebraic restrictions, query evaluation and join-based techniques—from both perspectives. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1196
Venue: PODS
Year: 2000
Pagerank: 5.9287393e-05
Overall Rank: 6,278 | 56.93%
DOI: 10.1145/335168.335209

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi (Rice University)

BibTeX Citation

@inproceedings{vardi_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Constraint Satisfaction and Database Theory: a Tutorial}},
        url = {https://dl.acm.org/doi/10.1145/335168.335209},
        doi = {10.1145/335168.335209},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vardi, Moshe Y.},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,678	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.2680182e-05
11,140	Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity	2024	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
298	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00022138018
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
515	Answering Recursive Queries Using Views	1997	PODS	0.00017177428
763	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00014230134
1,302	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00011238375
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.1434045e-05
2,330	Hypertree Decompositions and Tractable Queries	1999	PODS	8.7447066e-05
3,103	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.7562264e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,986	Combinatorial Games in Database Theory	1995	PODS
2	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
3	5,046	Toward Practical Constraint Databases	1993	VLDB
4	9,029	On the Satisfiability of Dependency Constraints in Entity-Relationship Schemata	1987	VLDB
5	5,340	Machine Learning for Databases	2021	VLDB
6	1,489	Constraint Checking with Partial Information	1994	PODS
7	8,506	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB
8	889	Constraint Programming and Database Languages: A Tutorial	1995	PODS
9	9,755	Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction	2021	PODS
10	382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS