Lesson 7.1: Patterns as constraints

Introduction to patterns

TypeQL uses pattern matching as the basis for all data queries. We have seen in previous lessons how almost all queries have a match clause. The content of a match clause is a pattern, which comprises any number of consecutive statements and specifies what data in the database should be matched. Subsequent clauses in a query then determine the action that should be taken for each match found, for instance retrieving data from each match with a fetch clause, inserting data for each match with an insert clause, or deleting data from each match with a delete clause. Consider the following queries, each of a different kind: Fetch, Insert, Delete, and Update respectively, but with identical match clauses.

match
$book has title "The Complete Calvin and Hobbes";
$user has name "Lorenzo Nixon";
$review has score $score;
($book, $review);
$execution ($user, action: $review);
fetch
$execution: timestamp;

match
$book has title "The Complete Calvin and Hobbes";
$user has name "Lorenzo Nixon";
$review has score $score;
($book, $review);
$execution ($user, action: $review);
insert
$review has verified true;

match
$book has title "The Complete Calvin and Hobbes";
$user has name "Lorenzo Nixon";
$review has score $score;
($book, $review);
$execution ($user, action: $review);
delete
$review isa review;
$rating isa rating;
$execution isa action-execution;

match
$book has title "The Complete Calvin and Hobbes";
$user has name "Lorenzo Nixon";
$review has score $score;
($book, $review);
$execution ($user, action: $review);
delete
$review has $score;
insert
$review has score 10;

Each of them has the same pattern in the match clause.

$book has title "The Complete Calvin and Hobbes";
$user has name "Lorenzo Nixon";
$review has score $score;
($book, $review);
$execution ($user, action: $review);

This pattern matches reviews of The Complete Calvin and Hobbes by the user Lorenzo Nixon. Each query then performs a different action for the review(s) matched:

The Fetch query returns the timestamp of the review’s submission.
The Insert query marks the review as verified.
The Delete query removes the review.
The Update query changes the score given by the review.

Understanding how to construct patterns and how they are resolved by TypeDB is necessary for all kinds of data queries, and thus the key to building more expressive queries.

Constraint satisfaction

Every pattern is equivalent to a list of constraints that must be simultaneously satisfied. Let’s consider the previous pattern. It represents several constraints about the terms involved, where a term can be either a variable or a literal:

$book owns "The Complete Calvin and Hobbes".
"The Complete Calvin and Hobbes" is of type title.
$user owns "Lorenzo Nixon".
"Lorenzo Nixon" is of type name.
$review owns $score.
$score is of type score.
$book and $review plays roles in the same relation.
$execution has the role action.
$user plays a role in $execution.
$review plays action in $execution.

In TypeDB 2.x, the match clause of all queries uses all-or-nothing pattern matching, meaning that every constraint must be satisfied simultaneously. Syntax for optional pattern elements will be introduced in TypeDB 3.0, which will allow some constraints to be matched only if possible. To learn more about this and other powerful new features, see the TypeDB 3.0 roadmap.

The types of $book, $user, and $review are not explicitly specified in the pattern, but we have previously seen how TypeDB is able to infer their types regardless. This is done by solving the pattern as a constraint satisfaction problem.

Let’s examine the constraints and attempt to determine the type of $user. We only know two things about $user: constraint (3) tells us that it owns "Lorenzo Nixon", and constraint (9) tells us that it plays a role in $execution. This doesn’t seem like enough to work with, but we can solve the type of $user by combining these constraints with others.

Constraint (4) tells us that "Lorenzo Nixon" must be of type name. By combining this with constraint (3), we can infer that $user must be of a type that owns name. Examining the schema, there are five types that do: user, contributor, place (and its subtypes), company (and its subtypes), and promotion.

Meanwhile, constraint (8) tells us that $execution has the role action. Examining the schema, there is only one relation type with a role of that name: action-execution. Combining this with constraint (9) means that $user must be of a type that plays one of its roles, either action-execution:action or action-execution:executor. Examining the schema again, there are four types that play one of these roles: user, order, login, and review.

Finally, we know that $user must be one of types user, contributor, place, company, or promotion, and that it must also be one of types user, order, login, or review. As a result, there is only one possible type for $user, and that is of course user! This fact might seem obvious to us, but this is only because we have named the variables sensibly. If we gave them meaningless names instead, it would be much harder to guess the type of each variable.

$a has title "The Complete Calvin and Hobbes";
$b has name "Lorenzo Nixon";
$c has score $d;
($a, $c);
$e ($b, action: $c);

Thus, in order to determine the return types of variables in a query, TypeDB solves each pattern as a constraint satisfaction problem, in which each statement captures one or more constraints. This is the process of type inference. In this example, $user only had a single possible return type, but we have previously seen queries in which variables have multiple possible return types, notable in Lesson 3.2.

Exercise

We encountered the following Fetch query in Lesson 3.5, which retrieves the IDs of orders being sent to a city other than the city of the user that placed the order. The role names have been omitted now, as they are actually unnecessary for this particular query to be interpreted correctly.

match
($user, $user-city) isa locating;
($order, $user) isa action-execution;
($order, $destination) isa delivery;
($destination, $destination-city) isa locating;
$user-city isa city;
$destination-city isa city;
not { $destination-city is $user-city; };
fetch
$order: id;

By identifying constraints present in the query and comparing them to the bookstore schema, determine the return type(s) of $destination.

Schema

define

book sub entity,
    abstract,
    owns isbn-13 @key,
    owns isbn-10 @unique,
    owns title,
    owns page-count,
    owns genre,
    owns price,
    plays contribution:work,
    plays publishing:published,
    plays promotion-inclusion:item,
    plays order-line:item,
    plays rating:rated,
    plays recommendation:recommended;

hardback sub book,
    owns stock;

paperback sub book,
    owns stock;

ebook sub book;

contributor sub entity,
    owns name,
    plays contribution:contributor,
    plays authoring:author,
    plays editing:editor,
    plays illustrating:illustrator;

company sub entity,
    abstract,
    owns name;

publisher sub company,
    plays publishing:publisher;

courier sub company,
    plays delivery:deliverer;

publication sub entity,
    owns year,
    plays publishing:publication,
    plays locating:located;

user sub entity,
    owns id @key,
    owns name,
    owns birth-date,
    plays action-execution:executor,
    plays locating:located,
    plays recommendation:recipient;

order sub entity,
    owns id @key,
    owns status,
    plays order-line:order,
    plays action-execution:action,
    plays delivery:delivered;

promotion sub entity,
    owns code @key,
    owns name,
    owns start-timestamp,
    owns end-timestamp,
    plays promotion-inclusion:promotion;

review sub entity,
    owns id @key,
    owns score,
    owns verified,
    plays rating:review,
    plays action-execution:action;

login sub entity,
    owns success,
    plays action-execution:action;

address sub entity,
    owns street,
    plays delivery:destination,
    plays locating:located;

place sub entity,
    abstract,
    owns name,
    plays locating:located,
    plays locating:location;

city sub place;

state sub place;

country sub place;

contribution sub relation,
    relates contributor,
    relates work;

authoring sub contribution,
    relates author as contributor;

editing sub contribution,
    relates editor as contributor;

illustrating sub contribution,
    relates illustrator as contributor;

publishing sub relation,
    relates publisher,
    relates published,
    relates publication;

promotion-inclusion sub relation,
    relates promotion,
    relates item,
    owns discount;

order-line sub relation,
    relates order,
    relates item,
    owns quantity,
    owns price;

rating sub relation,
    relates review,
    relates rated;

action-execution sub relation,
    relates action,
    relates executor,
    owns timestamp;

delivery sub relation,
    relates deliverer,
    relates delivered,
    relates destination;

locating sub relation,
    relates located,
    relates location;

recommendation sub relation,
    relates recommended,
    relates recipient;

isbn sub attribute, abstract, value string;
isbn-13 sub isbn;
isbn-10 sub isbn;
title sub attribute, value string;
page-count sub attribute, value long;
genre sub attribute, value string;
stock sub attribute, value long;
price sub attribute, value double;
discount sub attribute, value double;
id sub attribute, value string;
code sub attribute, value string;
name sub attribute, value string;
birth-date sub attribute, value datetime;
street sub attribute, value string;
year sub attribute, value long;
quantity sub attribute, value long;
score sub attribute, value long;
verified sub attribute, value boolean;
timestamp sub attribute, value datetime;
start-timestamp sub attribute, value datetime;
end-timestamp sub attribute, value datetime;
status sub attribute, value string, regex "^(paid|dispatched|delivered|returned|canceled)$";
success sub attribute, value boolean;

rule review-verified-by-purchase:
    when {
        ($review, $product) isa rating;
        ($order, $product) isa order-line;
        ($user, $review) isa action-execution, has timestamp $review-time;
        ($user, $order) isa action-execution, has timestamp $order-time;
        $review-time > $order-time;
    } then {
        $review has verified true;
    };

rule review-unverified:
    when {
        $review isa review;
        not { $review has verified true; };
    } then {
        $review has verified false;
    };

rule book-recommendation-by-genre:
    when {
        $user isa user;
        $liked-book isa book;
        {
            ($user, $order) isa action-execution;
            ($order, $liked-book) isa order-line;
        } or {
            ($user, $review) isa action-execution;
            ($review, $liked-book) isa rating;
            $review has score >= 7;
        };
        $new-book isa book;
        not { {
            ($user, $order) isa action-execution;
            ($order, $new-book) isa order-line;
        } or {
            ($user, $review) isa action-execution;
            ($review, $new-book) isa rating;
        }; };
        $liked-book has genre $shared-genre;
        $new-book has genre $shared-genre;
        not { {
            $shared-genre == "fiction";
        } or {
            $shared-genre == "nonfiction";
        }; };
    } then {
        (recommended: $new-book, recipient: $user) isa recommendation;
    };

rule book-recommendation-by-author:
    when {
        $user isa user;
        $liked-book isa book;
        {
            ($user, $order) isa action-execution;
            ($order, $liked-book) isa order-line;
        } or {
            ($user, $review) isa action-execution;
            ($review, $liked-book) isa rating;
            $review has score >= 7;
        };
        $new-book isa book;
        not { {
            ($user, $order) isa action-execution;
            ($order, $new-book) isa order-line;
        } or {
            ($user, $review) isa action-execution;
            ($review, $new-book) isa rating;
        }; };
        ($liked-book, $shared-author) isa authoring;
        ($new-book, $shared-author) isa authoring;
    } then {
        (recommended: $new-book, recipient: $user) isa recommendation;
    };

rule order-line-total-retail-price:
    when {
        ($order) isa action-execution, has timestamp $order-time;
        $line ($order, $item) isa order-line;
        not {
            ($promotion, $item) isa promotion-inclusion;
            $promotion has start-timestamp <= $order-time,
                has end-timestamp >= $order-time;
        };
        $item has price $retail-price;
        $line has quantity $quantity;
        ?line-total = $quantity * $retail-price;
    } then {
        $line has price ?line-total;
    };

rule order-line-total-discounted-price:
    when {
        ($order) isa action-execution, has timestamp $order-time;
        $line ($order, $item) isa order-line;
        ($best-promotion, $item) isa promotion-inclusion, has discount $best-discount;
        $best-promotion has start-timestamp <= $order-time,
            has end-timestamp >= $order-time;
        not {
            ($other-promotion, $item) isa promotion-inclusion, has discount > $best-discount;
            $other-promotion has start-timestamp <= $order-time,
                has end-timestamp >= $order-time;
        };
        $item has price $retail-price;
        ?discounted-price = round(100 * $retail-price * (1 - $best-discount)) / 100;
        $line has quantity $quantity;
        ?line-total = $quantity * ?discounted-price;
    } then {
        $line has price ?line-total;
    };

rule transitive-location:
    when {
        (location: $parent-place, located: $child-place) isa locating;
        (location: $child-place, located: $x) isa locating;
    } then {
        (location: $parent-place, located: $x) isa locating;
    };

Answer

The only possible return type for $destination is address, as it is the only type that plays a role in both delivery and locating.

We encountered the following Fetch query in Lesson 3.2, which retrieves the details of any book that a particular user has interacted with via any kind of system action they performed.

match
$user isa user, has id "u0008";
$book isa book;
(executor: $user, action: $action) isa action-execution;
($book, $action) isa relation;
fetch
$book: isbn, title;

As before, determine the return type(s) of $action.

Answer

The possible return types for $action are order and reivew, as they are the types that play both action-execution:action, as well as a role in a relation in which book also plays a role.

Pattern validation

We have seen in Lessons 3.5 and 4.5 that TypeDB validates queries, both to retrieve and to modify data. This is done by resolving the query’s patterns via type inference. Previously in this lesson, we have seen how TypeDB infers return types for each variable in a pattern. Now consider the following Fetch query.

match
$x has id $id;
($x, $y, $z) isa publishing;
fetch
$x: attribute;

The types that own id are user, order, and review, but the types that play roles in publishing are book (and its subtypes), publisher, and publication. This means there are no possible types for $x, as no type has both necessary capabilities. When solving a pattern’s constraints, a solution requires a type for every variable, much like a set of simultaneous equations. If there is no possible return type for any single variable, then there are no solutions for the entire pattern. As a result, this query could not possibly return any data, and so TypeDB returns an error. This validation is performed for patterns in both read queries, as we have just seen, and in write queries, as in the following example.

match
$odyssey isa ebook, has isbn "9780393634563";
insert
$odyssey has stock 20;

We encountered this invalid query in Lesson 4.5. The problem here is that ebook does not own stock. This highlights an additional consideration. If we consider just the pattern in the match clause, it is perfectly well-formed. It is only when we combine it with the pattern in the insert clause that a problem occurs. The insert and delete clauses of Insert, Delete, and Update queries also contain patterns, in the same way as match clauses. When validating a write query with multiple patterns, TypeDB validates those patterns in conjunction, so their constituent constraints must all be solved simultaneously.