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: 1469
Venue: PODS
Year: 2008
Pagerank: 5.1109656e-05
Overall Rank: 6,312 | 56.14%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,732	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2137395e-05
5,629	Datalog and Emerging Applications: An Interactive Tutorial	2011	SIGMOD	5.4018902e-05
6,955	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	4.8812945e-05
9,676	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	4.3006524e-05
12,354	Autocompletion for Mashups	2009	VLDB	4.1905499e-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.00099936325
1,687	Automata Theory for Database Theoreticians	1989	PODS	0.0001090256
1,959	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.958725e-05
2,323	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	9.0322199e-05
2,396	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.8892825e-05
5,099	Methods and Rules	1993	SIGMOD	5.6942143e-05
6,751	Can Datalog be approximated?	1994	PODS	4.9352222e-05
7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.8389293e-05
7,884	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	4.6233362e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,856	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1905499e-05
6,253	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.1318715e-05
5,996	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2365238e-05
7,823	Optimization Of Systems Of Algebraic Equations For Evaluating Datalog Queries	1987	VLDB	4.6390991e-05
3,865	Type Systems for Querying Class Hierarchies with Non-strict Inheritance.	1989	PODS	6.6809234e-05
1,900	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	0.00010168127
12,390	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	4.1905499e-05
12,914	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1905499e-05
289	Declarative Information Extraction Using Datalog with Embedded Extraction Predicates	2007	VLDB	0.00028865317
12,780	Implementing Abstract Objects with Inheritance in Datalogneg	1997	VLDB	4.1905499e-05