Introduction

Another Simplistic Datalog Implementation (ASDI), in Rust.

Datalog is a logic programming language and a subset of the earlier Prolog¹. The language is interesting as it can be used as a data query language akin to SQL with some important additional capabilities such as recursive queries. It is also expressive enough to allow for it’s use as an entailment mechanism for ontology languages such as the Web Ontology Language (OWL) and the Semantic Web.

This package provides an in-memory model to represent Datalog programs, a parser for a textual representation, relation input/output implementations and some implementations of common inference techniques.

Chapter 1, provides a brief simple description of Datalog by example.

Chapter 2 will provide a more detailed overview of Datalog itself from both an abstract point of view, and a tour of the concrete syntax used as the textual representation.

Chapter 3 will provide a guide to the crate API in a more scenario-based fashion and relies on the rust doc to provide the definitive reference.

Chapter 4 will cover the major extension points in the crate and identify how to contribute new implementations for specific extension traits.

Brief Datalog Example

We will consider the following syllogism from Mill1851, vol. 1, chap. 2:

All men are mortal.

Socrates is a man.

Therefore, Socrates is mortal.

This can be represented in the following Datalog textual program.

human("Socrates").

mortal(X) <- human(X).

?- mortal("Socrates").

The execution of this program will start with the goal query “is Socrates mortal?” and in doing so will evaluate the necessary rule and derive the relation mortal. The result is a boolean value denoting whether the goal is satisfied.

+------------+
| _: boolean |
+============+
| true       |
+------------+

However, if we were to change the final query to replace the constant with a variable, as follows.

?- mortal(X).

The program will select all matching (in this case all) facts from the mortal relation.

+------------+
| X: string  |
+============+
| "Socrates" |
+------------+

The following is the same example constructed via the ASDI library.

#![allow(unused)]
fn main() {
use asdi::{NameReferenceSet, Program};
use asdi::edb::{Attribute, Predicate};
use asdi::idb::{Atom, Term, Variable};
use std::str::FromStr;

let mut syllogism = Program::default();

let predicates = syllogism.predicates();
let p_human = predicates.fetch("human").unwrap();
let p_mortal = predicates.fetch("mortal").unwrap();

let human = syllogism
    .add_new_extensional_relation(p_human.clone(), vec![Attribute::string()])
    .unwrap();
human.add_as_fact(["Socrates".into()]).unwrap();

let variables = syllogism.variables();
let var_x: Term = variables.fetch("X").unwrap().into();

syllogism
    .add_new_pure_rule(
        p_mortal.clone(),
        [var_x.clone()],
        [Atom::new(p_human, [var_x]).into()],
    )
    .unwrap();

syllogism
    .add_new_query(p_mortal, ["Socrates".into()])
    .unwrap();
}

The textual form of Datalog also has a set of pragmas, or directives, which allow us to specify details of the relations in our program. For example, in the text below we use the assert pragma to identify an EDB relation named “human” with a single column of type string. We then go on to use the infer pragma to identify an IDB relation named “mortal”, and we declare that it’s schema is the same as the EDB relation “human”.

.assert human(string).
.infer mortal from human.

human("Socrates").

mortal(X) <- human(X).

?- mortal("Socrates").

License

MIT License

Copyright (c) 2021 Simon Johnston

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.