Darwen

Darwen is an in-memory engine for relational algebra inspired by The Third Manifesto of Date, Codd, and Darwen.

This is the final version of the library. Further development is not planned, because the project is educational.

Example

use darwen::{
    heading,
    tuple,
    prelude::{AttributeName, Predicate, RelationBuilder, Scalar, ScalarType},
};

let users = RelationBuilder::new()
    .with_heading(heading!(name = ScalarType::String, age = ScalarType::Integer)?)
    .with_body(vec![
        tuple!(name = "Monica", age = 18)?,
        tuple!(name = "Erica", age = 19)?,
        tuple!(name = "Rita", age = 20)?,
        tuple!(name = "Tina", age = 21)?,
        tuple!(name = "Sandra", age = 22)?,
        tuple!(name = "Mary", age = 23)?,
        tuple!(name = "Jessica", age = 18)?,
    ])
    .build()?;

let adults = users.restrict(&Predicate::gt(
    AttributeName::from("age"),
    Scalar::Integer(20),
))?;

let expected = RelationBuilder::new()
    .with_heading(heading!(name = ScalarType::String, age = ScalarType::Integer)?)
    .with_body(vec![
        tuple!(name = "Tina", age = 21)?,
        tuple!(name = "Sandra", age = 22)?,
        tuple!(name = "Mary", age = 23)?,
    ])
    .build()?;

assert_eq!(adults, expected);
# Ok::<(), darwen::prelude::Error>(())

Predicates

Darwen supports six predicate forms:

• Not / Predicate::not negates another predicate.
• And / Predicate::and performs logical conjunction; both sides are always evaluated and errors are not hidden.
• Or / Predicate::or performs logical disjunction; both sides are always evaluated and errors are not hidden.
• Eq / Predicate::eq compares two operands for equality; only INTEGER = INTEGER, BOOLEAN = BOOLEAN, STRING = STRING, and BINARY = BINARY are valid. Mixed-type comparisons return an error.
• Gt / Predicate::gt compares two operands with >; only INTEGER > INTEGER is valid. All other comparisons return an error.
• Lt / Predicate::lt compares two operands with <; only INTEGER < INTEGER is valid. All other comparisons return an error.

Implemented Operations

RESTRICT/SELECTION (σ)

Example - cargo run --example restrict

σ age > 20 (people)

people

name	age
Ann	19
Bob	24

Output

name	age
Bob	24

Code

let adults = people.restrict(&Predicate::gt(
    AttributeName::from("age"),
    Scalar::Integer(20),
))?;

PROJECT (π)

Example - cargo run --example project

π name (people)

people

name	age
Ann	19
Bob	24

Output

name
Ann
Bob

Code

let names = people.project(&[AttributeName::from("name")])?;

RENAME (ρ)

Example - cargo run --example rename

ρ person_name/name (people)

people

name
Ann
Bob

Output

person_name
Ann
Bob

Code

let renamed = people.rename(&[(
    AttributeName::from("name"),
    AttributeName::from("person_name"),
)])?;

UNION (⋃)

Example - cargo run --example union

a ⋃ b

a

value
foo
bar

b

value
bar
baz

Output

value
foo
bar
baz

Code

let result = a.union(&b)?;

DIFFERENCE (−)

Example - cargo run --example difference

a − b

a

value
foo
bar
baz

b

value
bar

Output

value
foo
baz

Code

let result = a.difference(&b)?;

PRODUCT (×)

Example - cargo run --example product

colors × sizes

colors

color
red
blue

sizes

size
S
M

Output

color	size
red	S
red	M
blue	S
blue	M

Code

let result = colors.product(&sizes)?;

JOIN (⋈)

Example - cargo run --example join

users ⋈ cities

users

id	name
1	Ann
2	Bob

cities

id	city
1	Rome
3	Oslo

Output

id	name	city
1	Ann	Rome

Code

let result = users.join(&cities)?;

INTERSECT (∩)

Example - cargo run --example intersect

a ∩ b

a

value
foo
bar

b

value
bar
baz

Output

value
bar

Code

let result = a.intersect(&b)?;

DIVIDE (÷)

Example - cargo run --example divide

enrollments ÷ required_courses

enrollments

student	course
Ann	Math
Ann	Rust
Bob	Math
Bob	Rust
Bob	DB
Kate	Math

required_courses

course
Math
Rust

Output

student
Ann
Bob

Code

let result = enrollments.divide(&required_courses)?;

Sources

• The Third Manifesto - the foundational manifesto of relational databases
• TutorialD - a practical implementation of relational algebra
• BNF for TutorialD from RelDB project