Skip to content

Part 2: Unification, negation, and ignoring columns

Part 1 ended with a promise: declaring a relation pays off when its columns are reasoned over, not merely read. This part is the runway for that. By the end you will know what a query means, and you will have written a relation in terms of another, denied one, and seen the one way a denial asks a different question than you meant.

Nothing new is stored. The cargo relation and the two cargos from Part 1 are still there, and every example below asks them something. If you skipped Part 1, its first section is all you need.

We start smaller than that, with two variables and a string.

Unification, and, or

Before we build anything more impressive, we need to step back and learn some basics. First, we need to learn how to say that things are equal, and in relational programming the name for that is unification. This is how a variable value gets deduced:

Unifiable<String> first = lvar();
Query.of(first.unifies("Hello"))
        .select(first).stream()
        .map(row -> row.get(first))
        .collect(toList());              // ["Hello"]
What Query.of takes is called a goal: an invariant all answers must satisfy. A unification is the simplest goal, and there are two ways to combine them into a bigger one. They can be declared to hold together, in conjunction:

Unifiable<String> first = lvar();
Unifiable<String> second = lvar();
Query.of(first.unifies("Hello").and(second.unifies("world!")))
        .select(first, second).stream()
        .map(row -> row.get(first) + " " + row.get(second))
        .collect(toList());              // ["Hello world!"]

Whenever the engine finds an and, it will make sure that both sides of it hold in a single answer. Here, it is visible in two ways: we select both first and second, and we read them from a single row. When solutions are collected, we only have one, and it is the mapped Hello world!. If the two sides cannot both hold, this line of reasoning is abandoned and produces no answer:

Unifiable<String> first = lvar();
Query.of(first.unifies("Hello").and(first.unifies("world!")))
        .select(first).stream()
        .map(row -> row.get(first))
        .collect(toList());              // []

Here the engine fails because you specified that first is Hello and world!, which is a contradiction. The second connective is or, disjunction, and it has different rules:

Unifiable<String> first = lvar();
Query.of(first.unifies("Hello").or(first.unifies("world!")))
        .select(first).stream()
        .map(row -> row.get(first))
        .collect(toList());              // ["Hello", "world!"]

Whenever the engine finds an or, it will branch and reason about the two sides separately. They are allowed to succeed or fail independently, and they may produce distinct answers that obey the rules declared in each branch. Here, it is again seen in two ways: we have a single variable, first, that we select, and only first is in the row. However, it produces two distinct answers, Hello and world!. Because the engine reasons about the branches separately, there is no contradiction between them.

Of course, we can mix the two connectives to create more complicated logic:

Unifiable<String> first = lvar();
Unifiable<String> second = lvar();
Query.of(first.unifies("Hello").and(second.unifies("world!"))
        .or(first.unifies("Goodbye").and(
                second.unifies("clauseway!").or(second.unifies("reader!"))))
        .or(first.unifies("this").and(first.unifies("fails"))))
        .select(first, second).stream()
        .map(row -> row.get(first) + " " + row.get(second))
        .collect(toList());              // ["Hello world!", "Goodbye clauseway!", "Goodbye reader!"]

A more contrived example, with branch nesting and failure. The first answer is, unsurprisingly, Hello world!, like in the previous examples. The second alternative holds two branches, Goodbye with clauseway! or reader!, and produces two answers. The fourth branch produces nothing, because first cannot be both this and fails.

A literal is a goal

Now that we have the vocabulary, we can say what the relation from last time means. Here it is again:

static External<?> cargo(AnswerSource db, Unifiable<String> trackingId, Unifiable<String> origin) {
    return Literal.relation(Cargo.class, "cargo")
            .arg("trackingId", trackingId).indexed()
            .arg("origin", origin)
            .from(db);
}

cargo returns an External, and an External is a literal: a relation's name applied to arguments, which is what Literal.relation(...).arg(...) builds. A literal is a goal like the ones above, and over a stored relation it means the disjunction of its rows: every row is one way for the relation to hold, and a row holds when each variable unifies with the value in its column. With the two cargos from Part 1 in the store, cargo(db, trackingId, origin) reads as

trackingId.unifies("ABC123").and(origin.unifies("CNHKG"))
        .or(trackingId.unifies("JKL567").and(origin.unifies("CNHGH")))

and because a literal is a goal, it composes with the connectives. Add a conjunction:

Unifiable<String> trackingId = lvar();
Unifiable<String> origin = lvar();
Query.of(cargo(db, trackingId, origin).and(trackingId.unifies("ABC123")))
        .select(origin).stream()
        .map(row -> row.get(origin))
        .collect(toList());                      // ["CNHKG"]

Only one answer is produced, because the question is equivalent to the disjunction above with trackingId.unifies("ABC123") conjoined to each branch, and the second branch cannot hold. Ask for an id nobody booked:

Query.of(cargo(db, trackingId, origin).and(trackingId.unifies("NONEXISTENT")))
        .select(origin).stream()
        .map(row -> row.get(origin))
        .collect(toList());                      // []

and neither branch can hold. That is what a literal means, and every answer you get is one you could derive this way. It is not how the engine computes it. A thousand rows and a conjunction do not become a thousand branches, and when the cost of a question matters we will come back to why. For now, the meaning is all you need.

Notice what this buys you: one language for describing data and computations over it. You no longer have to fetch data with SQL, map it into Java objects, and only then express the computation. Both are described uniformly, which opens up interesting possibilities, including choosing where the work happens: inside the JVM or in the database.

Derived relations

At some point you will want relations defined in terms of other relations. We call them derived. They are built the same way as an External, with a different terminal: .solving(Goal). Any goal will do, and we have just seen that a literal is one:

public static Literal<?> known(AnswerSource db, Unifiable<String> trackingId) {
    return Literal.relation(Cargo.class, "known")
            .arg("trackingId", trackingId)
            .solving(cargo(db, trackingId, lvar()));
}

Here we're saying that known holds whenever cargo has a trackingId. The .args are the relation's arguments, and they are all a caller of known sees. The goal under .solving is its body, and a variable the body makes for itself stays inside. We don't care about origin, so it is a fresh variable that nothing else mentions. You can use this relation the same way you'd use cargo:

// Which cargos are booked? Nothing is known, only the tracking id is asked for.
Unifiable<String> trackingId = lvar();
Query.of(known(db, trackingId))
        .select(trackingId).stream()
        .map(row -> row.get(trackingId))
        .collect(toList());                      // ["ABC123","JKL567"]

The important bit is that derived relations are never stored in an AnswerSource and are recomputed per Query. They are, however, memoized, so that repeated uses with the same arguments are reused. In logic programming this technique is called tabling, and for now it's enough to know that it's there. Note that you still need to provide the AnswerSource for the downstream cargo.

Negation

If you want to add a new cargo to the database, you'll need to make sure that its trackingId is unique. In order to do that, you need to say that known does not hold for a specific value. This is what negation means: exclude(G) holds exactly when G cannot. For example:

Unifiable<String> trackingId = lvar();
Query.of(trackingId.unifies("NONEXISTENT").and(exclude(known(db, trackingId))))
        .select(trackingId).stream()
        .map(row -> row.get(trackingId))
        .collect(toList());                      // ["NONEXISTENT"]

Here, we ask whether NONEXISTENT is known. It isn't, so the exclusion holds and the engine answers. Alternatively, we could ask:

Unifiable<String> trackingId = lvar();
Query.of(trackingId.unifies("ABC123").and(exclude(known(db, trackingId))))
        .select(trackingId).stream()
        .map(row -> row.get(trackingId))
        .collect(toList());                      // []

In this case, ABC123 is a known trackingId, so the branch fails and no answer is produced. A bound value is checked like this, at once. A variable that is still free when the exclusion is stated gets the denial attached to it as a condition, and the check happens when the variable binds. You can also exclude a unification directly:

Unifiable<String> trackingId = lvar();
Query.of(trackingId.unifies("ABC123").and(exclude(trackingId.unifies("ABC123"))))
        .select(trackingId).stream()
        .map(row -> row.get(trackingId))
        .collect(toList());                      // []

Since we're saying that trackingId is ABC123 and cannot be ABC123, this must fail, and so it does. If you play with exclusion a bit more, you may want to try this:

Unifiable<String> trackingId = lvar();
Query.of(trackingId.unifies("XYZ556").and(exclude(trackingId.unifies("JKL567").or(trackingId.unifies("ABC123")))))
        .select(trackingId).stream()
        .map(row -> row.get(trackingId))
        .collect(toList());                      // does not compile

This will not compile, and the reason is worth knowing. exclude takes a statement the engine can hold on to while it reasons: a piece of knowledge it adds to what it already knows and checks everything that follows against. A unification is one. A literal is one. A conjunction of them is one, because adding both halves can only narrow what is possible, never widen it, and that is what lets the engine settle. A disjunction is not: it opens two worlds instead of narrowing one, and there is nothing to settle on. So the engine refuses to take it directly. What it can take is a derived relation, because a derived relation is computed to completion for the question asked, its answers tabled, and a finite table of answers is knowledge the engine can hold on to and deny. Give the disjunction a name:

public static Literal<?> eitherOne(AnswerSource db, Unifiable<String> trackingId) {
    return Literal.relation(Cargo.class, "eitherOne")
            .arg("trackingId", trackingId)
            .solving(trackingId.unifies("JKL567").or(trackingId.unifies("ABC123")));
}

Unifiable<String> trackingId = lvar();
Query.of(trackingId.unifies("XYZ556").and(exclude(eitherOne(db, trackingId))))
        .select(trackingId).stream()
        .map(row -> row.get(trackingId))
        .collect(toList());                      // ["XYZ556"]

This compiles and produces the expected answer.

Ignoring columns

known is a one-line derived relation over cargo, and you may be wondering whether you need it at all. Use cargo directly under exclude, with the fresh variable for the origin, the way known spelled it:

Unifiable<String> trackingId = lvar("trackingId"); // you can name lvars for a better output
Query.of(trackingId.unifies("ABC123")
            .and(exclude(cargo(db, trackingId, lvar("origin")))))
        .select(trackingId).stream()
        .map(row -> row.get(trackingId))
        .collect(toList());
        // java.lang.IllegalStateException: 
        // holds only under ∃<origin>. ¬(cargo@7a5d012c({ABC123}, <origin>)), 
        // about a name the select did not name: (<trackingId>: {ABC123}) : ∃<origin>. ¬(cargo@7a5d012c({ABC123}, <origin>)) 
        // — a reading into Java needs a row that holds outright; select the name or read it raw

This is a new kind of outcome - the engine produced an answer, but refused to hand it to Java, because it holds only under a condition. How to deal with this kind of situation is the subject of part 4 so for now, I'll translate the answer for you: trackingId is ABC123 if there is some origin for which there is no cargo with trackingId=ABC123. There are a lot of origins like that: USNYC, DEHAM, and in fact every string except CNHKG, the one that actually sits next to ABC123 in the row. This tells us that the model specifies something different from "I don't care about this column". It says: "there is some value for which the row exists". The difference is visible here because it's excluded - "there is some value for which the row doesn't exist".

What you meant was "no row with this id, whatever its origin". The engine has a marker for exactly that, ignored():

Unifiable<String> trackingId = lvar();
Query.of(trackingId.unifies("ABC123")
            .and(exclude(cargo(db, trackingId, ignored()))))
        .select(trackingId).stream()
        .map(row -> row.get(trackingId))
        .collect(toList());                      // []

An ignored() column is not a variable of the question at all. The literal's answers are a set over the columns that remain, and under exclude the denial reads the way you meant it. Outside a negation the two spellings differ only in how often an answer repeats, which is why nothing in the sections above could show you the difference.

So ignored() is a shortcut: it writes the one-line derived relation for you, at the place you use the literal, and that is all it is. Inside a derived relation you do not need it. Only the .args are visible from outside, so a fresh lvar() for a column the body does not care about stays inside, and known is right as it was written. Where you need the shortcut is a stored literal standing under exclude on its own, with no derived relation around it to keep the column inside, as in the example above. Spell that column ignored(), or write the relation.

Where this leads

That is all the runway. Connectives, a relation written over another, and a denial that means what it says are enough to write a rule that does real work.

The next part writes one: plannedHandling, the handling a cargo's itinerary expects at each step. Ask it with the step bound and it says what should happen next. Ask it with an event bound and it says which step the event was. One rule, both directions, and that is the point of declaring relations instead of writing lookups.