Solving Implication Problems in Database Applications

Summary: Graph/SAT framing of the implication problem for derived DB relations, relevant to query derivation, view maintenance, and optimization. General problem NP-hard with all six operators and both conjunctions and disjunctions; polynomial-time algorithm for restricted case (no != in Q, no disjunction in T); analyzes # and disjunctions, giving necessary conditions to detect tractable instances for heuristics. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf7878d042cda9180
Venue: SIGMOD
Year: 1989
Pagerank: 5.7949204e-05
Overall Rank: 6,406 | 56.94%
DOI: 10.1145/67544.66943

Incoming Non-self Citations Over Time

Authors

1. Xian-He Sun (Michigan State University)
2. Nabil Kamel (Michigan State University)
3. Lionel M. Ni (Michigan State University)

BibTeX Citation

@inproceedings{sun_sigmod89,
        title = {{Solving Implication Problems in Database Applications}},
        author = {Sun, Xian-He and Kamel, Nabil and Ni, Lionel M.},
        series = {{SIGMOD} '89},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/67544.66943},
        url = {https://dl.acm.org/doi/10.1145/67544.66943},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,511	WATCHMAN: A Data Warehouse Intelligent Cache Manager	1996	VLDB	8.3696476e-05
5,538	Temporal Query Processing and Optimization in Multiprocessor Database Machines	1992	VLDB	6.0918672e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.00046602544
551	Computing Queries from Derived Relations	1985	VLDB	0.000165527
592	Global Query Optimization	1986	SIGMOD	0.00015841026
1,393	Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates	1986	VLDB	0.00010805324
2,811	Horizontal Data Partitioning In Database Design	1982	SIGMOD	7.9818853e-05
8,387	Fragments Of Relations	1983	SIGMOD	5.341531e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,383	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB
2	8,015	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
3	6,195	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
4	10,357	On the Vexing Difficulty of Evaluating IN Predicates	2026	CIDR
5	7,141	Tree-Width and Functional Dependencies in Databases	2008	PODS
6	1,503	The Complexity of Evaluating Relational Queries	1983	PODS
7	2,098	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
8	3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
9	1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
10	8,053	Polynomial-time program transformations in deductive databases	1990	PODS