Subsumption relationship

Subsumption is a powerful mechanism for comparing alternative representations. When a representation subsumes another, the entities represented by the latter can also be represented by the former representation, without any data loss.

A subsumption relationship (denoted '≤') is defined over sorts.

• A disjunctive sort naturally defines a subsumption relationship over sorts: a disjunctive sort subsumes each component sort. Any individual of a disjunctive sort is necessarily an individual of one of the component sorts. For example, the sort of points and line segments subsumes both the sort of points and the sort of line segments, because every point (as well as every line segment) is also an individual of the sort of points and line segments.
  Given two sorts a and b: a ≤ b ⇔ a + b = b
• This subsumption relationship is extended to attribute sorts: an attribute sort subsumes its base sort. For example, the sort of colored labels subsumes the sort of labels: every label is also an individual of the sort of colored labels, omitting the color attribute.
  Given two sorts a and b: a ≤ a ^ b

The extension of the subsumption relationship to attribute sorts implies that the specification of an attribute form to an individual of an attribute sort is optional. That is, the attribute form may be empty. As a result, an attribute relationship for sorts is denoted a semi-conjunctive relationship.

Many representational formalisms consider a subsumption relationship in order to achieve partially ordered representational structures. Most are based on first-order logic, and link subsumption directly to information specificity, that is, a structure is subsumed by another, if this structure contains strictly more information than the other.

The subsumption relationship on sorts can also be considered in terms of information specificity, however, there is a distinction to be drawn in the way in which subsumption is treated in sorts and in first-order logic based representational formalisms.

• First-order logic formalisms generally consider a relation of inclusion (hyponymy relation), commonly denoted as an is-a relationship. Consider the union of points and line segments: both can be said to be bounded geometrical entities of zero or one dimensions—note the is-a relationship.
• Sorts, on the other hand, consider a part-of relationship (meronymy relation). Consider a disjunctive sort of points and line segments, the sort of points forms part of the sort of points and line segments—note the part-of relationship. More distinctively, consider an attribute sort of colored labels, a label cannot be said to be a colored label, however, a label is part of a colored label.

In logic formalisms, a relational construct is used to represent such attribute associations. For example, in description logic¹, roles are defined as binary relationships between concepts. Consider a concept Label and a concept Color; the concept of colored labels can then be represented as Label ∩ ∃hasAttribute.Color, denoting those labels that have an attribute that is a color. Here, ∩ denotes intersection and ∃R.C denotes full existential quantification with respect to role R and concept C. It follows then that Label ∩ ∃hasAttribute.Color ⊆ Label; that is, the concept of labels subsumes the concept of colored labels—this is quite the reverse of how it is considered in sorts.

Another important distinction arises when considering searching and matching.

• First order logic-based representations generally make for an open-world assumption—that is, nothing is excluded unless it is done so explicitly. For example, polygon objects may have an assigned color. When looking for a yellow square, logically, every square is considered a potential solution—unless, it has an explicitly specified color, or it is otherwise known not to have the yellow color. The fact that a color is not specified does not exclude an object from potentially being yellow. As such, logic-based representations are automatically considered to be incomplete.
• Sorts, on the other hand, hold to a closed-world assumption: what isn't specified can never be assumed. A polygon has a color only if one is explicitly assigned: when looking for a yellow square, any square will not do; it has to have the yellow color assigned. This restriction is used to constrain emergence.

Another way of looking at this distinction between the open or closed world assumptions is to consider their applicability to knowledge representation.

• Logic-based representations essentially represent knowledge.
• Sorts, on the other hand, are intended to represent data—any reasoning is based purely on present (or emergent) data.

1. F. Baader, D. Calvanese, D. McGuinness, D. Nardi and P. Patel-Schneider, 2003, The Description Logic Handbook: Theory, Implementation and Applications, Cambridge University, Cambridge, UK.

Last update: 9 June 2012, webmaster @ sortal.org