6 Cardinality

Attribute cardinality

Suppose that for the supplier-parts database we make small, natural cardinality adjustments to the supplier model: a supplier may have one or two names, the status is optional, and a supplier may be located in one or more cities. In Predica, these changes are expressed locally:

entity Supplier
{
    Integer id;
    String name[1..2];
    Integer status?;
    String city+;
    key {id};
}

The nested picture has the same shape; only the permitted sizes of the unary extensions have changed:

These cardinality changes affect the constraints on the attribute extensions, but not how queries are written, nor their denotations into logic.

To express the same simple cardinality changes that Predica handles locally, The RM is forced into a 6NF explosion. Tutorial D must:

• split the S relvar into four relvars (S, S_NAME, S_STATUS, S_CITY)
• introduce three new keys for (S_NAME, S_STATUS, S_CITY)
• introduce three new foreign-key constraints (one for each of the new relvars)
• change every query that touches names, cities or status
• change every constraint that refers to SNAME, CITY, or STATUS
• change every view or derived relvar that depends on S or any of the attributes that were factored out

This illustrates the structural fragility that Predica avoids. In Predica, cardinality is a declarative property of each attribute. In the RM, the same information must be encoded by restructuring the schema, introducing new relvars, new keys, new foreign keys, and rewriting every query and constraint that touches the affected attributes.

VAR S BASE RELATION
{ 
    S#     CHAR,
    SNAME  CHAR,
    STATUS INTEGER,
    CITY   CHAR 
}
KEY { S# };

-- Supplier S# exists
VAR S BASE RELATION
{
    S#  CHAR
}
KEY { S# };

-- Supplier S# has NAME
VAR S_NAME BASE RELATION
{
    S#   CHAR,
    NAME CHAR
}
KEY { S#, NAME };

CONSTRAINT S_NAME_FK
    S_NAME { S# } ⊆ S { S# };

CONSTRAINT S_NAME_CARDINALITY
    IS_EMPTY (
        S
        MINUS
        ( ( S_NAME GROUP ( NAME AS NAMES ) )
            WHERE COUNT(NAMES) BETWEEN 1 AND 2 ) { S# }
    );

-- Supplier S# has status STATUS
VAR S_STATUS BASE RELATION
{
    S#     CHAR,
    STATUS INTEGER
}
KEY { S# };

CONSTRAINT S_STATUS_FK
    S_STATUS { S# } ⊆ S { S# };

-- Supplier S# is located in CITY
VAR S_CITY BASE RELATION
{
    S#   CHAR,
    CITY CHAR
}
KEY { S#, CITY };

CONSTRAINT S_CITY_FK
    S_CITY { S# } ⊆ S { S# };

CONSTRAINT S_CITY_MIN_1
    IS_EMPTY (
        S
        MINUS
        S_CITY { S# }
    );    

Partial information

Predica provides a native, principled, and compositional way to model partial information. The key idea is simple: optional information is represented by empty attribute extensions, not by a special marker value inside a tuple.

An unnested, single-relvar representation becomes structurally unstable under partial information. The pure relational answer is usually to decompose optional or repeating attributes into separate relvars. SQL practice often takes more convenient shortcuts. If an entity has dozens of attributes, any of which may be unknown, practitioners typically reach for some mixture of:

• nullable columns, with SQL's special NULL behaviour
• separate child tables for optional or repeating attributes
• outer joins and CASE expressions in queries
• EAV-style designs for highly sparse data
• JSON/document columns when the relational shape becomes too cumbersome
• application-level validation to recover constraints no longer expressed cleanly in the schema

Some of these approaches are principled in isolation, especially decomposition into separate relvars. But they are not local: changing the optionality or cardinality of an attribute changes the surrounding schema shape and forces queries, views, and constraints to be rewritten. The common SQL shortcuts are more convenient, but they introduce their own semantic complications around NULLs, outer joins, constraint checking, and type information.

Predica’s “attributes as unary predicates” implicitly handles partial information, because each attribute has its own extension, which can be empty independently of other attributes. In Predica:

• each attribute is a unary predicate
• ? means “0 or 1”. Partial information is first-class
• unions of populations are always well-formed
• projection can be defined to skip entities lacking the attribute
• derived attributes can be typed and constrained
• the type system can infer union types automatically

The important point is locality. In Predica, optionality is stated directly on the attribute:

Email email?;

The attribute remains part of the conceptual type, while its denotation remains relational: email is a predicate that may hold for zero or one email values.

This yields a modelling space where every subset of attributes corresponds to a well-typed, well-formed predicate.

Example

Consider using the ? cardinality qualifier on dozens of attributes of a Person entity type:

entity Person
{
    String name?;
    Address address?;
    Phone phone?;
    Email email?;
    Date birthdate?;
    ...
}

entity Company
{
    Person person*;
}

// Database variable of type Company
var c = openDatabase<Company>("/path/to/database");

For any subset of attributes, say {name, email}, you can simply write: c.person.(name, email). Its logical denotation is:

name=N:String, email=E:Email
where
  ∃P:Person
    c.person(P)
  ∧ P.name(N)
  ∧ P.email(E)

This yields a clean, well-typed population of:

• exactly those people who have both attributes
• with both attributes guaranteed to be present
• with no NULLs
• with no schema gymnastics
• with no loss of type information

Adding another projected attribute, as in c.person.(name, address, email), adds P.address(A) to the conjunction, so the result contains exactly those people for whom all three attributes are present.

This is much cleaner than the usual SQL alternatives: no NULL tests, no outer joins, no JSON unpacking, and no separate modelling pattern just because an attribute is optional.

Zaniolo’s interpretation of partial information

Predica is sympathetic to the “no-information” interpretation of NULL associated with Carlo Zaniolo, but implements the idea differently. Zaniolo interprets NULLs inside relations. Predica avoids null markers altogether: optional attributes are predicates whose extensions may be empty for a given entity.

Projection over a set of attributes then restricts to those entities for which all projected attributes are present, producing a clean, total representation with no NULLs and no special cases. Missing information is represented by empty attribute extensions, not by special marker values.

In this way, Predica captures much of the motivation behind the no-information interpretation while remaining within classical two-valued logic and preserving strong typing, compositionality, and clean set-theoretic semantics.

The none expression

The expression none denotes an empty result, not a value. It is valid only where the surrounding expression form explicitly permits absence, especially for optional attributes and conditional branches whose result cardinality permits absence.

entity Person
{
    Email email?;
    → Boolean hasEmail = email ≠ none;
    → Email primaryEmail? = if hasEmail then email else none;
}

none is not a marker value stored inside the attribute, is not a member of any value domain, and must not be passed to ordinary functions as an argument. For an optional path or attribute expression E, the expression E = none tests that the extension of E is empty, while E ≠ none tests that it is non-empty. Equivalently, E = none means E.Σempty, and E ≠ none means E.Σexists. In an update to an optional location, assigning none clears the corresponding attribute extension.

Difference from SQL NULL

Although none is used where an application might otherwise use SQL NULL, it has a different semantic role. SQL NULL is a marker that can appear in a column position and then affects ordinary expressions through special three-valued logic. Predica none is not a value at all: it denotes the absence of a result in a context that permits absence.

This avoids the usual NULL pathologies. Equality remains ordinary two-valued equality over actual values; none is never an extra inhabitant of every type; arithmetic and ordinary functions do not need null-propagation rules; and stored predicates do not contain a hidden marker. Presence tests are explicit extension tests, written with none only as source shorthand for Σempty or Σexists.