90 Headings, Domains, and Universe

Tuples and relations do not carry headings. A tuple is a finite mapping from attributes to values, and a relation is a set of tuples. There is only one empty relation: {}.

A relation type has a heading: the result attributes and the value domain for each attribute. Predica's type system provides this relation-type context, so operations such as complement and heading-relative m-tuple expansion can be defined without making the heading part of the relation itself.

Headings

A heading is a finite mapping from attribute labels to value domains:

H = { id: Integer, city: String }

The labels id and city are result labels. They are not logic variables, and they need not be the names of source predicates. They are the labels that remain after the frame's result terms have been evaluated.

An s-tuple under heading H assigns exactly one value from the corresponding domain to each label:

{ id: 17, city: "London" }

An s-relation under H is a set of such s-tuples. The heading supplies the relevant result shape:

{} under { id: Integer }
{} under { id: Integer, city: String }

Both displays use the same empty relation {}. They place that relation under different headings, and therefore give it different possible tuples.

This is analogous to empty sets in a strongly typed language. Predica may allow expressions such as Set<Integer>{} and Set<Real>{}. The two values are equal as sets, but the expressions have different static types. Likewise, the empty relation is a single value even when it appears under different relation types.

Universe for a Heading

The universe for a heading is the Cartesian product of the value domains assigned by the heading. For:

H = { id: Integer, city: String }

the abstract universe is:

universe(H) =
{
    { id: i, city: c }
    | i ∈ Integer and c ∈ String
}

Every s-relation under H is a subset of universe(H).

R under H  iff  R ⊆ universe(H)

The universe is usually not something an implementation should materialise. It may be infinite, and even when it is finite it may be far too large. It is a semantic reference point for the relation view.

Complement Is Relative

Complement is meaningful only after the heading and value domains have been fixed:

not_H(R) = universe(H) \ R

For example, suppose a materialisation context uses the finite domains:

D_id   = {17, 23}
D_city = {"London", "Paris"}
H      = { id: D_id, city: D_city }

and:

R =
{
    { id: 17, city: "London" }
}

Then:

not_H(R) =
{
    { id: 17, city: "Paris" },
    { id: 23, city: "London" },
    { id: 23, city: "Paris" }
}

If the city domain is extended to include "Athens", the complement changes. The relation body R has not changed, but the universe against which it is complemented has changed. This is why complement cannot be defined from the set of result rows alone.

Abstract Domains and Active Domains

The abstract value domain for a type may be very large or infinite. A materialised query result, test fixture, or implementation plan may instead use a finite active domain for a particular operation. That can be useful and sometimes necessary, but it is a choice of materialisation or implementation context.

The two readings should not be confused:

Under an abstract domain reading, Integer means the whole integer domain.
Under an active-domain reading, the integer domain may be restricted to a finite set relevant to the current materialisation.

When a chapter writes universe(H), the intended domain context must already be fixed. If the text is discussing implementation algorithms or finite examples, the domain context may be a finite active domain. If the text is discussing abstract semantics, the domain context is the full value domain assigned by the heading.

M-Relations and Unrestricted Attributes

Headings and domains also explain omitted attributes in m-tuples during expansion. If an m-tuple does not mention an attribute from the heading, that attribute is unrestricted by the m-tuple and ranges over the whole domain supplied by the heading:

t↑a = t.a if a ∈ dom(t), otherwise domain_H(a)

For example, under:

H = { id: {17, 23}, city: {"London", "Paris"} }

the m-tuple:

< id: {17} >

expands to:

{
    { id: 17, city: "London" },
    { id: 17, city: "Paris" }
}

The omitted city attribute does not mean that city is absent from the result. It means that city is present in the heading but unrestricted by that rectangle. If city should not be in the result, that is a different result heading.

Relation Types

A heading can be read as a type for a relation result: it fixes the attribute names and the value domain for each attribute. This is not an intrinsic type of the relation. A relation may have more than one possible heading, and therefore more than one possible relation type.

This non-unique typing is what makes subtype relationships between relation types possible. The same relation value may satisfy a narrower heading/type and also a wider or more general one. If relations carried a unique heading as part of their identity, those subtype relationships would collapse into equality of differently headed objects rather than inclusion between possible interpretations.

This should also not be confused with the denotational type of a Predica path expression. The path expression still denotes a logic frame. The heading describes one way to materialise that frame's extension.

Previous89 Notation and Surface Syntax Next91 Projection and Result Shape