PaperlayerView exact revision on arXiv

Source-linked AI summary

Compiling Linear Datalog to SQL for Program Analysis

Amir Shaikhha, Anna Herlihy, Hung Ngo

arXiv:2609.06301v1cs.DBcs.PL

TL;DR

Datalog is effective for expressing static program analyses, but Datalog compilers and relational engines have largely developed separately. This paper compiles Linear Datalog to recursive SQL through Midlog; at 8 threads, DLSQL’s geometric-mean speedup over Soufflé is 5.46× on Umbra and 0.68× on DuckDB.

  • Problem

    Datalog compilers and relational engines have evolved in isolation, despite Datalog’s use in program analysis and relational engines’ support for recursive queries.

    Source: §1 · p. 1

  • Method

    DLSQL compiles Linear Datalog to recursive SQL through Midlog, which addresses mutual-recursion and scoping mismatches.

    Source: §1 · p. 1

  • Results

    At 8 threads, DLSQL’s geometric-mean speedup over Soufflé is 5.46× on Umbra and 0.68× on DuckDB.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Linear Datalog expresses several canonical program analyses and compiles to recursive queries that run across seven relational engines.

    Source: §9 · p. 13

    The multi-head optimization uses a linear algorithm that finds only feedback vertex sets of size one, while a generalized minimum-feedback-vertex-set approach is NP-hard.

    Source: §6.1 · p. 8

Abstract

from arXiv · show

Datalog is a declarative query language that has proven highly effective for expressing static program analyses. Although Datalog has deep roots in database theory, most recent advances have largely emerged from the programming languages and compiler communities, with systems such as Souffl\'e. In contrast, modern relational engines have made significant progress in optimizing recursive SQL. This paper revisits the connection between Datalog and relational databases, advocating recursive SQL as a backend for Datalog evaluation. We present a compilation framework that translates Datalog programs, particularly those in the Linear Datalog fragment, into equivalent recursive SQL queries. To bridge the gap between Datalog and SQL, the compiler routes every program through an intermediate language called Midlog. The compiler additionally recovers functional dependencies from the program and exposes them as schema keys, unlocking the engine's standard query optimizations. This approach enables existing database engines to execute a broad class of program analyses, outperforming the Souffl\'e engine by up to an order of magnitude on the Umbra backend. Umbra achieves a geometric-mean speedup of 5.46$\times$ at 8 threads, whereas DuckDB is competitive with Souffl\'e single-threaded and is slower at 8 threads (geometric-mean speedup of 0.68$\times$). Furthermore, the generated SQL is portable; it runs on seven database systems without any engine modification. Our results highlight what the relational engines require to fully support Datalog for large-scale program analysis.

1 Introduction

Datalog and relational engines have developed largely in isolation, despite their complementary strengths for program analysis. The paper compiles Linear Datalog to recursive SQL through Midlog and evaluates the resulting compiler across analyses and database systems.

1 Introduction

  • Datalog compilers and relational engines have evolved separately, leaving Datalog systems without relational-engine indexing and parallelism and engines without Datalog’s concise abstractions.The paper targets both sides by compiling Datalog to recursive SQL so relational engines can serve as backends without custom runtimes.Source: §1 · p. 1
  • DLSQL translates Linear Datalog, whose recursive rules contain at most one recursive predicate, into recursive SQL.The paper evaluates five canonical analyses spanning call-graph construction, borrow checking, and points-to, escape, and dataflow analysis.Source: §1 · p. 1
  • Midlog bridges the mismatch between Datalog and practical recursive SQL, including limited engine support for mutual recursion and different scoping rules.The compiler routes every program through Midlog in four phases.Source: §1 · p. 1
  • On Umbra, DLSQL achieves a 5.46× geometric-mean speedup over Soufflé at 8 threads; on DuckDB, its speedups are 0.96× single-threaded and 0.68× at 8 threads.It reaches up to 14.3× on individual benchmarks and is evaluated on five workloads, seven database engines, and four Datalog systems.Source: §1 · p. 2

2 Background

The background introduces Datalog’s rule-based fixed-point evaluation and recursive SQL’s CTE form. It explains how recursive CTEs express linear recursion and let engines perform evaluation and optimization.

2 Background

  • The section treats the database engine as a black-box recursive-query evaluator, while Datalog supplies the declarative rules and fixed-point semantics.A Datalog program is a finite set of rules; the transitive-closure example shows corresponding Datalog and SQL formulations.Source: §2 · p. 2, §2.1 · p. 2

2.1 Datalog

  • Datalog rules derive facts bottom-up until each predicate dependency component reaches a least fixed point; stratified negation is evaluated in dependency order.Rules distinguish stored EDB facts from derived IDB facts, and safety requires variables in heads, negation, or comparisons to occur in a positive body atom.Source: §2.1 · p. 2

2.2 Recursive Common Table Expressions

  • A recursive SQL CTE combines a nonrecursive base case with a recursive step and iterates to a fixed point, with at most one recursive reference per UNION branch.SQL:1999 defines mutual recursion, but among the evaluated engines only MariaDB accepts it; DLSQL emits plain WITH RECURSIVE blocks for engines to evaluate.Source: §2.2 · p. 2

3 Linear Datalog

Linear Datalog limits each rule to at most one recursive predicate from the head’s strongly connected component, allowing its fixpoint to map to recursive SQL. The section shows how this fragment captures reduced kernels of canonical analyses while excluding some nonlinear analyses.

3.1 Syntax

  • Linear Datalog permits at most one same-SCC body predicate per rule, matching SQL recursion’s single recursive-relation reference and enabling a portable recursive query.Mutual recursion can occur within the SCC, though most relational engines do not support it directly.Source: §3.1 · p. 3

3.2 Program Analyses Expressible in Linear Datalog

  • Five reduced kernels cover points-to, call-graph, escape, dataflow, and borrow-checking analyses, but they are recursive cores rather than full analyses.The kernels are cross-validated against Soufflé where each engine completes.Source: §3.2 · pp. 3–4
  • The points-to kernel propagates heap objects through assignments, casts, loads, and virtual-call resolution; it removes reachable-method and field or array-index points-to computation from the fixpoint.Those computations are supplied as precomputed inputs because their original rules are nonlinear.Source: §3.2 · p. 3
  • The call-graph kernel mutually recurses between reachable methods and call edges; CHA resolves virtual calls using subtype and method-implementation relations.Static calls carry their targets directly, and call edges arise only at reachable call sites.Source: §3.2 · p. 3, Figure 4 · p. 3
  • Escape, null-dataflow, and borrow kernels use linear reachability-style propagation, while field-sensitive and Andersen-style points-to rules fall outside the fragment.Nonlinear analyses can require engine-specific SQL extensions, external fixpoint iteration, or limited compile-time rewrites; the first two routes lose portability or optimizer visibility.Source: §3.2 · p. 4

4 The Midlog Intermediate Representation

Midlog bridges Linear Datalog and recursive SQL by representing mutually recursive relations and Datalog’s flat scope in a form suited to SQL’s recursive CTEs. Its syntax and normalization establish structural invariants, while preserving program meaning under stated conditions.

4 The Midlog Intermediate Representation

  • Midlog bridges two mismatches: most tested engines lack mutual recursion, and SQL’s lexical scoping differs from Datalog’s flat namespace.It represents an SCC with one recursive primary and non-recursive companion CTEs nested as locals.Source: §4 · p. 4

4.1 Syntax

  • Midlog merges same-head Datalog rules into a union of conjunctions and nests mutually recursive companions as lexically scoped locals.This structure mirrors one SQL WITH entry per rule and one UNION branch per conjunction.Source: §4.1 · p. 4, §4 · p. 4, Figure 5

4.2 Midlog Invariants

  • Midlog invariants ensure unique heads, one combined body per head, canonical projections, and stable schema-derived column lists for emitted CTEs.Each invariant is established by the grammar or asserted as the compiler builds the program.Source: §4.2 · pp. 4–5

4.3 Normalized Midlog

  • Normalization places each multi-member SCC under a primary definition with locals and hoists projections needed outside the SCC; the normalized program preserves the Datalog model under stated rewrite conditions.A mechanized proof of both equivalences is future work.Source: §4.3 · p. 5

5 Compiling Linear Datalog to SQL

DLSQL routes Linear Datalog through a four-phase compiler pipeline to produce recursive SQL, with Midlog bridging differences in recursion and scoping. Normalization and translation turn the program into SQL structures that a database engine evaluates.

5 Compiling Linear Datalog to SQL

  • DLSQL normalizes Datalog, translates it to Midlog, normalizes Midlog, then emits typed SQL IR for an engine-portable recursive query.The compiler emits one WITH RECURSIVE CTE per recursive group and leaves iterative evaluation to the database engine.Source: §5 · p. 5

5.1 Datalog Normalization

  • Datalog normalization rewrites supported surface syntax into single-headed Horn clauses with distinct head variables and variable-only atom arguments.It also splits disjunctions, eliminates existential wildcards, and removes rules unreachable from output relations.Source: §5.1 · p. 5

5.2 Datalog to Midlog

  • SCC analysis orders predicates topologically, then packages each component as a Midlog rule, using a MultiDef for mutually recursive relations.For cgcha, ReachableMethod and CallEdge form a MultiDef with one branch per relation; this phase establishes Midlog invariants I1–I4.Source: §5.2 · pp. 5–6

5.3 Midlog Normalization

  • Multi-member SCCs become one tagged, NULL-padded primary relation with local and hoisted projections, reducing mutual recursion to self-recursion.The encoding preserves data complexity, but its tag, padding, and k-way union overhead peaks on large SCCs with heterogeneous arities.Source: §5.3 · pp. 6–7

5.4 Midlog to SQL

  • Each Midlog conjunction becomes a SELECT–FROM–WHERE query, while primary rules with locals split into base and recursive-step branches.Repeated variables become join conditions, comparisons become WHERE predicates, and negated atoms become correlated NOT EXISTS subqueries.Source: §5.4 · p. 7

5.5 Final Statement and Output

  • The final statement selects the declared output relation, emits companion input-table DDL, and unparses SQL for the target dialect.DuckDB, Umbra, and Hyper accept the generated code unmodified.Source: §5.5 · p. 7

6 Optimizations

Two passes optimize the generated SQL: multi-head elimination can avoid a synthetic combined relation, and functional-dependency discovery exposes input keys to database engines. The multi-head rewrite is conditional, while discovered dependencies are exact for the supplied input data.

6 Optimizations

  • Two passes optimize the compiled SQL: multi-head elimination can avoid a synthetic combined relation, and functional-dependency discovery exposes schema keys to the engine.The key declarations let the engine apply its standard optimizations.Source: §6 · p. 7

6.1 Multi-Head Optimization

  • The multi-head pass lifts a self-recursive branch with a base case when it is a feedback vertex; otherwise, it uses the tagged rewrite.For cgcha, ReachableMethod is the primary and CallEdge is a local and hoisted sibling; this path is taken on every benchmark, while programs failing the condition retain the tagged fallback.Source: §6.1 · p. 8, Figure 7

6.2 Functional-Dependency Discovery for EDBs

  • FD discovery finds minimal dependencies and candidate keys from supplied EDB tuples, then declares a referenced candidate key as a primary key.The constraints are exact for the materialized input, not schema-level guarantees; discovery is worst-case exponential in attribute count, but is a one-time offline pass and the EDB arities are small.Source: §6.2 · pp. 8–9

7 Experimental Results

The evaluation compares DLSQL with Datalog systems and relational backends across five analysis workloads, then tests its optimizations, parallelism, portability, and scaling. Results vary by backend: Umbra leads at eight threads, while DuckDB’s performance depends on workload and thread count.

7.1 Experimental Setup

  • The study tests five canonical program-analysis workloads against four Datalog systems and seven database engines, using one machine and 1- and 8-thread runs.It reports median query-execution times from five repeats, excludes loading and compilation, and validates completed outputs by cardinality against Soufflé.Source: §7 · p. 9, §7.1 · p. 9

7.2 End-to-End Results

  • 17.4× and 20.5× faster than Logica on escape and cgcha at 8 threads; Logica times out on the other three benchmarks.FlowLog exceeds Soufflé only on csda (1.40×) and has a 0.53× geomean; RecStep completes only escape and cgcha, far behind DLSQL.Source: §7.2 · p. 10

7.3 Impact of the Optimizations

  • At M=6, tagged-relation overhead reaches 3.51× on DuckDB, 1.76× on Umbra, and 2.48× on Hyper; multi-head removes it when its rewrite condition holds.On cgcha, the tagged relation costs 1.45× on DuckDB, 1.84× on Umbra, and 2.02× on Hyper.Source: Figure 8 · p. 10, §7.3 · p. 10

7.4 Impact of Parallelization

  • Umbra gains 6.3–7.4× on four larger workloads but 3.9× on cgcha; DuckDB borrow anti-scales to 0.76× at 8 threads.DuckDB repeatedly parallel-scans the small static cfg_edge relation across 1008 rounds, failing to amortize scan overhead; the effect is engine-specific, while Umbra achieves 7.02× on that SCC.Source: Figure 9 · p. 10, §7.4 · pp. 10–11

7.3 Impact of the Optimizations

  • 1.68× on escape and 1.49× on csda are the largest Umbra gains from FD keys; DuckDB is neutral and Hyper gains at most 1.01×.Beyond the main backends, SQLite and PostgreSQL also improve on some workloads, while keys can slightly regress where recursion is cheap; MySQL’s key build alone exceeds 15 minutes on two large inputs.Source: §7.3 · p. 10

7.2 End-to-End Results

  • 5.46× geomean speedup over Soufflé on Umbra at 8 threads, versus 1.02× on Hyper and 0.68× on DuckDB.DuckDB reaches 0.96× single-threaded and wins three of five benchmarks; Umbra reaches 2.42× single-threaded and beats Soufflé on every benchmark at 8 threads.Source: §7.2 · p. 10, Table 2 · p. 11

7.5 Portability across Engines

  • All seven engines accept all five programs after targeted rewrites, but portability does not ensure speed: most time out on the two largest workloads.MariaDB, MySQL, and SQLite need local-IDB inlining, while PostgreSQL needs CTE shadowing for the remaining programs.Source: Table 3 · p. 11, §7.5 · p. 11

7.6 Scaling with Input Size and Recursion Depth

  • At fixed rounds, five systems grow 82–118× for 80× more edges; raising L from 50 to 800 costs relational engines 3.9–6.8× but native Datalog 1.3–1.6×.Logica times out beyond 10M edges, while the other systems complete every tested cell.Source: Figure 10 · p. 11, §7.6 · p. 12

8 Related Work

Related work spans specialized Datalog compilers, systems that evaluate Datalog through relational engines, and recursive-SQL compilation. DLSQL distinguishes itself by targeting Linear Datalog and rewriting mutual recursion and scoping through Midlog.

Datalog engines for program analysis

  • Soufflé specializes Datalog into C++, while FlowLog lowers rules to Differential Dataflow; DLSQL instead emits a standard recursive query for the host engine.FlowLog provides explicit incremental-maintenance support, whereas DLSQL exposes the entire fixpoint to the engine’s optimizer.Source: §8 · p. 12

RDBMS-backed Datalog

  • On identical DuckDB backend, DLSQL runs the entire fixpoint inside one standard recursive query and is 17.4× and 20.5× faster than Logica on the two benchmarks Logica completes.Source: §8 · p. 12

Datalog-to-SQL compilation

  • DLSQL targets Linear Datalog across seven engines and uses Midlog rewrites to handle mutual recursion and scoping within SQL’s practical restrictions.Unlike prior translation approaches discussed here, its tagged and multi-head rewrites produce single-self-reference recursive queries accepted by typical engines.Source: §8 · p. 12

9 Conclusion

The conclusion presents DLSQL as a compiler from Linear Datalog to SQL, with Midlog bridging structural differences and optimization passes refining the output. It identifies broader source-language support and additional analysis features as future work.

Conclusion

  • Linear Datalog expresses the paper’s five analysis kernels and compiles to recursive queries running across seven relational engines; Midlog handles mutual recursion and scoping differences.Multi-head rewriting and functional-dependency discovery further refine the emitted SQL.Source: §9 · p. 13
  • Extending beyond linear recursion to full Datalog and its extensions remains future work, alongside SCC-level backend selection and lattice-valued aggregations.The paper names non-standard SQL extensions, external drivers or unrolling, and compile-time rewriting as possible routes beyond the linearity restriction.Source: §9 · p. 13

Appendix: Full Rule Listings

The appendix supplies full rule listings for three analyses and identifies their recursive structure and relation roles.

Appendix: Full Rule Listings

  • Escape analysis lists all 11 rules and five IDB predicates counted in Table 1; its three recursive predicates are linear-recursive.Points-to summaries are precomputed EDB inputs.Source: Figure 11 · p. 15
  • Each Polonius borrow-checker recursive rule contains exactly one positive recursive literal, with negation only at SCC boundaries.Source: Figure 12 · p. 15
  • The ten-rule varpointsto program is linear: VarPointsTo and StaticFieldPointsTo form one mutually recursive SCC, with at most one SCC literal per rule.Figure 2 shows four of the ten rules.Source: Figure 13 · p. 16
Loading 2609.06301v1…