A Decision Procedure for Conjunctive Query Disjointness

Summary: Decides whether two conjunctive queries are always disjoint, resolving the view-recomputation-under-FDs problem; algorithm time is optimal unless directed reachability admits sublinear solutions. Key idea: combine FD and dense-order decision procedures via tableaux supporting <, <=, =, >=, >, !=. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 858
Venue: PODS
Year: 1989
Pagerank: 5.7885617e-05
Overall Rank: 6,731 | 53.83%
DOI: 10.1145/73721.73735

Incoming Non-self Citations Over Time

Authors

1. Charles Elkan (Cornell University)

BibTeX Citation

@inproceedings{elkan_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{A Decision Procedure for Conjunctive Query Disjointness}},
        url = {https://dl.acm.org/doi/10.1145/73721.73735},
        doi = {10.1145/73721.73735},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Elkan, Charles},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,314	Independence of Logic Database Queries and Updates	1990	PODS	0.00011182427
2,617	Chasing Constrained Tuple-Generating Dependencies	1996	PODS	8.3391085e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00047309646
539	Computing Queries from Derived Relations	1985	VLDB	0.00016872223
1,361	Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates	1986	VLDB	0.00011037801
4,351	The Complexity Of Testing Predicate Locks	1979	SIGMOD	6.7495011e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS
2	7,858	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
3	1,269	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
4	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
5	8,700	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB
6	13,129	Complexity of Query Processing in Databases with OR-Objects	1989	PODS
7	9,403	Materializing Views with Minimal Size To Answer Queries	2003	PODS
8	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
9	5,905	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS
10	3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS