Cardinality and List Length

Last revised 01/18/2017. Send comments to A. W. Crapo


SADL Version 3 introduces types Lists, which can have a restriction on List length. List length has sometimes been confused with cardinality restrictions. The purpose of this document is to make the meaning of each, and thereby the difference, clear.

Cardinality and Qualified Cardinality

Please recall that in OWL, to which SADL models are translated, properties are first class citizens--they can exist independent of any class definitions. The following kinds of concepts can exist in a model.

  1. class--a mathematical set
  2. instance--a specific thing, which may belong to one or more sets (classes)
  3. property--a type of relationship. Properties are divided into object properties, whose values are things with identity, e.g., instances, and datatype properties, whose values are things without identity, i.e., a number, a string, a date.
  4. triple--a statement with a subject, which is normally an instance, a predicate which is a property, and an object, which is normally an instance for object properties and a primitive value for datatype properties
  5. restriction (aka property restrictions)--a constraint or restriction on the values that a property can have in triples whose subject belong to a particular class

Cardinality restrictions are a particular type of restriction and have to do with the number of triples that can exist with the restricted property for a given subject. Cardinality restrictions can specify the maximum number of triples, the minimum number of triples, or the exact number of triples allowed. In SADL syntax, examples of each are, respectively:

These cardinality restrictions are each expressed without consideration of the type of the value. Qualified cardinality restrictions add the ability to specify a cardinality restriction for each of possibly multiple kinds of values. For example

digit of Hand has exactly 1 value of type Thumb.    // a hand has 1 thumb
digit of Hand has exactly 4 value of type Finger.    // a hand has 4 fingers

One might infer from this that the total number of values of "digit" for an instance of "Hand" (cardinality) must be 5.

List Length

The length of a List can be restricted, but such restriction has nothing to do with cardinality restrictions on a class. Consider the following example.

StudentsInSection is a type of Person List length 2-18.   // StudentsInSection is a List of type Person and the length of the List can be from 2 to 18.
Teacher is a class, described by  teaches with  values of type StudentsInSection.   // teaches is a property with domain Teacher and range the previously defined type of Person List
teaches of Professor has at most 3 values.    // a professor can teach at most 3 sections, each of which is a list of between 2 and 18 students