Source-linked AI summary
The Vadalog System: Datalog-based Reasoning for Knowledge Graphs
Luigi Bellomarini, Georg Gottlob, Emanuel Sallinger
TL;DR
Knowledge-graph reasoning needs Datalog extensions such as existential quantification, but unrestricted reasoning becomes undecidable and Warded Datalog± previously lacked an implementation. The paper presents Vadalog, implements Warded Datalog± with termination-control techniques, and evaluates it across real-world and synthetic scenarios. The system shows competitive performance and outperforms existing reasoners in the reported comparisons.
Problem
Existing Datalog-based reasoning needed existential quantification for complex knowledge-graph scenarios, yet unrestricted reasoning is undecidable and Warded Datalog± had no implementation.
Method
The paper presents Vadalog, a Datalog-based system whose logical core is Warded Datalog± and whose recursion-control techniques guide termination with limited memory.
Results
Vadalog receives a full-scale evaluation on real-world and synthetic scenarios and outperforms existing reasoners in the reported comparisons.
Takeaways & Limitations
Vadalog provides a practical implementation of Warded Datalog± with competitive performance across the evaluated scenarios.
Takeaways & Limitations
Generic chase memorization and full isomorphism checking are impractical in space and time, while pruning labelled-null isomorphisms is not generally correct; harmless Warded Datalog± is a restricted case where generic chase graphs can be used.
Abstract
from arXiv · showhide
Over the past years, there has been a resurgence of Datalog-based systems in the database community as well as in industry. In this context, it has been recognized that to handle the complex knowl\-edge-based scenarios encountered today, such as reasoning over large knowledge graphs, Datalog has to be extended with features such as existential quantification. Yet, Datalog-based reasoning in the presence of existential quantification is in general undecidable. Many efforts have been made to define decidable fragments. Warded Datalog+/- is a very promising one, as it captures PTIME complexity while allowing ontological reasoning. Yet so far, no implementation of Warded Datalog+/- was available. In this paper we present the Vadalog system, a Datalog-based system for performing complex logic reasoning tasks, such as those required in advanced knowledge graphs. The Vadalog system is Oxford's contribution to the VADA research programme, a joint effort of the universities of Oxford, Manchester and Edinburgh and around 20 industrial partners. As the main contribution of this paper, we illustrate the first implementation of Warded Datalog+/-, a high-performance Datalog+/- system utilizing an aggressive termination control strategy. We also provide a comprehensive experimental evaluation.
1. INTRODUCTION
The paper motivates a resurgence of Datalog for knowledge-graph reasoning, where recursion, ontological reasoning, and tractable complexity must coexist despite undecidability challenges. It presents Vadalog as the first practical implementation of Warded Datalog± and reports experimental evidence that it outperforms existing reasoners.
- Motivation: Knowledge graphs renewed interest in deductive databases, but existing systems faced hardware, database-management, and expressiveness barriers.The paper connects this renewed interest to scalability demands and corporate efforts to represent and exploit knowledge graphs.
- Requirements: A suitable knowledge-graph reasoner must support recursion and joins, ontological reasoning, and tractable data complexity.Recursion enables graph navigation and complex reasoning, while tractability is presented as necessary for scaling over large data volumes.
- Requirements: Recursive Datalog with existential quantification is undecidable, forcing trade-offs between recursion, existential reasoning, and low complexity.The paper uses Datalog± to denote languages that add existential features while imposing restrictions for decidability.
- Prior work: Warded Datalog± is identified as the only known language satisfying all three requirements, but its existing algorithms were impractical for implementation.Weakly Frontier Guarded Datalog± is EXPTIME-complete, whereas Warded Datalog± lacked a practical implementation despite favorable theoretical properties.
- Contribution: Vadalog implements Warded Datalog± using guide structures that control termination and memory while exploiting execution periodicity.The linear forest, warded forest, and lifted linear forest provide complementary roles in the first practical algorithm for Warded Datalog±.
- Evaluation: The evaluation reports that Vadalog outperforms top existing systems in absolute and comparative performance.The paper describes a full-scale evaluation across real-world and synthetic scenarios.
2. REASONING WITH VADALOG
Vadalog uses existential rules and Warded Datalog± to support reasoning over databases with generated nulls while preserving tractability. Its wardedness conditions constrain null propagation by localizing dangerous variables within a ward.
- Core language: Datalog± generalizes Datalog rules with existentially quantified variables in rule heads, and its semantics is defined through the chase procedure.The chase adds facts, possibly containing nulls, until the existential rules are satisfied; the result may be infinite.
- Core language: Reasoning computes universal answers whose tuples are preserved across all solutions through a homomorphism.The paper defines the reasoning task using a database, existential rules, answer predicates, and a most-general answer instance.
- Core language: General existential-rule reasoning is undecidable even when the query is fixed and only the database varies.Restrictions on existential rules define decidable Datalog± languages.
- Warded Datalog±: Warded Datalog± captures PTIME data complexity, includes Datalog, and supports ontological reasoning.These properties motivate its use as Vadalog’s logical core.
- Warded Datalog±: Wardedness limits null propagation by requiring dangerous variables to occur in one ward that shares only harmless variables with other body atoms.Dangerous variables can bind to labelled nulls and occur in heads; the ward localizes them during rule evaluation.
- Warded Datalog±: Harmful joins are permitted in Warded Datalog± when the harmful variable is not dangerous, although the more restrictive harmless fragment forbids such joins.The paper’s examples distinguish harmful variables, dangerous variables, and the role of the ward.
3. TERMINATION AND RECURSION CONTROL
The Vadalog system controls potentially infinite existential-rule chases using structural properties of Warded Datalog±, preserving correctness while targeting practical termination and lower checking overhead.
- Warded forest: The warded forest preserves chase structure by connecting linear-rule derivations and ward-directed edges from non-linear rules.Each fact inherits labelled nulls from one direct parent or ward, exposing structural organization for the chase.
- Warded forest: Isomorphic facts in a warded forest have isomorphic subtrees, enabling structurally equivalent chase regions to be recognized without changing the reasoning result.This periodicity underlies termination control, although unrestricted chase memorization and isomorphism checking are impractical.
- Harmless Warded Datalog±: Pruning by labelled-null isomorphism is not correct for general Warded Datalog±, but it becomes valid for Harmless Warded Datalog±.Theorem 2 applies when joins on harmful variables are forbidden; general warded rules can be rewritten into an equivalent harmless set.
- Harmless Warded Datalog±: The first two rewritten rules encode grounded harmful-variable cases, while the remaining rules encode StrongLink transitive closure; the rewriting procedure terminates for Warded Datalog±.This rewriting supports applying the harmless-case structural results to the broader warded setting.
- Lifted linear forest: The lifted linear forest groups pattern-isomorphic linear subtrees into equivalence classes, factoring out structural symmetries independently of specific ground values.Together with the linear and warded forests, it reduces unnecessary isomorphism checks in Algorithm 1.
- Termination strategy: The algorithm provides termination guarantees for Warded Datalog± while controlling fact generation in the generally infinite chase.It guides each chase step by deciding whether it should be activated.
4. ARCHITECTURE
Vadalog compiles rules and queries into a pull-based pipe-and-filters pipeline that streams data while controlling recursion and termination. Its architecture combines specialized cycle handling, caching, dynamic indexing, and non-blocking aggregation.
- Memory management: The system addresses chase-based scalability limits with a specialized streaming architecture rather than requiring all original and generated data as chase inputs.Intermediate facts are held in fragmented per-filter buffer caches, while final facts can be materialized at the end.
- Pipeline architecture: Vadalog compiles rules and queries into an active pipeline that reads inputs, transforms data, and produces outputs.The architecture applies logic optimization before execution and represents external sources and terminal results as pipeline filters.
- Execution model: The pull-based execution model uses a round-robin strategy across parent filters to balance workload and propagate facts through recursive pipelines.Round-robin exploration also supports breadth-first rule application.
- Join processing: The slot machine join extends indexed nested-loop joins with dynamic in-memory indexes built as iterators consume predicate facts.The technique supports arbitrary predicate arity and can fall back to scans when indexed matches are unavailable.
- Aggregation: Non-blocking monotonic aggregation avoids introducing blocking nodes into the pipeline.This feature is presented as a way to support aggregation within the stream-based execution model.
- Cycle management: Cycle management distinguishes temporary cyclic misses from permanent real misses before allowing a negative answer.The notifyCycle() signal propagates through the pipeline, while round-robin exploration preserves fair treatment of recursive and base cases.
5. ADVANCED VADALOG FEATURES
Vadalog extends its Warded Datalog± core with practical language features for real-world reasoning, including typed terms, expressions, Skolem functions, annotations, and monotonic aggregation. These features improve expressiveness but particular combinations may produce highly complex or non-terminating programs.
- Overview: Advanced Vadalog features extend the tractable Warded Datalog± core, but some feature combinations may be highly complex or non-terminating.The core guarantees tractability, whereas advanced combinations do not generally preserve those guarantees.
- Data types: Vadalog supports integer, float, string, date, Boolean, set, list, and dictionary data types.Terms, including variables and constants, are typed in the language.
- Expressions: Expressions can serve as condition operands or assignments that define values for existentially quantified head variables.Expressions are defined recursively from terms and combinations of expressions.
- Skolem functions: Deterministic, injective, range-disjoint Skolem functions calculate existential values while controlling labelled-null identity.Repeated invocations produce the same labelled null for the same function arguments.
- Monotonic aggregation: Monotonic aggregation adds sum, min, max, count, grouping, and windowing while preserving monotonicity with respect to set containment.Aggregations operate as stateful record-level operators whose subsequent invocations return updated values.
- Aggregate rules: Aggregate rules group tuples and track contributors while computing an existentially quantified monotonic aggregate.Contributor variables enable subgrouping or windowing, and aggregation can be expressed through functions such as maggr.
- Aggregation example: The aggregation example produces two groups, for x = 1 and x = 2, with outputs determined by contributor-sensitive maxima and sums.The described chase sequence yields Q(1, 5), Q(1, 12), Q(2, 2), Q(2, 3), and Q(2, 4).
- Aggregation semantics: Monotonicity ensures that each group’s final aggregate is independent of the permitted chase sequence.The paper also identifies summing distinct contributors as another aggregation use case.
6. EXPERIMENTAL EVALUATION
The evaluation covers synthetic, data-integration, real-world, and generic reasoning scenarios, testing scalability, termination control, and comparisons with existing systems. Across these settings, Vadalog shows strong performance, including faster execution, polynomial scaling, and limited memory use.
- Evaluation scope: The evaluation uses two synthetic, two real-world, and additional generic reasoning scenarios involving non-trivial warded Datalog± rules.The scenarios include existentials, harmful joins, null propagation, recursion, and cases where wardedness cannot be exploited.
- Synthetic scenarios: Eight iWarded scenarios vary rule types, recursion, existential quantification, and harmless or harmful joins while activating all rules through common multi-queries.The generator controls linear and non-linear rules, recursion, existential rules, and join configurations.
- Synthetic scenarios: Under 10 seconds, Vadalog performs best on SynthB and SynthH, where warded joins create deep forests that strengthen isomorphism checks and pattern learning.SynthB's 45 harmless-harmful joins increase execution time by only 1 second.
- Scalability: All synthetic scenarios use less than 400MB of memory, while scaling tests show polynomial behavior and 4 to 51 seconds across 10k to 500k tuples.Increasing rules from 100 to 1k raises elapsed time from 9 to 101 seconds in the reported Rule# experiment.
- iBench: Vadalog completes STB-128 in 6.59 seconds and ONT-256 in 51.579 seconds, outperforming all compared chase-based systems and averaging 3 times the speed of RDFox.The comparison uses ChaseBench scenarios translated into Vadalog and includes RDFox, LLunatic, DLV, Graal, and PDQ.
- DBpedia: On DBpedia transitive-closure scenarios, execution times grow linearly and remain below 100 seconds, while Vadalog is twice as fast as Neo4J.PostgreSQL, MySQL, and Oracle report six-times worse performance, and monotonic aggregation adds no observed overhead.
7. RELATED WORK AND COMPARISON
The comparison surveys reasoning systems related to Vadalog, emphasizing trade-offs among chase strategies, query rewriting, recursion, and memory usage. Vadalog avoids some homomorphism-check and grounding costs through fragment-aware techniques.
- Systems based on query rewriting: PDQ is outperformed by Vadalog by three orders of magnitude in the tested scenarios.PDQ combines query rewriting with restricted chase on PostgreSQL, but interleaving homomorphism checks and updates is reported to be ineffective performance-wise.
- Systems based on query rewriting: Graal uses saturation and homomorphism checks across multiple backends, whereas Vadalog exploits fragment structure to avoid those checks and storing a fresh copy of generated facts.The comparison attributes performance drawbacks to both full homomorphism checking and restricted-chase implementations.
- In-memory systems: DLV’s in-memory grounding creates a memory footprint that becomes prohibitive for large inputs, unlike Vadalog’s lifted inference.DLV supports advanced Datalog optimizations and performs better than PDQ and Graal, but the cited limitation is grounding-related memory use.
- In-memory systems: Vadalog is three times faster than RDFox on iBench by considering fewer structurally similar rule instances through the lifted linear forest.RDFox considers all rule instances, while Vadalog reduces the number considered when input tuples are structurally similar.
- Restricted versus unrestricted chase: Backend-based restricted chase implementations repeatedly pay query overhead because updates can invalidate earlier homomorphism checks.The example shows how derived facts can trigger further rules and invalidate a previous check; Vadalog instead recognizes isomorphic copies within warded-forest components.
8. CONCLUSION
The paper introduces Vadalog as the first implementation of Warded Datalog±, using novel recursion-control techniques. The system shows competitive performance on real-world and synthetic benchmarks, while further optimization and data-source expansion remain future work.
- Vadalog is presented as the first implementation of Warded Datalog±.
- Novel recursion-control techniques exploit the theoretical properties of Warded Datalog± at the core of the system.
- The architecture and system exhibit competitive performance on real-world and synthetic benchmarks.
- Further work includes more sophisticated cost-based query-plan optimization and support for additional data sources.