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.


select takes at least three arguments:

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))
         @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


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))
-> NIL
: (? (select (@Item) ((nr +Item (1 . 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 +Links or +Joints.

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 #2 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
         @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: