91 Projection and Result Shape

Projection is the relation view of keeping fewer result attributes. In the logic-first semantics, the primary operation is still on frames: choose which result bindings to expose, and let the hidden result values become hidden witnesses.

Frame Projection

Given a frame:

⟨R for F where Ψ⟩

Keeping only attributes A means retaining only the result bindings in R whose attribute names belong to A. Informally:

project_A(⟨R for F where Ψ⟩) = ⟨R|A for F where Ψ⟩

At the frame level, the condition that defines the path is unchanged. Assignments to variables that are no longer exposed remain possible witnesses for the projected result. When displayed as a formula over only the remaining result variables, those hidden result variables may appear under existential quantifiers. When the extension is materialised as a set, duplicate result tuples collapse.

For example:

id=I:Integer, city=C:String
where ∃S:Supplier (s.supplier(S) ∧ S.id(I) ∧ S.city(C))

projected to id gives:

id=I:Integer
where ∃S:Supplier ∃C:String (s.supplier(S) ∧ S.id(I) ∧ S.city(C))

The city variable is no longer a result, but it is still a witness: the resulting id appears when there exists some city satisfying the original condition.

S-Relation Projection

For an s-relation under heading H, projection to A ⊆ H restricts every tuple to the attributes in A:

π_A(S) = { s|A | s ∈ S }

For example:

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

π_{id}(S) =
{
    { id: 17 },
    { id: 23 }
}

The two rows for supplier 17 collapse because s-relations are sets.

M-Relation Projection

For m-relations, projection must still be judged by the s-relation semantics. If M is interpreted under heading H, then projection to A ⊆ H is correct only when:

π_A^m(M)!_A = π_A(M!_H)

A tempting definition is to project every m-tuple attribute-wise:

π_A^naive(M) = { t|A | t ∈ M }

This is correct only under a precondition: no m-tuple may be unsatisfiable because of an attribute that projection will drop.

The Bottom-Tuple Pitfall

Consider the m-relation:

M = { < id: {17}, status: {} > }

Under heading {id, status}, this m-relation has empty expansion:

M!_{id,status} = {}

Therefore projecting the s-relation extension gives:

π_{id}(M!_{id,status}) = {}

But naive m-relation projection gives:

π_{id}^naive(M) = { < id: {17} > }

π_{id}^naive(M)!_{id} =
{
    { id: 17 }
}

The naive projection has invented a result that was not present in the s-relation extension. It dropped the very attribute that made the rectangle unsatisfiable.

Extensional Projection

The factorised projection must discard unsatisfiable m-tuples before dropping attributes:

π_A^m(M) = { t|A | t ∈ M and t!_H ≠ {} }

Equivalently, for the finite m-tuples used in this part, discard any m-tuple whose present attributes include an empty value set. Then:

π_A^m(M)!_A = π_A(M!_H)

This is the same discipline used throughout the Relations part. The m-relation operation is accepted only because it preserves the heading-relative s-relation semantics.

Projection and Set-Valued Results

Projection should not be used to smuggle empty predicate extensions into rows. If the intended result is one row per supplier with the whole status extension recorded, then the frame must expose a set-valued result term such as:

statuses=TS:Set<Integer>
where TS = { T:Integer | S.status(T) }

That is different from exposing status=T:Integer and then projecting away failed status assignments. Projection keeps fewer attributes from an existing extension; it does not turn an unsatisfied single-valued result into an empty set-valued result.