Type Inference for Datalog and its Application to Query Optimisation

Summary: Targeting OO-Datalog compiled to Datalog with negation, paper introduces non-Cartesian type inference that tracks field equalities to enable optimisations similar to virtual method resolution. Algorithm is sound, optimal for negation-free Datalog, and yields practical speedups in a commercial system. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h258b7c5752b79ca7
Venue: PODS
Year: 2008
Pagerank: 5.7826139e-05
Overall Rank: 6,439 | 56.73%
DOI: 10.1145/1376916.1376957

Incoming Non-self Citations Over Time

Authors

1. Oege de Moor (Semmle Ltd.)
2. Damien Sereni (Semmle Ltd.)
3. Pavel Avgustinov (Semmle Ltd.)
4. Mathieu Verbaere (Semmle Ltd.)

BibTeX Citation

@inproceedings{moor_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Type Inference for Datalog and its Application to Query Optimisation}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376957},
        doi = {10.1145/1376916.1376957},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {de Moor, Oege and Sereni, Damien and Avgustinov, Pavel and Verbaere, Mathieu},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,461	Semantic Query Optimization in the Presence of Types	2010	PODS	6.5870588e-05
5,593	Datalog and Emerging Applications: An Interactive Tutorial	2011	SIGMOD	6.0707344e-05
7,227	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	5.5784356e-05
9,989	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.0989764e-05
12,836	Autocompletion for Mashups	2009	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00058997063
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5674072e-05
1,910	Automata Theory for Database Theoreticians	1989	PODS	9.3895837e-05
2,306	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.6673254e-05
2,350	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.5959895e-05
5,859	Methods and Rules	1993	SIGMOD	5.9656486e-05
6,826	Can Datalog be approximated?	1994	PODS	5.6695242e-05
7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	5.6068861e-05
8,061	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	5.3953684e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,133	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD
2	13,336	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
3	6,432	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
4	8,488	Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries	1987	VLDB
5	4,084	Type Systems for Querying Class Hierarchies with Non-strict Inheritance.	1989	PODS
6	2,319	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS
7	12,871	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB
8	13,395	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
9	328	Declarative Information Extraction Using Datalog with Embedded Extraction Predicates	2007	VLDB
10	13,261	Implementing Abstract Objects with Inheritance in Datalog^neg	1997	VLDB