chase-rs/docs

About the Project

Chase-rs is a Rust implementation of the chase algorithm for reasoning over rules and facts. It is designed for database-theory style workloads such as:

• query answering under tuple-generating dependencies
• materializing implied facts from rules
• working with existential rules that create fresh labeled nulls

The project focuses on correctness first, while still keeping the codebase small, fast, and idiomatic.

Main Features

• Core chase engine for deriving implied facts from rules and an initial instance
• Restricted-chase style active-trigger checks for existential rules
• Automatic generation of labeled nulls for existential variables
• Fluent RuleBuilder API for constructing rules in Rust
• Configurable step limit through chase_with_config
• Interactive frontend options:
  • REPL
  • script runner
  • local GUI
• Querying and explanation support in the frontend session layer
• Example scripts and Geolog examples for transitive closure, existential rules, and joins

---

Quickstart

1. Run the example script

cargo run -- script examples/scripts/ancestor.chase

This loads a few Parent facts, applies ancestor rules, runs the chase, and prints the derived answers.

2. Open the REPL

cargo run -- repl

In the REPL you can add facts, add rules, run the chase, query results, and ask for explanations.

3. Open the GUI

cargo run -- gui

This starts a local web UI at http://127.0.0.1:7878 where you can type the same commands as in the REPL.

---

Glossary of Important Terms

• Atom: A predicate applied to one or more terms, for example Parent(alice, bob).
• Fact: A ground atom, meaning an atom with no variables. Facts are the input database state.
• Instance: The set of facts currently known to the chase engine.
• Rule / TGD: A tuple-generating dependency of the form body -> head that derives new facts when its body matches.
• Chase: The process of repeatedly applying rules until no new facts can be derived or a configured step limit is reached.
• Materialization: The fully derived instance produced by running the chase.
• Existential Rule: A rule whose head contains variables that do not appear in the body. These variables represent values that must be invented.
• Labeled Null: A fresh invented value used to satisfy an existential variable during the chase.
• Restricted Chase: The chase variant used by default in this project. It avoids redundant applications by checking whether a trigger is still active.
• Trigger: A particular match of a rule body against the current instance.
• Active Trigger: A trigger that still requires the rule to fire because its head is not already satisfied.
• Query: A conjunctive pattern used to ask for matching facts after, or sometimes before, materialization.
• Explanation: A derivation trace that shows why a query answer is present.
• Termination: Whether the chase finished normally or stopped because it reached the configured step bound.

Example Terms

• Parent, Ancestor, and WorksIn are example predicates used in the scripts.
• ?X, ?Y, and ?Dept are variables in the frontend command language.
• alice, bob, and carol are constants.

Changelog

• April 8, 2026 -- The first version of this document was written.