Polynomial-time program transformations in deductive databases

Summary: Tight complexity dichotomy for k-containment of conjunctive queries: 2-containment in P, 3-containment NP-complete, so slight relaxations turn common program transformations NP-hard. Yields poly-time algorithms for restricted deductive-database transformations and characterizes complexity of sequencability/commutativity of linear rules, 1-boundedness in sirups, and ZYT-linearizability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 894
Venue: PODS
Year: 1990
Pagerank: 5.5225498e-05
Overall Rank: 7,886 | 45.90%
DOI: 10.1145/298514.298551

Incoming Non-self Citations Over Time

Authors

1. Yatin P. Saraiya (Stanford University)

BibTeX Citation

@inproceedings{saraiya_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{Polynomial-time program transformations in deductive databases}},
        url = {https://dl.acm.org/doi/10.1145/298514.298551},
        doi = {10.1145/298514.298551},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Saraiya, Yatin P.},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,159	On the Efficiency of Checking Perfect Privacy	2006	PODS	6.8626218e-05
7,549	Hard problems for simple logic programs	1990	SIGMOD	5.6011655e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
344	On the Power of Magic	1987	PODS	0.00020659405
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
1,970	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.3746238e-05
3,629	Compiling Separable Recursions	1988	SIGMOD	7.2392728e-05
4,150	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.8705682e-05
5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.280882e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,238	Polynomial Time Query Processing in Temporal Deductive Databases	1990	PODS
2	12,165	Does Query Evaluation Tractability Help Query Containment?	2014	PODS
3	6,282	Solving Implication Problems in Database Applications	1989	SIGMOD
4	382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
5	13,956	Knowledge compilation = Query rewriting + View synthesis	2002	PODS
6	5,736	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS
7	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
8	134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS
9	1,269	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
10	3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS