# Lesson 7.1: Patterns as constraints

## [](#_introduction_to_patterns)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.

```typeql
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,
};
```

```typeql
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;
```

```typeql
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;
```

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

```typeql
$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)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](../7.3-logical-operators/index.md).)

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:

1.  `$book` owns `"The Complete Calvin and Hobbes"`.
    
2.  `"The Complete Calvin and Hobbes"` is of type `title`.
    
3.  `$user` owns `"Giovanni Beard"`.
    
4.  `"Giovanni Beard"` is of type `name`.
    
5.  `$review` owns `$score`.
    
6.  `$score` is of type `score`.
    
7.  `$book` and `$review` plays roles in the same `rating` relation.
    
8.  `$execution` has the role `action`.
    
9.  `$user` plays a role in `$execution`.
    
10.  `$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.

```typeql
$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](../../3-reading-data/3.2-fetching-polymorphic-data/index.md).

Exercise

We encountered the following Fetch query in [Lesson 3.5](../../3-reading-data/3.5-query-validation/index.md), 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.

```typeql
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

```typeql
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](../../3-reading-data/3.2-fetching-polymorphic-data/index.md), which retrieves the details of any book that a particular user has interacted with via any kind of system action they performed.

```typeql
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)Pattern validation

We have seen in Lessons [3.5](../../3-reading-data/3.5-query-validation/index.md) and [4.5](../../4-writing-data/4.5-data-validation/index.md) 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.

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

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

We encountered this invalid query in [Lesson 4.5](../../4-writing-data/4.5-data-validation/index.md). 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.

[7\. Understanding query patterns](../index.md) [Relation patterns](../7.2-relation-patterns/index.md)

[Edit on GitHub](https://github.com/typedb/typedb-docs/edit/3.x-development/academy/modules/ROOT/pages/7-understanding-query-patterns/7.1-patterns-as-constraints.adoc) Edit this page on GitHub.