The Relational Model

These requirements of an implementation arise from the Relational Model.

Prescriptions

These are requirements that an implementation must implement, support or allow.

Note: Some prescriptions contain additional recommendations that are not mandatory.

RM Pre 1 – Scalar type

A scalar type is a named set of scalar values. The set of values is non-empty and the definition must be accompanied by an example value of that type.

Note: As a result, a type must be non-empty.

An implementation must provide built-in scalar types, and the means to create and destroy user-defined scalar types.

The built-in scalar types must include a logical type with the values of true and false and the logical operators and, or and not. It should provide concise additional logical operators that are combinations of these.

Note: In practice the built-in scalar types are expected to include an ordered numeric type (for at least positive integer values) and a (possibly ordered) character type.

An implementation must provide means to define literal values, variables, components, attributes, parameters and operators of any scalar type.

RM Pre 2 – Scalar values

A scalar value is a value that is a member of a scalar type. Every scalar value belongs to exactly one scalar type. Values that belong to different types are different values.

RM Pre 3 – Scalar operators

A read-only operator takes zero or more arguments, each of which is a value of a declared type, and returns a result that is a value of a declared type. It updates no variables (other than local or temporary variables).

An update operator has the effect of assigning a value to a variable, or perhaps more than one. It takes one or more arguments, at least one of which is a reference to a variable of a declared type that it updates. It does not return a result.

An implementation must provide built-in operators and means to create and destroy user-defined operators of both kinds. Operator definitions must allow recursion.

Note: The above apply equally to both scalar and non-scalar operators.

A scalar operator is one that returns a scalar result or causes a scalar assignment.

An implementation must provide built-in scalar operators that include:

• Selectors, comparisons and assignment
• Additional operators required to give effect to the built-in scalar types.

RM Pre 4 – Representation of scalar types and values

Values are conceived as being immutable and pre-existing, so that particular values are chosen by a selector (rather than a constructor). A selector takes the form of a read-only operator that returns a value of the type.

Values of a scalar type are assumed to have a concrete or physical representation, which is not made visible. Instead values may be represented by the components of one or more abstract or possible representations or possreps.

An implementation must provide means to create user-defined types by specifying one or more possreps, each of which is made up of one or more components, each with a name and a declared type. Each possrep and its components must correspond one-to-one with a selector and its arguments, and there must be an invocation with literal arguments that will produce any value of that type.

Note: an implementation may provide additional operators that resemble selectors and are not bound by this requirement.

For a built-in type components are optional, but if omitted then an implementation must ensure that there is some selector invocation with literal arguments that will produce any value of that type.

Note: it is not specified whether an implementation may provide a built-in type if it is unable to meet this last requirement.

RM Pre 5 – Components are exposed

For each value of a type that has a possible representation, an implementation must provide read-only operators by which the value of any component of that value may be retrieved as a value of its declared type. These are informally referred to as getters.

For each variable of a type that has a possible representation, an implementation must provide update operators by which a new value is assigned to the variable so that any given component of its value will have a different value before and after the update.

An implementation may provide means for pseudo-variable assignment to individual components. These are informally referred to as setters.

Note: an implementation may provide additional operators that resemble getters and setters and are not bound by these requirements.

RM Pre 6 – Tuple types

A heading comprises a set of attributes, each of which has a distinct name and is of a declared type. The degree of a heading is the number of those attributes. The attributes are unordered, and accessed only by name. The empty heading has a degree of zero.

Note: An implementation is not required to provide a heading type.

A tuple type is a named set of tuple values, for which the type name is generated by reference to its unique heading. The effect is that two tuple values are of the same type if they have the same heading, and thereby the same type name. The degree of a tuple type is the degree of its heading. The empty tuple type has a degree of zero.

An implementation must provide means to define a tuple type by specifying the name and type of each attribute that comprise its heading.

An implementation must provide means to define literal values, variables, components, attributes, parameters and operators of any tuple type.

An implementation must provide built-in tuple operators that include:

• selectors, comparisons and assignment
• a subset of the relational algebra: such as Rename, Project, Extend and Join
• attribute extraction
• nesting and unnesting.

Attribute extraction means an operator that takes a tuple value and an attribute name as arguments and returns the value of that attribute as its result.

Tuple nesting means an operator that takes tuple values as arguments and returns a tuple value with a corresponding tuple-valued attribute as its result. Tuple unnesting means an operator that does the reverse.

RM Pre 7 – Relation types

A relation type is a named set of relation values, for which the type name is generated by reference to its unique heading. The effect is that two relation values are of the same type if they have the same heading, and thereby have the same type name. The degree of a relation type is the degree of its heading. The empty relation type has a degree of zero.

An implementation must provide means to define a relation type by specifying the name and type of each attribute that comprise its heading.

An implementation must provide means to define literal values, variables, components, attributes, parameters and operators of any relation type.

An implementation must provide built-in relation operators that include:

• selectors, comparisons and assignment
• the relational algebra
• tuple extraction
• nesting and unnesting.

Tuple extraction means an operator that takes a relation of cardinality one as an argument and returns its sole tuple as its result.

Relation nesting means an operator that takes a relation and tuple values as arguments and returns a corresponding relation value with those tuples constituting a relation-valued attribute as its result. Relation unnesting means an operator that does the reverse.

RM Pre 8 – Equality operator

An equality operator is one that takes two values as its arguments and returns true if and only if they are the same value. If this is so, then of course they are also the same type.

Two values that compare equal must be indistinguishable in their behaviour for all other operators, and if they behave differently in any way then they are different values and must not compare equal.

An implementation must provide an equality operator for every type, whether built-in or user-defined, scalar or non-scalar, or require and provide means for one to be defined.

RM Pre 9 – Tuple values

A tuple value comprises a heading (that of its type) and a set of values, one corresponding to each of its attributes. The attributes are not ordered, and its attribute values are accessible only by name.

The degree of a tuple value is the degree of its heading. The empty tuple has a degree of zero.

For each tuple type, an implementation must provide a selector with parameters that correspond one-to-one with its attributes and must ensure that there is some selector invocation with literal arguments that will produce any value of that type.

RM Pre 10 – Relation values

A relation value comprises a heading (that of its type) and a body. The body consists of a set of tuples, all with that same heading. The tuples are not ordered, and cannot be accessed individually.

The degree of a relation value is the degree of its heading. Its cardinality is the number of tuples in its body. An empty relation has a cardinality of zero.

For each relation type, an implementation must provide a selector with parameters that comprise a set of tuples of that same heading. It must ensure that there is some selector invocation with literal arguments that will produce any value of that type.

Note: there are exactly two relation values with an empty heading, one that is empty and one with a body consisting of a single empty tuple. They are sometimes referred to as Dum and Dee respectively.

RM Pre 11 – Scalar variables

A scalar variable means a variable of a scalar type. It must always hold a value of that same type. Note: there is no null value.

An implementation must provide means to define variables of any scalar type.

RM Pre 12 – Tuple variables

A tuple variable means a variable of a tuple type. It must always hold a value of that same type. The heading, attributes and degree of a tuple variable are as defined for its type and value. Note: there is no null value.

An implementation must provide means to define variables of any tuple type.

RM Pre 13 – Relation variables

A relation variable or relvar means a variable of a relation type. It must always hold a value of that same type. The heading, attributes, degree and cardinality of a relvar are as defined for its type and value.

Relation variables comprise database relvars and application relvars. Database relvars are contained in a database. Application relvars are local to an application.

An implementation must provide means to define application relvars, and to create and destroy database relvars.

Note: the lifetime and visibility of application variables and the extent to which they may be shared amongst programs that constitute an application, are not specified. Database relvars are not part of the application and are assumed to be shared.

RM Pre 14 – Real, virtual, public and private relvars

Database relvars may be real or virtual. Application relvars may be public or private.

A real relvar or base relvar is a database relvar that is not virtual. It exists in the database, it is time-varying and it is updatable.

A virtual relvar is a database relvar that has as its value the result of evaluating a relational expression that in turn refers to at least one database relvar other than itself. Whether it is updateable is not specified but if so, this is pseudo-variable assignment. Note: a virtual relvar is sometimes referred to as a view.

A public relvar is one that an application will perceive as a real relvar, but may actually be virtual. The intent is to provide a measure of isolation between the application’s requirements and possible changes in the database. If it is a view, it should be updateable.

A private relvar is one that is known and accessible only to the application.

An implementation must provide means to create or define each of the above.

Note: the lifetime and visibility of each kind of relvar are not specified.

Note: it is assumed that database relvars and public relvars are shared and that the effects of updates by other programs will cause their values to change over time, and may also cause attempts to update them to fail. Means to address this are not specified.

RM Pre 15 – Candidate keys

A candidate key is a set of attributes of a relation for which the values in every tuple are different, and that has no subset with that property.

An implementation must ensure that at least one candidate key is defined when any relvar is created.

Note: it is possible for a candidate key to be the set of all attributes, or to be empty (in which case the relation can contain only a single value or be empty).

RM Pre 16 – Database

A database is a named container for database relvars. Databases need not be disjoint.

The means to define, create or destroy databases are not specified, but should take place without effect on any running program.

RM Pre 17 – Transactions

A transaction is a grouping of statement executions that interacts with a single database. Distinct transactions interact with distinct databases (which need not themselves be disjoint).

An implementation must ensure that every statement is executed within the context of some transaction. Statements must be executed atomically, except that there may be specific exceptions such as nested statements and user-defined update operators.

RM Pre 18 – Relational Algebra

The Relational Algebra means a well-known set of operators over relation types by means of which relation values may be manipulated.

Note: A sufficient set would be monadic Restrict, Rename, Project, Extend and dyadic Join, Antijoin, Union and Minus; the precise set is not specified.

An implementation must provide a concise set of such operators and the means by which others can be defined.

Although each relational operator is generic in that it can apply to any relational type as input, the output type for any input can always be inferred. An implementation must use type inference to determine the result of using relational operators and detect errors accordingly.

The above should also apply to the subset of operators provided for tuple types.

RM Pre 19 – References

An implementation must provide means to use a reference to a variable of any kind or a constant of any type as a value in any expression.

Note: the value of a shared variable may change due to external updates. An implementation may provide means to detect and manage such changes, but this is not specified.

RM Pre 20 – Tuple and Relational Operators

An implementation should provide built-in relational operators in addition to those of the relational algebra, and must provide means to define and destroy read-only and update relational operators.

The above applies equally to tuple operators.

RM Pre 21 – Assignment

Assignment means replacing the value of a variable by another value. It is the operation performed by all update operators, regardless of form.

Multiple assignment means replacing the values of two or more variables by new values in such a way that they constitute a single atomically-executed statement.

The Assignment Principle states that if a value is assigned to a variable, then subsequently the value and that of the variable will compare equal.

The Golden Rule is that the state of the database must never violate the total database constraint.

An implementation must provide an assignment operator for every built-in type, and the means to define new ones for any type. Assignment must conform to the Assignment Principle.

Note: Assignment syntax is not specified, and may take the form of an update operator.

Note: Assignment to a shared variable or one subject to a constraint may fail. Means to detect and/or recover from such a failure are not specified.

An implementation must provide means for multiple assignment. The Golden Rule must be satisfied on successful completion.

RM Pre 22 – Comparison Operators

A comparison operator is one that takes two arguments of declared types and returns a logical result. The minimum set of comparison operators that an implementation must provide is:

• For all types: is equal to
• For ordered types: is less than
• For relational types: is a subset of
• For a tuple and a relational argument: is a member of.

For all but the last the arguments must be of the same type; for the last they must have the same heading.

An implementation should provide concise forms of the operators that result from combining and/or reordering the above together with logical operators. The precise set is not specified.

RM Pre 23 – Integrity Constraints

A constraint or integrity constraint is the equivalent of a logical assertion as to some part of the program or database state that is satisfied if it is true and is violated if it is false. The assertion may take the syntactic form of a logical expression, or some other form.

A type constraint specifies the set of values that constitute a type. The appearance of any other value whether as an intermediate result or as the value of a variable is a constraint violation.

A database constraint specifies the values allowed for a given set of database relvars taken in combination. The appearance of any combination of values that does not satisfy the constraint at the end of any statement execution (which may of course include multiple assignment) is a constraint violation.

An implementation must provide means to define and destroy type and database constraints. It must also where possible provide constraint inference, including detecting constraint incompatibility.

Note: an implementation may provide constraints on application relvars in similar form to those on database relvars.

An automatic update is one that may be performed where a database constraint applies to a set of database relvars and an update to one then requires that a specific update to another be performed to avoid a constraint violation.

An implementation should where possible and not prohibited determine and perform such automatic updates.

Note: automatic updates may cause database relvars to change value unexpectedly. Means to address this are not specified.

RM Pre 24 – Total Database Constraint

The total database constraint is the logical conjunction (AND) of all of the currently defined database constraints.

An implementation must ensure that no update leaves a database in a state that violates its own total constraint. Note: this is the Golden Rule.

RM Pre 25 – Catalog

The catalog for a database is a set of database relvars in that database, including the catalog itself. Operations such as defining and destroying types, variables, operators and constraints are regarded as assignments to the catalog and are subject to the rules of assignment, including multiple assignment.

RM Pre 26 – Good language design

An implementation must conform to the principles of good language design. Some of the principles to be considered include generality, parsimony, completeness, similarity, extensibility, openness, orthogonality and conceptual integrity.

Proscriptions

These are features that an implementation should not provide, support or allow, and that arise from the Relational Model.

RM Pro 1 – Attributes are not ordered

An implementation must not distinguish attributes of a relation or tuple by order, but only by name.

RM Pro 2 – Tuples are not ordered

An implementation must not distinguish tuples of a relation by order, but only by value.

RM Pro 3 – Duplicates not allowed

An implementation must not permit duplicate tuples in a relation. No pair of tuples in a relation may compare equal.

RM Pro 4 – No nulls

An implementation must ensure that every attribute in every tuple has a value of its type. Note: so there are no null values.

RM Pro 5 – Empty relations, tuples, headings and keys not excluded

An implementation must allow empty relations, tuples, headings and keys.

RM Pro 6 – No internal or physical access

An implementation must not provide access to physical, storage or internal levels of the system. It must rely on such access being provided by other means.

RM Pro 7 – No tuple-at-a-time operations

An implementation must not provide individual tuple operations or tuple-at-a-time operations on relational values.

RM Pro 8 – No composite attributes

A composite or compound attribute is one that can hold more than a single value, or can hold other attributes. Common examples include records, structures and arrays. The scalar and non-scalar values described above are single values for this purpose.

An implementation must not provide composite or compound attributes.

RM Pro 9 – No domain check override

Domain check override refers to means to defeat or override or bypass the type system.

An implementation must provide domain check override operators, but must ensure that all operations are in accordance with the type system.

RM Pro 10 – Not SQL

An implementation must not be called SQL.