Appendix B  O-Telos Axioms

O-Telos is the variant of Telos (originally defined by John Mylopoulos, Alex Borgida, Manolis Koubarakis and others) that is used by the ConceptBase system. This list is the complete set of pre-defined axioms of O-Telos and thus defines the semantics of a O-Telos database (without user-defined rules and constraints). The subsequent axioms are written in a first-order logic syntax but all can be converted to Datalog with negation (though there is some choice in the conversion wrt. mapping to rules or constraints).

• Axiom 1: Object identifiers are unique.
  ∀  o,x₁,n₁,y₁,x₂,n₂,y₂  P(o,x₁,n₁,y₁) ∧ P(o,x₂,n₂,y₂) ⇒
  (x₁=x₂) ∧ (n₁=n₂) ∧ (y₁=y₂)
• Axiom 2: The name of individual objects is unique.
  ∀  o₁,o₂,n  P(o₁,o₁,n,o₁) ∧ P(o₂,o₂,n,o₂) ⇒ (o₁=o₂)
• Axiom 3: Names of attributes are unique in conjunction with the source object.
  ∀  o₁,x,n,y₁,o₂,y₂  P(o₁,x,n,y₁) ∧ P(o₂,x,n,y₂) ⇒ (o₁=o₂) ∨ (n=in) ∨ (n=isa)
• Axiom 4: The name of instantiation and specialization objects (in, isa) is unique in conjunction with source and destination objects.
  ∀  o₁,x,n,y,o₂  P(o₁,x,n,y) ∧ P(o₂,x,n,y) ∧ ((n = in) ∨ (n = isa)) ⇒ (o₁=o₂)
• Axioms 5,6,7,8: Solutions for the predicates In, Isa, and A are derived from the object base.
  ∀  o,x,c  P(o,x,in,c) ⇒ In(x,c)
  ∀  o,c,d  P(o,c,isa,d) ⇒ Isa(c,d)
  ∀  o,x,n,y,p,c,m,d  P(o,x,n,y) ∧ P(p,c,m,d) ∧ In(o,p) ⇒ AL(x,m,n,y)
  ∀  x,m,n,y  AL(x,m,n,y) ⇒ A(x,m,y)
• Axiom 9: An object x may not neglect an attribute definition in one of its classes.
  ∀  x,y,p,c,m,d  In(x,c) ∧ A(x,m,y) ∧ P(p,c,m,d) ⇒
  ∃  o,n  P(o,x,n,y) ∧ In(o,p)
• Axioms 10,11,12: The isa relation is a partial order on the object identifiers.
  ∀  c  In(c,#Obj) ⇒ Isa(c,c)
  ∀  c,d,e  Isa(c,d) ∧ Isa(d,e) ⇒ Isa(c,e)
  ∀  c,d  Isa(c,d) ∧ Isa(d,c) ⇒ (c=d)
• Axiom 13: Class membership of objects is inherited upwardly to the superclasses.
  ∀  p,x,c,d  In(x,d) ∧ P(p,d,isa,c) ⇒ In(x,c)
• Axiom 14: Attributes are "typed" by their attribute classes.
  ∀  o,x,n,y,p  P(o,x,n,y) ∧ In(o,p) ⇒ ∃  c,m,d  P(p,c,m,d) ∧ In(x,c) ∧ In(y,d)
• Axiom 15: Subclasses which define attributes with the same name as attributes of their superclasses must refine these attributes.
  ∀  c,d,a₁,a₂,m,e,f
  Isa(d,c) ∧ P(a₁,c,m,e) ∧ P(a₂,d,m,f) ⇒ Isa(f,e) ∧ Isa(a₂,a₁)
• Axiom 16: If an attribute is a refinement (subclass) of another attribute then it must also refine the source and destination components.
  ∀  c,d,a₁,a₂,m₁,m₂,e,f
  Isa(a₂,a₁) ∧ P(a₁,c,m₁,e) ∧ P(a₂,d,m₂,f) ⇒ Isa(d,c) ∧ Isa(f,e)
• Axiom 17: For any object there is always a unique "smallest" attribute class with a given label m.
  ∀  x,m,y,c,d,a₁,a₂,e,f  (In(x,c) ∧ In(x,d) ∧ P(a₁,c,m,e) ∧ P(a₂,d,m,f)
  ⇒ ∃  g,a₃,h  In(x,g) ∧ P(a₃,g,m,h) ∧ Isa(g,c) ∧ Isa(g,d))
• Axioms 18-22: Membership to the builtin classes is determined by the object’s format.
  ∀  o,x,n,y  (P(o,x,n,y) ⇔ In(o,#Obj))
  ∀  o,n  (P(o,o,n,o) ∧ (n ≠ in) ∧ (n ≠ isa) ⇔ In(o,#Indiv))
  ∀  o,x,c  (P(o,x,in,c) ∧ (o ≠ x) ∧ (o ≠ c) ⇔ In(o,#Inst))
  ∀  o,c,d  (P(o,c,isa,d) ∧ (o ≠ c) ∧ (o ≠ d) ⇔ In(o,#Spec))
  ∀  o,x,n,y  (P(o,x,n,y) ∧ (o ≠ x) ∧ (o ≠ y) ∧ (n ≠ in) ∧ (n ≠ isa) ⇔ In(o,#Attr))
• Axiom 23: Any object falls into one of the four builtin classes.
  ∀  o  In(o,#Obj) ⇒ In(o,#Indiv) ∨ In(o,#Inst) ∨ In(o,#Spec) ∨ In(o,#Attr)
• Axioms 24-28: There are five builtin classes.
  P(#Obj,#Obj,Proposition,#Obj)
  P(#Indiv,#Indiv,Individual,#Indiv)
  P(#Attr,#Obj,attribute,#Obj)
  P(#Inst,#Obj,InstanceOf,#Obj)
  P(#Spec,#Obj,IsA,#Obj)
• Axiom 29: Objects must be known before they are referenced. The operator ≼ is a (predefined) total order on the set of identifiers.
  ∀  o,x,n,y  P(o,x,n,y) ⇒ (x ≼ o) ∧ (y ≼ o)
• Axioms 30,31 (axiom schemas): For any object P(p,c,m,d) in the extensional object base we have two formulas for "rewriting" the In and A predicates. The In is mapped to a unary predicate where the class name is forming part of the predicate name and the A predicates is mapped to a binary predicate that carries the identifier of the class of the attribute in its predicate name. Internally, user-defined deductive rules that derive In and A predicates will also be rewritten accordingly. This extends the choices for static stratification.
  ∀  o  In(o,p) ⇒ In.p(o)
  ∀  o,x,n,y  P(o,x,n,y) ∧ In(o,p) ⇒ A.p(x,y)

The following axioms are taken from papers on Telos (i.e. formulated by Mylopoulos, Borgida, Koubarakis, Stanley and Greenspan): axioms 2, 3, 4, 10, 12, 13, 14. Axiom 1 is probably also in an earlier Telos paper though we could not immediately find it there. The axioms 15 and 16 are similar to the structural ISA constraint of Taxis [MBW80] for attributes. In O-Telos, we do however not inherit attributes downward to subclasses but rather constrain refined attributes at subclasses in the sense of co-variance. Moreover, attributes in O-Telos are objects as well, hence the notion of specialization is more complicated than for the Taxis case. Axiom 17 is needed to be able to uniquely match an attribution predicate to a most specific attribute. This is utilized in the compilation of logical expressions, in particular for generating triggers that only evaluate the affected logical expressions when an update occurs. The remaining axioms 18-28 are also specific to O-Telos. They define the five predefined objects in O-Telos. Axiom 29 takes care that objects cannot refer via its source/destination parts to objects that were defined later than the object itself. This virtually forbids to define an link between two objects when one of the objects is not yet defined. While this sounds natural, we need to posutlate it. Otherwise, we can’t guarantee that we can refer to any object by a name. Axioms 30 and 31 are used to transfer instantiation and attribution facts from the extensional databases to the intensional database. They have more a technical purpose in the mapping of logical expressions to Datalog.

While O-Telos has just five predefined objects and 31 predefined axioms, the ConceptBase system has many more pre-defined objects to provide a better modeling experience and for representing concepts like query classes, active rules, functions etc. They are in a way also predefined but are less essential in understanding the foundations. So, O-Telos is the foundation of ConceptBase but ConceptBase has more pre-defined constructs than those mentioned in the axioms of O-Telos.

Axiom 15 is only applicable to attribute classes, i.e. where the attribute value is an object that potentially can have instances. If the attribute value is for example a number, then ConceptBase will not enforce the axiom. We leave the formula unchanged, since classes for numbers such as Integer, are not part of the axiomatization.

ConceptBase allows to add user-defined rules and constraints. The semantics of an O-Telos database including such rules and constraints is the perfect model of the deductive database with the P(o,x,n,y) as the only extensional predicate and all axioms and user-defined rules/constraints as deductive rules. Note that integrity constraints can be rewritten to deductive rules deriving the predicate inconsistent.

This list of axioms is excerpted from M.A. Jeusfeld: Änderungskontrolle in deduktiven Objektbanken. Dissertation Universität Passau, Germany, 1992. Available as Volume DISKI-19 from INFIX-Verlag, St. Augustin, Germany or via link (in German).

Axioms 19-21 have been corrected after Christoph Radig found an example that led to the undesired instantiation of an individual object to #Inst or #Spec, respectively.