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.7634942e-05
Overall Rank: 6,451 | 56.76%
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,482	Semantic Query Optimization in the Presence of Types	2010	PODS	6.5653184e-05
5,608	Datalog and Emerging Applications: An Interactive Tutorial	2011	SIGMOD	6.0506609e-05
7,246	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	5.5599899e-05
10,024	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.082116e-05
12,879	Autocompletion for Mashups	2009	VLDB	4.9605343e-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.00058816744
1,827	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5417632e-05
1,920	Automata Theory for Database Theoreticians	1989	PODS	9.3586444e-05
2,318	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.6386744e-05
2,354	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.5732755e-05
5,872	Methods and Rules	1993	SIGMOD	5.9459225e-05
6,843	Can Datalog be approximated?	1994	PODS	5.6508689e-05
7,086	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	5.5883468e-05
8,078	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	5.377528e-05

Semantically Similar Papers

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