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: 1197
Venue: PODS
Year: 2000
Pagerank: 5.7881576e-05
Overall Rank: 4,977 | 65.38%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
10,919	Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity	2024	PODS	4.1945683e-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
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054402763
114	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046339735
291	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00028831632
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028596715
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
532	Answering Recursive Queries Using Views	1997	PODS	0.00020778506
602	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00019352415
1,081	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00014216794
2,327	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.0276061e-05
2,342	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.0015589e-05
2,796	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1112658e-05
3,228	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.3405281e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,792	Combinatorial Games in Database Theory	1995	PODS	4.1945683e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9164359e-05
8,871	On The Satisfiability Of Dependency Constraints In Entity-Relationship Schemata	1987	VLDB	4.431665e-05
5,861	Machine Learning for Databases	2021	VLDB	5.298883e-05
1,578	Constraint Checking with Partial Information	1994	PODS	0.00011284233
8,269	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB	4.5455963e-05
620	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00019005954
9,627	Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction	2021	PODS	4.3146507e-05
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562