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: 2501
Venue: SIGMOD
Year: 1989
Pagerank: 5.9274711e-05
Overall Rank: 6,282 | 56.91%
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,456	WATCHMAN: A Data Warehouse Intelligent Cache Manager	1996	VLDB	8.5526697e-05
5,402	Temporal Query Processing and Optimization in Multiprocessor Database Machines	1992	VLDB	6.2310833e-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.00047309646
539	Computing Queries from Derived Relations	1985	VLDB	0.00016872223
583	Global Query Optimization	1986	SIGMOD	0.00016145442
1,361	Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates	1986	VLDB	0.00011037801
2,855	Horizontal Data Partitioning In Database Design	1982	SIGMOD	8.0323779e-05
8,220	Fragments Of Relations	1983	SIGMOD	5.4641029e-05

Semantically Similar Papers

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