Research map / Large language models / Agents, code and math
Goal-Driven Reasoning in DatalogMTL with Magic Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends magic set rewriting to DatalogMTL, producing goal-driven rewritten programs that are then reasoned over with a finite-representation (MeTeoR-style) materialisation, and shows large speedups on LUBM_t, iTemporal and meteorological benchmarks.
Problem
Reasoning in DatalogMTL is computationally very expensive, and bottom-up materialisation derives many temporal facts irrelevant to a specific query, which can exhaust memory.
Approach
A temporal variant of magic set rewriting that adds diamond operators to magic-predicate body atoms and boxminus/boxplus head adjustments (via MagicHeadAtoms) so that query-relevant time points are preserved; the query interval is replaced by (-inf,+inf) so the rewriting is query-time independent, and termination is retained for bounded programs.
Key results
- On LUBM_t, the magic-rewritten programs answered every query faster, with the least speedup 1.95x and the most 111,157x for not-entailed queries.
- On iTemporal, a more than 69,000x performance boost was observed on every query.
- On meteorological data, the least accelerated query was 1.58x faster and one query was over 1 million times faster.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply temporal magic-set rewriting | DatalogMTL reasoning on LUBM_t · LUBM_t, 10^6 facts, all queries | query speedup: 1.95 times speedup at minimum | Helped |
| Apply temporal magic-set rewriting | DatalogMTL reasoning on LUBM_t · LUBM_t, 10^6 facts, entailed queries | query speedup: more than 3.46 times; more than 112 times; 2,110 times | Helped |
| Apply temporal magic-set rewriting | DatalogMTL reasoning on LUBM_t · LUBM_t, 10^6 facts, not-entailed queries | query speedup: more than 12 times; more than 128 times; more than 9,912 times; 111,157 times | Helped |
| Apply temporal magic-set rewriting | DatalogMTL reasoning on meteorological data · Meteorological data, ten years | query speedup: 1.58 times; more than 3.54 times; more than 1 million times | Helped |
| Apply temporal magic-set rewriting | DatalogMTL reasoning on iTemporal · iTemporal, 10^5 facts | query speedup: more than 69,000 times; some over a million times | Helped |
| Apply temporal magic-set rewriting | DatalogMTL canonical-model computation · LUBM_t, dataset scalability | materialisation time | Helped |
| Apply temporal magic-set rewriting | DatalogMTL canonical-model computation · iTemporal, dataset scalability | materialisation time | Helped |
Limitations
- Only handles fact queries in evaluation since current DatalogMTL systems do not answer non-ground queries.
- Does not support negation or aggregation.
- Termination guarantee only for bounded programs and datasets.
Experimental setup
Datasets: LUBM_t iTemporal meteorological data
Benchmarks: LUBM_t iTemporal meteorological
Metrics: query answering time speedup ratio scalability (materialisation time)
Baselines: MeTeoR
Builds on: magic sets DatalogMTL MeTeoR
Closest papers by meaning
- LogicCat: A Chain-of-Thought Text-to-SQL Benchmark for Complex Reasoning (AAAI 2026 · similarity 0.85)
- Large Language Models Meet Symbolic Provers for Logical Reasoning Evaluation (ICLR 2025 · similarity 0.84)
- Reasoning-as-Logic-Units: Scaling Test-Time Reasoning in Large Language Models Through Logic Unit Alignment (ICML 2025 · similarity 0.84)
- ORACLE: Optimizing Reasoning Abilities of Large Language Models via Constraint-Led Synthetic Data Elicitation (AAAI 2026 · similarity 0.84)
- Bag of Tricks for Inference-time Computation of LLM Reasoning (NeurIPS 2025 · similarity 0.84)
- Optimised Storage for Datalog Reasoning (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.