The Predicative Sublanguage CBL

 

The ConceptBase predicative language CBL [JK90] is used to express integrity constraints, deductive rules and queries. The variables inside the formulas have to be quantified and assigned to a ``type'' that limits the range of possible instantiations to the set of instances of a class. ConceptBase offers a set of literals for the predicative language defined on top of a Telos knowledge base. Usually, this knowledge base is restricted by a rollback time:

= {P(oid,x,l,y,tt) in KB | rbt during tt}

The value of the rollback time depends on the kind of formula to be processed: integrity constraints are evaluated on the current KB (rbt=Now=the smallest time interval that contains the current time), the rollback time of queries is usually provided together with the query.

The following literals provide the basic access to an O-Telos object base. Some have both an infix and a prefix notation.

1. (x in c) or In(x,c)
   The object x is an instance of class c.
2. (c isA d) or IsA(c,d)
   The object c is a specialization (subclass) of d
3. (x m y) or A(x,m,y)
   The object x has an attribute to object y and this relationship is an instance of an attribute category with label m. Structural integrity demands that the label m belongs to an attribute of a class of x.
4. Ai(x,m,p)
   The object x has an attribute p. This attribute is instance of an attribute category with label m.
5. From(p,x)
   The object p has source x.
6. To(p,y)
   The object p has destination y.
7. Label(p,l)
   The object p has label l.
8. P(p,x,l,y)
   There is an object P(p,x,l,y) in the object base at the specified rollback time.

In order to avoid ambiguity, neither in and isa nor the logical connectives and and or are allowed as attribute labels.

The next literals are second class citizens in formulas. In contrast to the above literals they cannot be assigned to classes of the Telos knowledge base. Consequently, they may only be used for testing, i.e. in a legal formula their parameters must be bound by one of the literals 1 - 8.

9.

x < y, x > y, x <= y, x >= y, x = y, x <> y
Note that x and y must be instances of Integer or Real.

10.

x == y
The objects x and y are the same.

The exact syntax of CBL is given in appendix . The types of variables (i.e. quantified identifiers) are interpreted as instantiations:

• forall x/C F
• exists x/C F

are shorthands for the untyped formulas

• forall x (x in C) ==> F
• exists x (x in C) and F

We demand that each variable is quantified exactly once inside a formula. This is no real restriction: in case of double quantification rename one of the variables. More important is a restriction similar to static type checking in programming languages that demands a strong relationship between formulas and the knowledge base.

Formula Assignment Restriction

Each constant (= arguments that are not variables) in a formula F must be the name of an existing object in the Telos knowledge base, or it is a constant of the builtin classes Integer, Real, or String. Moreover, for each attribute predicate (x m y) (or Ai(x,m,p), resp.) occuring in a formula there must be a unique attribute labelled m of one class c of x in the knowledge base.

A formula violating the first part of the restriction would make a statement about something that is not part of the KB. As an example, consider the following formula:

forall x/Emplye not (x boss Mary)

With the example KB of section 2.1, we find two errors: There are no objects with names Emplye and Mary.

There are two possible cases to violate the second part of the restriction. The first case is illustrated by an example:

forall x/Proposition y/Integer (x salary y) ==> y < 10000

In this case the classes of x, Proposition and any of its superclasses, have no attribute labelled salary. Therefore, the predicate (x salary y) cannot be assigned to an attribute of the KB. Instead, one has to specify

forall x/Employee y/Integer (x salary y) ==> y < 10000

or

forall x/Manager y/Integer (x salary y) ==> y < 10000

depending on whether the formula applies to managers or to all employees.

The second case is closely related to multiple generalization/instantiation. Suppose, we have new classes Shop, Guest and GuestEmployee:

Individual Shop in Class,SimpleClass
end 

Individual Guest in Class,SimpleClass with
      attribute
            dept: Shop
end

Individual GuestEmployee in Class,SimpleClass
                         isA Guest,Employee
end

The following formula refers to objects of class GuestEmployee and their dept attribute. The problem is that two different attributes, Employee!dept and Guest!dept, apply as candidates for the predicate (x dept PR):

forall x/GuestEmployee (x dept PR) ==> not (x in Manager)

In order to solve this ambiguity, we demand that in such cases a common subclass exists that defines an attribute dept which conforms to both definitions, e.g.

Individual Shop in Class,SimpleClass
end 

GuestEmployee with
        attribute
                dept: ShopDepartment
end 

Individual ShopDepartment in Class,SimpleClass
                                isA Shop,Department
end

A legal integrity constraint is a CBL formula that fulfills the formula assigment restriction. A legal deductive rule is a CBL formula fulfilling the same restriction and having the format:

forall x1/c1 ... forall xn/cn R ==> lit(a1,...,am)

where

• lit is a literal of type 1 to 3, and
• the variables in a1,...,am are exactly x1,...,xn

In O-Telos, rules and constraints are defined as attributes of classes. Use the category constraint for integrity constraints, and the category rule for deductive rules. The text of the formula has to be enclosed by the character `$'. The choice of the class for a rule or constraint is arbitrary (except for query classes which use the special variable 'this').

Continuing our running example, the following formula is a deductive rule that defines the boss of an Employee. Note that the variables e,m are forall-quantified.

Employee with
 rule
   BossRule : $ forall e/Employee m/Manager
                (exists d/Department 
                (e dept d) and (d head m))
                ==> (e boss m) $
 constraint
   SalaryBound : $ forall e/Employee b/Manager x,y/Integer 
                (e boss b) and (e salary x) and (b salary y) 
                   ==> x <= y $
end

The second formula is an integrity constraint that uses the boss attribute defined by the above rule. The constraint demands salaries of Employees not to excceed the salary of their boss. Note that you can define different salaries for Employees. The constraint is on each individual salary, not on the sum! Also note that the arguments of the <= literal are bound by the two literals with attribute label salary.

Regular deduction rules and integrity constraints in addition to the formula assignment condition require that in literals (x in c) c is always a constant class name. The idea of this restriction is that then all in literals (in an analogous way as attribute literals ensured by the formula assignment condition) may uniquely be mapped to so called concerned classes which serve as anchor objects for generated triggers. Formulas that do not fall into this category are called meta formulas and may use arbitrary variables (even for the second argument of in literals) bound (by quantification) to a meta variable VAR. Meta formulas allow to specify assertions involving objects from different levels and hence significantly improve flexibility of O-Telos models. An example for the usage of meta formulas can be find in the appendix where the enforcement of constraints in ER diagrams is solved in a very elegant way.

In addition to the so called select expressions !,=>,-> already introduced above for directly refering to attributes, specializations and instantiations as objects, three other basic constructors may be used within frames and assertions.

• is the counterpart of ! and denotes the target of an attribute instead of the attribute object itself, e.g. mary advises is the same as PR.
• The set valued . operator has the commonly used meaning as in paths in object-oriented models and relates an object with the set of all attribute values of a certain category, i.e. mary.dept contains both PR and R&D.
• As . can be understood as the set variant of but employing the attribute category instead of the concrete attribute label, the same holds for | (with respect to !). Thus mary|dept is the set of all attributes (as objects) that belong to category dept and have source mary.

Note, that . and | are only allowed to occur within assertions whereever classes may be interpreted as range restrictions, e.g. in quantifications or at the right hand side of in literals. The full syntax which allows combinations of all basic constructors can be found in the appendix. For illustration we just give two examples here. The first is an alternative representation for the rule above, the second could be a constraint stating that all bosses of Mary earn exactly 50.000.

1. forall e/Employee m/Manager (m in e.dept.head) ==> (e boss m).
2. forall b/Mary.dept.head (b salary 50000)