88 Relations as Extensions

Status

This part is explanatory. It does not replace the denotational semantics of path expressions with a relation-valued semantics, and it does not make relations first-class Predica values. The authoritative denotation of a path expression remains a logic frame:

⟨R for F where Ψ⟩

The relation corresponding to the frame is obtained from its extension: assignments to the typed variables in F that satisfy Ψ are used to evaluate the result part R. It is therefore derived from the logic denotation, not a replacement for it.

Frame Extensions

A frame is similar to a set comprehension, but it deliberately keeps more structure than a set. The triple (R,F,Ψ) records the result terms, the free variables, and the formula that must hold. The extension of a frame is the set of concrete results obtained by assigning values to the free variables so that the formula is true, then evaluating the result terms.

Informally:

extension(⟨R for F where Ψ⟩)
    = { evaluate(R, σ) | σ assigns F and σ satisfies Ψ }

The extension forgets information. It does not remember the formula Ψ, the free-variable set F, the provenance of variables, or the particular result terms used in R. Distinct frames may have the same extension. This is why relations are useful as an extensional view, but are not an adequate replacement for frames as denotations.

A frame determines a relation, but a relation does not determine the frame that produced it: different choices of witnesses, formulas, and result expressions may have the same extension. The frame also determines a heading for its result; the relation alone does not.

S-Tuples and S-Relations

An s-tuple is a finite function from attributes to single values. An attribute in an s-tuple is therefore single-valued.

{ id: 17, city: "London" }

An s-relation is a set of s-tuples. For example, under a heading {id, city}, an s-relation may be:

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

Here {id, city} names the result attributes. When value domains matter, a heading for this result is written with types, for example { id: Integer, city: String }.

M-Tuples and M-Relations

An m-tuple is a finite function from attributes to sets of possible values. It is a compact representation of a rectangular set of s-tuples.

< id: {17}, city: {"London", "Athens"} >

Under the heading {id, city}, this m-tuple represents the two s-tuples:

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

An m-relation is a set of m-tuples. It represents the union of the rectangular regions represented by its m-tuples. M-relations are useful because they can avoid multiplying out Cartesian products until an implementation actually needs the s-relation extension.

Set-valued Attribute View

It is important not to confuse two related views. A single object may be inspected as a bundle of predicate extensions:

< id: {17}, city: {"London", "Athens"}, status: {} >

This says that the supplier has one id, two cities, and no status. That is useful as an object-centric, set-valued-attribute view.

By contrast, when this chapter writes !_H, the set attached to each attribute is interpreted as a set of alternatives to be multiplied out into s-tuples under heading H. If a result attribute has the empty set of alternatives, then there are no s-tuples for that rectangle under a heading that includes that attribute. If the intended result must still retain the supplier while showing that there is no status, then the status extension should be returned as a single set-valued term rather than multiplied out as a single-valued relation attribute.

Expansion

The expansion operator, written !, is the boundary between an m-relation representation and the s-relation semantics it represents. Expansion is always relative to a heading. This chapter writes !_H for expansion under heading H.

For an m-tuple t and attribute a, define:

t↑a = t.a if a ∈ dom(t), otherwise the value domain of a

Then the heading-relative expansion of t is:

t!_H = { s | dom(s) = H and for every a ∈ H, s.a ∈ t↑a }

If some present attribute of t has no values, then t!_H is empty. The expansion of an m-relation is the union of the expansions of its m-tuples:

M!_H = ⋃ { t!_H | t ∈ M }

Two m-relations are equivalent under heading H when they have the same expansion:

M ≡_H N  iff  M!_H = N!_H

This equivalence, not equality of representation, is the meaningful equality for m-relations used as implementation structures under that heading.

Operations

The governing rule is:

(op_m(M₁, ..., Mₙ))!_H = op_s(M₁!_H, ..., Mₙ!_H)

An m-relation operation is trusted only when it commutes with expansion in this sense. Elegance of an m-relation formula is not enough.

Union and Meet

The union of m-relations is ordinary set union of their m-tuples. Under expansion it corresponds to union of the represented s-relations.

(M ∪ N)!_H = M!_H ∪ N!_H

The meet of m-tuples intersects their allowed value sets attribute by attribute. Pairwise meet of m-relations corresponds to s-relation join under expansion:

(M ∧ N)!_H = M!_H ⋈ N!_H

When both expanded s-relations are under the same heading H, join is intersection. In that fixed-heading setting, meet behaves as conjunction of represented extensions.

Complement and Difference

Complement is relative to a heading and to the value domains of the attributes in that heading. For an m-tuple, the complement of the rectangle can be represented compactly as the union of the ways an s-tuple can escape the rectangle on at least one attribute.

For example, if each attribute has value domain {0,1}, then:

< a: {0}, b: {0} >!_{a,b}
    = { {a: 0, b: 0} }

not < a: {0}, b: {0} >
    expands to
    {
        {a: 0, b: 1},
        {a: 1, b: 0},
        {a: 1, b: 1}
    }

This is not the same as attribute-wise negation, which would produce only the opposite corner {a:1,b:1}. Semantic complement requires at least one attribute to escape, not every attribute.

Relation complement follows De Morgan's law: the complement of a union of rectangles is the meet of the complements of those rectangles. Difference is meet with complement:

(not M)!_H = universe(H) \ M!_H
(M -- N)!_H = M!_H \ N!_H
M -- N ≡_H M ∧ (not N)

Normalisation

Many different m-relations can represent the same s-relation. Implementations may replace one m-relation with another whenever expansion under the relevant heading is preserved.

A simple normalisation pass may:

remove m-tuples whose expansion is empty;
remove attributes whose value set is the whole value domain, since they do not restrict expansion;
remove an m-tuple whose expansion is contained in the expansion of another m-tuple.

For m-tuples, subsumption under heading H can be checked without multiplying out:

t subsumes u under H  iff  for every a ∈ H, t↑a ⊇ u↑a

Normalisation is not part of the logical denotation. It is an implementation freedom. Its obligation is simply:

normalize(M,H)!_H = M!_H

Fixed Heading Algebra

For a fixed heading H, normalised m-relations behave like a compressed representation of ordinary s-relations under H, modulo expansion. The laws are extensional laws:

(M ∪ N)!_H          = M!_H ∪ N!_H
(M ∧ N)!_H          = M!_H ∩ N!_H
(not M)!_H          = universe(H) \ M!_H
(M -- N)!_H         = M!_H \ N!_H
(M ∪ not M)!_H      = universe(H)
(M ∧ not M)!_H      = {}
(not not M)!_H      = M!_H
not (M ∪ N) ≡_H (not M) ∧ (not N)
not (M ∧ N) ≡_H (not M) ∪ (not N)

These laws should not be read as saying that the m-relation representations on both sides are identical. They say that the representations expand to the same s-relation under !_H.

Chapter Scope

This chapter establishes the core correspondence from frames to relations: frame extensions, s-relations, m-relations, heading-relative expansion, and the commutation criterion for m-relation operations. Later chapters spell out notation conventions, headings, projection, examples, relational-model correspondence, materialised accessors, and implementation obligations.

PreviousPart VIII: Relations Next89 Notation and Surface Syntax