Implementing Deductive Databases by Linear Programming

Summary: Compile deductive logic programs (including negation and disjunction) into mixed-integer linear programs to perform deduction at compile-time and compute minimal models. Enables incremental updates via constraint insertion/deletion, avoids SLD looping, and maps to RDBMS-backed query execution; prototype shows promising performance. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 973
Venue: PODS
Year: 1992
Pagerank: 5.093636e-05
Overall Rank: 13,083 | 10.24%
DOI: 10.1145/137097.137892

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Colin Bell (University of Iowa)
2. Anil Nerode (Cornell University)
3. Raymond T. Ng (University of Maryland)
4. V.S. Subrahmanian (University of Maryland)

BibTeX Citation

@inproceedings{bell_pods92,
        address = {New York, NY, USA},
        series = {{PODS} '92},
        title = {{Implementing Deductive Databases by Linear Programming}},
        url = {https://dl.acm.org/doi/10.1145/137097.137892},
        doi = {10.1145/137097.137892},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bell, Colin and Nerode, Anil and Ng, Raymond T. and Subrahmanian, V.S.},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
344	On the Power of Magic	1987	PODS	0.00020659405
1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS	0.0001126031
1,538	Bottom-Up Beats Top-Down For Datalog	1989	PODS	0.00010446034
5,161	Rewriting of Rules Containing Set Terms in a Logic Data Language (LDL)	1988	PODS	6.3398667e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,885	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD
2	13,956	Knowledge compilation = Query rewriting + View synthesis	2002	PODS
3	5,046	Toward Practical Constraint Databases	1993	VLDB
4	3,107	Integrity Checking in Deductive Databases	1987	VLDB
5	13,040	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
6	6,752	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB
7	1,830	Optimizing the Rule-Data Interface in a KMS	1986	VLDB
8	12,939	Binding Propagation in Disjunctive Databases	1998	VLDB
9	13,049	Query Evaluation under the Well Founded Semantics (Extended Abstract)	1993	PODS
10	7,886	Polynomial-time program transformations in deductive databases	1990	PODS