abu@software-lab.de

# The 'select' Predicate

(c) Software Lab. Alexander Burger

The Pilog select/3 predicate is rather complex, and quite different from other predicates. This document tries to explain it in detail, and shows some typical use cases.

- Syntax
- First Example
- Unification Variables
- Generator Clauses
  - B-Tree Stepping
  - Interaction of Generator Clauses
  - Combined Indexes
  - Indirect Object Associations
  - Nested Pilog Queries
- Filter Clauses
  - A Little Report
  - Filter Predicates

## Syntax

`select` takes at least three arguments:

- A list of unification variables,
- a list of generator clauses
- and an arbitrary number of filter clauses

We will describe these arguments in the following, but demonstrate them first on a concrete example.

## First Example

The examples in this document will use the demo application in "app/*.l" (see also "A Minimal Complete Application"). To get an interactive prompt, start it as

    $ pil app/main.l -main +
    :

As ever, you can terminate the interpreter by hitting `Ctrl-D`.

For a first, typical example, let's write a complete call to solve that returns a list of articles with numbers between 1 and 4, which contain "Part" in their description, and have a price less than 100:

    (let (Nr (1 . 4)  Nm Part  Pr '(NIL . 100.00))
       (solve
          (quote
             @Nr Nr
             @Nm Nm
             @Pr Pr
             (select (@Item)
                ((nr +Item @Nr) (nm +Item @Nm) (pr +Item @Pr))
                   (range @Nr @Item nr)
                   (part @Nm @Item nm)
                   (range @Pr @Item pr) ) )
          @Item ) )

This expression will return, with the default database setup of "app/init.l", a list of exactly one item `({3-2})`, the item with the number 2.

The `let` statement assigns values to the search parameters for number `Nr`, description `Nm` and price `Pr`. The Pilog query (the first argument to `solve`) passes these values to the Pilog variables `@Nr`, `@Nm` and `@Pr`. Ranges of values are always specified by cons pairs, so `(1 . 4)` includes the numbers 1 through 4, while `(NIL . 100.00)` includes prices from minus infinite up to one hundred.

The list of unification variables is

       (@Item)

The list of generator clauses is

          ((nr +Item @Nr) (nm +Item @Nm) (pr +Item @Pr))

The filter clauses are

             (range @Nr @Item nr)
             (part @Nm @Item nm)
             (range @Pr @Item pr)

## Unification Variables

As stated above, the first argument to `select` should be a list of variables. These variables communicate values (via `unify`) from the `select` environment to the enclosing Pilog environment.

The first variable in this list (`@Item` in the above example) is mandatory, it takes the direct return value of `select`. Additional optional variables may be unified by clauses in the body of `select`, and return further values.

## Generator Clauses

The second argument to `select` is a list of "generator clauses". Each of these clauses specifies some kind of database B-Tree `+index`, to be traversed by `select`, step by step, where each step returns a suitable single database object. In the simplest case, they consist like here just of a relation name (e.g. `nr`), a class (e.g. `+Item`), an optional hook specifier (not in this example), and a pattern (values or ranges, e.g. (1 . 4) or "Part").

The generator clauses are the core of 'select'. In some way, they behave analog to `or/2`, as each of them generates a sequence of values. However, the generator clauses behave different, as they will not generate an exhaustive set of values upon backtracking, one after the other, where the next gets its turn when the previous one is exhausted. Instead, all clauses will generate their values quasi-parallel, with a built-in optimization so that successful clauses will be called with a higher probability. "Successful" means that the returned values successfully pass `select`'s filter clauses.

### B-Tree Stepping

In its basic form, a generator clause is equivalent to the `db/3` predicate, stepping through a single B-Tree. The clause

    (nr +Item @Nr)

generates the same values as would be produced by a stand-alone Pilog clause

    (db nr +Item @Nr @Item)

as can be seen in the following two calls:

    : (? (db nr +Item (1 . 4) @Item))
     @Item={3-1}
     @Item={3-2}
     @Item={3-3}
     @Item={3-4}
    -> NIL
    : (? (select (@Item) ((nr +Item (1 . 4)))))
     @Item={3-1}
     @Item={3-2}
     @Item={3-3}
     @Item={3-4}
    -> NIL

### Interaction of Generator Clauses

`select` is mostly useful if more than one generator clause is involved. The tree search parameters of all clauses are meant to form a logical `AND`. Only those objects should be returned, for which all search parameters (and the associated filter clauses) are valid. As soon as one of the clauses finishes stepping through its database (sub)tree, the whole call to `select` will terminate, because further values returned from other generator clauses cannot be part of the result set.

Therefore, `select` would find all results most quickly if it could simply call only the generator clause with the smallest (sub)tree. Unfortunately, this is usually not known in advance. It depends on the distribution of the data in the database, and on the search parameters to each generator clause.

Instead, `select` single-steps each generator clause in turn, in a round-robin scheme, applies the filter clauses to each generated object, and re-arranges the order of generator clauses so that the more successful clauses will be preferred. This process usually converges quickly and efficiently.

### Combined Indexes

A generator clause can also combine several (similar) indexes into a single one. Then the clause is written actually as a list of clauses.

For example, a generator clause to search for a customer by phone number is

    (tel +CuSu @Tel)

If we want to search for a customer without knowing whether a given number is a normal or a mobile phone number, then a combined generator clause searching both index trees could look like

    ((tel +CuSu @Tel  mob +CuSu @Tel))

The generator will first traverse all matching entries in the `+Ref` tree of the `tel` relation, and then, when these are exhausted, all matching entries in the `mob` index tree.

### Indirect Object Associations

But generator clauses are not limited to the direct B-Tree interaction of `db/3`. They can also traverse trees of associated objects, and then follow `+Link` / `+Joint` relations, or tree relations like `+Ref` to arrive at database objects with a type suitable for return values from `select`.

To locate appropriate objects from associated objects, the generator clause can contain - in addition to the standard relation/class/pattern specification (see Generator Clauses above) - an arbitrary number of association specifiers. Each association specifier can be

1. A symbol. Then a `+Link` or `+Joint` will be followed, or a `+List` of those will be traversed to locate appropriate objects.
2. A list. Then this list should hold a relation and a class (and an optional hook) which specify some B-Tree `+index` to be traversed to locate appropriate objects.

In this way, a single generator clause can cause the traversal of a tree of object relations to generate the desired sequence of objects. An example can be found in "app/gui.l", in the 'choOrd' function which implements the search dialog for `+Ord` (order) objects. Orders can be searched for order number and date, customer name and city, item description and supplier name:

    (select (@@)
       ((nr +Ord @Nr) (dat +Ord @Dat)
          (nm +CuSu @Cus (cus +Ord))
          (ort +CuSu @Ort (cus +Ord))
          (nm +Item @Item (itm +Pos) ord)
          (nm +CuSu @Sup (sup +Item) (itm +Pos) ord) )

While `(nr +Ord @Nr)` and `(dat +Ord @Dat)` are direct index traversals, `(nm +CuSu @Cus (cus +Ord))` iterates the `nm` (name) index of customers/suppliers `+CuSu`, and then follows the `+Ref` `+Link` of the `cus` relation to the orders. The same applies to the search for city names via `ort`.

The most complex example is `(nm +CuSu @Sup (sup +Item) (itm +Pos) ord)`, where the supplier name is searched in the `nm` tree of `+CuSu`, then the `+Ref` tree `(sup +Item)` tree is followed to locate items of that supplier, then all positions for those items are found using `(itm +Pos)`, and finally the `ord` `+Joint` is followed to arrive at the order object(s).

### Nested Pilog Queries

In the most general case, a generator clause can be an arbitrary Pilog query. Often this is a query to a database on a remote machine, using the `remote/2` predicate, or some other resource not accessible via database indexes, like iterating a `+List` of `+Link`s or `+Joint`s.

Syntactically, such a generator clause is recognized by the fact that its CAR is a Pilog variable to denote the return value.

The second argument is a list of Pilog variables to communicate values (via `unify`) from the surrounding `select` environment.

The third argument is the actual list of clauses for the nested query.

Finally, an arbitrary number of association specifiers may follow, as described in the Indirect Object Associations section.

We can illustrate this with a somewhat useless (but simple) example, which replaces the standard generators for item number and supplier name

    (select (@Item)
       (
          (nr +Item @Nr)
          (nm +CuSu @Sup (sup +Item))
       )
       ...

with the equivalent form

    (select (@Item)
       (
          (@A (@Nr) ((db nr +Item @Nr @A)))
          (@B (@Sup) ((db nm +CuSu @Sup @B)) (sup +Item))
       )

That is, a query with the `db/3` tree iteration predicate is used to generate appropriate values.

## Filter Clauses

The generator clauses produce - independent from each other - lots of objects, which match the patterns of individual generator clauses, but not necessarily the desired result set of the total `select` call. Therefore, the filter clauses are needed to retain the good, and throw away the bad objects. In addition, they give feedback to the generator for optimizing its traversal priorities (as described in Generator Clauses).

`select` then collects all objects which passed through the filters into a unique list, to avoid duplicates which would otherwise appear, because most objects can be found by more than one generator clause.

Technically, the filters are normal Pilog clauses, which just happen to be evaluated in the context of `select`. Arbitrary Pilog predicates can be used, though there exist some predicates (e.g. `isa/2`, `same/3`, `bool/3`, `range/3`, `head/3`, `fold/3`, `part/3` or `tolr/3`) especially suited for that task.

### A Little Report

Assume we want to know how many pieces of item #2 were sold in the year 2007. Then we must find all `+Pos` (position) objects referring to that item and at the same time belonging to orders of the year 2007 (see the class definition for `+Pos` in "app/er.l"). The number of sold pieces is then in the `cnt` property of the `+Pos` objects.

As shown in the complete `select` below, we will hold the item number in the variable `@Nr` and the date range for the year in `@Year`.

Now, all positions referred by item #2 can be found by the generator clause

    (nr +Item @Nr (itm +Pos))

and all positions sold in 2007 can be found by

    (dat +Ord @Year pos)

However, the combination of both generator clauses

    (select (@Pos)
       ((nr +Item @Nr (itm +Pos)) (dat +Ord @Year pos)) )

will probably generate too many results, namely all positions with item #3 OR from the year 2007. Thus, we need two filter clauses. With them, the full search expression will be:

    (?
       @Nr 2                                                 # Item number
       @Year (cons (date 2007 1 1) (date 2007 12 31))        # Date range 2007
       (select (@Pos)
          ((nr +Item @Nr (itm +Pos)) (dat +Ord @Year pos))   # Generator clauses
          (same @Nr @Pos itm nr)                             # Filter item number
          (range @Year @Pos ord dat) ) )                     # Filter order date

For completeness, let's calculate the total count of sold items:

    (let Cnt 0     # Counter variable
       (pilog
          (quote
             @Nr 2
             @Year (cons (date 2007 1 1) (date 2007 12 31))
             (select (@Pos)
                ((nr +Item @Nr (itm +Pos)) (dat +Ord @Year pos))
                (same @Nr @Pos itm nr)
                (range @Year @Pos ord dat) ) )
          (inc 'Cnt (get @Pos 'cnt)) )  # Increment total count
       Cnt )  # Return count

### Filter Predicates

As mentioned under Filter Clauses, some predicates exists mainly for `select` filtering.

Some of these predicates are of general use: `isa/2` can be used to check for a type, `same/3` checks for a definite value, `bool/3` looks if the value is non-`NIL`. These predicates are rather independent of the `+relation` type.

`range/3` checks whether a value is within a given range. This could be used with any `+relation` type, but typically it will be used for numeric (`+Number`) or time ( `+Date` and `+Time`) relations.

Other predicates make only sense in the context of a certain `+relation` type:

- `head/3` is mainly intended for `(+Key +String)` or `(+Ref +String)` relations,
- `fold/3` is useful for `(+Fold +Ref +String)` relations,
- `part/3` for `(+Fold +Idx +String)` relations, and
- `tolr/3` for `(+Sn +Idx +String)` relations.