Research map / Large language models / Retrieval and knowledge
Optimised Storage for Datalog Reasoning
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.
Proposes a multi-scheme framework that integrates compressed storage (interval-based transitive closure and union tables) with semi-naive materialisation, enabling Datalog materialisation that fits in memory where standard approaches fail.
Problem
Datalog materialisation stores all derived facts, which becomes infeasible in memory for transitive and union rules over large fact sets (e.g., DBpedia broader relation transitive closure with 8.5 billion facts).
Approach
A general framework separating storage from reasoning so that specialised storage schemes (interval-tree-based transitive closure with incremental insertion support, and virtual union tables) can be plugged into semi-naive/modular materialisation, with schemes exposing schedule, derive and merge functions.
Key results
- On DBpedia broader subsets, the TC scheme is roughly 100-1000x faster than the standard approach and uses about 1/8 to 1/5 of its memory on small subsets.
- On the 50% DBpedia subset, the multi-scheme approach is 27x faster than standard (23,092s vs 479s-type comparison, reported as 479.35s vs 12,879.90s) and uses about 1/3 the memory.
- Standard and TC Module approaches fail to finish the 75% and full DBpedia materialisation, while the multi-scheme approach completes using around 15 GB, versus estimated 515 GB and 2094.9 GB for storing the materialisation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TC and Union storage schemes with a plain table | MultiScheme reasoning · DBpedia DB25% | time (s): 33.42 -> 31.39 | No clear effect |
| Use TC and Union storage schemes with a plain table | MultiScheme reasoning · DBpedia DB50% | time (s): 12,879.90 -> 479.35 | Helped |
| Use TC and Union storage schemes with a plain table | MultiScheme reasoning · DBpedia DB50% | peak memory (GB): 30.8 -> 8.7 | Helped |
| Use TC and Union storage schemes with a plain table | MultiScheme reasoning · DAG-R | time (s): 3,973.21 -> 26.45 | Helped |
| Use TC and Union storage schemes with a plain table | MultiScheme reasoning · Relations | peak memory (GB): 11.0 -> 4.9 | Helped |
| Store transitive closure in the TC storage scheme | DBpedia broader materialisation · DBpedia broader, 159,561 ▷ 29,086,642 | time (s): 2,845.08 -> 8.44 | Helped |
| Store transitive closure in the TC storage scheme | DBpedia broader materialisation · DBpedia broader, 159,561 ▷ 29,086,642 | peak memory (MB): 1,480.58 -> 249.64 | Helped |
| Store transitive closure in the TC storage scheme | DBpedia broader materialisation · DBpedia broader, 1,426,588 ▷ 1,949,306,188 | time (s): >38h -> 443.80 | Helped |
| Store transitive closure in the TC storage scheme | DBpedia broader materialisation · DBpedia broader, 1,426,588 ▷ 1,949,306,188 | peak memory (MB): 97,940.15 -> 2,447.91 | Helped |
| Use TC storage scheme instead of plain fact storage | MultiScheme query answering · DBpedia 50%, TC query Q0 (140M) | query time (s): 8.38 -> 22.43 | Hurt |
| Use Union storage scheme instead of plain fact storage | MultiScheme query answering · DBpedia 50%, Union query Q4 (337) | query time (s): 0.03 -> 0.03 | No clear effect |
Surprising findings
- For DAG-R, TC schemes speed up runtime but barely reduce memory because the transitive closure is large.
- Queries over union predicates are 2-20x slower in the multi-scheme approach, since retrieval must check other schemes to remove duplicates.
Limitations
- Deletion is not supported in the multi-scheme framework.
- Union queries are substantially slower (up to ~20x) than standard, and memory savings are limited on DAG-R due to large closure size.
Experimental setup
Datasets: DBpedia SKOS broader relation Relations Ontology synthetic dataset DAG-R synthetic benchmark
Benchmarks: DBpedia DAG-R Relations
Metrics: materialisation time (s) peak memory (GB/MB) static memory query answering time (s)
Baselines: Standard semi-naive materialisation TC Module (modular seminaive)
Builds on: semi-naive evaluation interval-based transitive closure compression modular materialisation (TC module)
Closest papers by meaning
- LogicCat: A Chain-of-Thought Text-to-SQL Benchmark for Complex Reasoning (AAAI 2026 · similarity 0.85)
- Holistic Reasoning with Long-Context LMs: A Benchmark for Database Operations on Massive Textual Data (ICLR 2025 · similarity 0.84)
- Reasoning Path Compression: Compressing Generation Trajectories for Efficient LLM Reasoning (NeurIPS 2025 · similarity 0.83)
- Goal-Driven Reasoning in DatalogMTL with Magic Sets (AAAI 2025 · similarity 0.83)
- Computing the Why-Provenance for Datalog Queries via SAT Solvers (AAAI 2024 · similarity 0.83)
- Plan and Budget: Effective and Efficient Test-Time Scaling on Reasoning Large Language Models (ICLR 2026 · 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.