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  "Giovanni Beard";
$review has score $score;
($book, $review);
$execution links ($user, action: $review);
fetch {
  "timestamp": $execution.timestamp,
};

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

match
$book has title "The Complete Calvin and Hobbes";
$user has name  "Giovanni Beard";
$review has score $score;
($book, $review);
$execution links ($user, action: $review);
delete
$review;
$execution;

match
$book has title "The Complete Calvin and Hobbes";
$user has name  "Giovanni Beard";
$review has score $score;
($book, $review);
$execution links ($user, action: $review);
delete
has $score of $review;
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  "Giovanni Beard";
$review has score $score;
($book, $review);
$execution links ($user, action: $review);

This pattern matches reviews of The Complete Calvin and Hobbes by the user Giovanni Beard. 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. (Note: some patterns have special semantics that modify this behaviour, like or, not, and try - see Lesson 7.3.)

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 "Giovanni Beard".
"Giovanni Beard" is of type name.
$review owns $score.
$score is of type score.
$book and $review plays roles in the same rating relation.
$execution has the role action.
$user plays a role in $execution.
$review plays action in $execution.

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 "Giovanni Beard", 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 "Giovanni Beard" 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 "Giovanni Beard";
$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
locating ($user, $user-city);
action-execution ($order, $user);
delivery ($order, $destination);
locating ($destination, $destination-city);
$user-city isa city;
$destination-city isa city;
not { $destination-city is $user-city; };
fetch {
  "order-id": $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

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

entity hardback sub book,
    owns stock;

entity paperback sub book,
    owns stock;

entity ebook sub book;

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

entity company @abstract,
    owns name;

entity publisher sub company,
    plays publishing:publisher;

entity courier sub company,
    plays delivery:deliverer;

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

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

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

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

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

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

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

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

entity city sub place;

entity state sub place;

entity country sub place;

relation contribution,
    relates contributor,
    relates work;

relation authoring sub contribution,
    relates author as contributor;

relation editing sub contribution,
    relates editor as contributor;

relation illustrating sub contribution,
    relates illustrator as contributor;

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

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

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

relation rating,
    relates review,
    relates rated;

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

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

relation locating,
    relates located,
    relates location;

relation recommendation,
    relates recommended,
    relates recipient;

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

# TODO: Change to check
fun is_review_verified_by_purchase($review: review) -> { order }:
  match
    ($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;
  return { $order };

fun book_recommendations_for($user: user) -> {book}:
  match
    $new-book isa book;
    {
        let $new-book in book_recommendations_by_author($user);
    } or {
        let $new-book in book_recommendations_by_genre($user);
    };
  return { $new-book };

fun book_recommendations_by_genre($user: user) -> { book }:
match
    $user isa user;
    $liked-book isa book;
    {
        ($user, $order-for-liked) isa action-execution;
        ($order-for-liked, $liked-book) isa order-line;
    } or {
        ($user, $review-for-liked) isa action-execution;
        ($review-for-liked, $liked-book) isa rating;
        $review-for-liked has score >= 7;
    };
    $new-book isa book;
    not { {
        ($user, $order-for-new) isa action-execution;
        ($order-for-new, $new-book) isa order-line;
    } or {
        ($user, $review-for-new) isa action-execution;
        ($review-for-new, $new-book) isa rating;
    }; };
    $liked-book has genre $shared-genre;
    $new-book has genre $shared-genre;
    not { {
        $shared-genre == "fiction";
    } or {
        $shared-genre == "nonfiction";
    }; };
  return { $new-book };

fun book_recommendations_by_author($user: user) -> { book }:
  match
    $user isa user;
    $liked-book isa book;
    {
        ($user, $order-for-liked) isa action-execution;
        ($order-for-liked, $liked-book) isa order-line;
    } or {
        ($user, $review-for-liked) isa action-execution;
        ($review-for-liked, $liked-book) isa rating;
        $review-for-liked has score >= 7;
    };
    $new-book isa book;
    not { {
        ($user, $order-for-new) isa action-execution;
        ($order-for-new, $new-book) isa order-line;
    } or {
        ($user, $review-for-new) isa action-execution;
        ($review-for-new, $new-book) isa rating;
    }; };
    ($liked-book, $shared-author) isa authoring;
    ($new-book, $shared-author) isa authoring;
  return { $new-book };

fun order_line_best_price($line: order-line) -> { double }:
  match
    ($order) isa action-execution, has timestamp $order-time;
    $line isa order-line, links ($order, $item);
    $item has price $retail-price;
    let $time_value = $order-time;
    let $best-discount = best_discount_for_item($item, $time_value);
    let $discounted-price = round(100 * $retail-price * (1 - $best-discount)) / 100;
    $line has quantity $quantity;
    let $line-total = $quantity * $discounted-price;
  return { $line-total };

fun best_discount_for_item($item: book, $order-time: datetime) -> double:
  match
    {
        $inclusion isa promotion-inclusion,
            links ($promotion, $item),
            has discount $discount-attr;
        $promotion has start-timestamp <= $order-time,
            has end-timestamp >= $order-time;
        let $discount = $discount-attr;
    } or {
        let $discount = 0.0; # default
    };
return max($discount);

fun transitive_places($place: place) -> { place }:
  match
    {
      locating (located: $place, location: $parent);
    } or {
      locating (located: $place, location: $middle);
      let $parent in transitive_places($middle);
    };
  return { $parent };

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;
action-execution (executor: $user, action: $action);
($book, $action);
fetch {
  "isbn": [$book.isbn],
  "title": $book.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;

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. 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.

Services

Platform

Tools

Why TypeDB?

Try cloud free

Pricing and plans

Learn

Content

Lesson 7.1: Patterns as constraints

Introduction to patterns

Constraint satisfaction

Pattern validation