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: 1468
Venue: PODS
Year: 2008
Pagerank: 5.9176726e-05
Overall Rank: 6,310 | 56.71%
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,369	Semantic Query Optimization in the Presence of Types	2010	PODS	6.7390374e-05
5,473	Datalog and Emerging Applications: An Interactive Tutorial	2011	SIGMOD	6.2055397e-05
7,079	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	5.7090732e-05
9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.214913e-05
12,540	Autocompletion for Mashups	2009	VLDB	5.093636e-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
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
1,856	Automata Theory for Database Theoreticians	1989	PODS	9.6053834e-05
2,248	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.8703718e-05
2,296	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.7908999e-05
5,734	Methods and Rules	1993	SIGMOD	6.105443e-05
6,690	Can Datalog be approximated?	1994	PODS	5.8012926e-05
6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	5.7382018e-05
7,888	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	5.5217972e-05

Semantically Similar Papers

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