ThirdManifestoParaphrase

The Original

The Third Manifesto by C. J. Date and Hugh Darwen is the culmination of more than two decades of work on defining a foundation for the future of managing data. The authors view SQL and the relational database management systems that use it as deeply flawed, and have set down their views on a language to address those flaws. The title reflects two prior attempts (manifestos) by other authors.

The Manifesto is intentionally an academic publication written in academic language for an academic audience. Parts of it can only be read in conjunction with other books by the same authors, and parts use highly specialised language. It is not easily accessible to a general audience.

The intention here is to paraphrase, generalise and shorten the wording and to use terminology familiar to a general IT audience, while retaining the original intent, meaning and numbering. This has involved some reorganisation and some inclusion of background material from other writings to ensure that the all the terms used can be understood within one document.

This is not an easy thing to do while keeping true to the original and there may well be errors and omissions, for which I apologise in advance. Those who seek further clarity or authority should consult the primary references.

1. The original: http://www.dcs.warwick.ac.uk/~hugh/TTM/TTM-2016-04-05.pdf.
2. The book: http://www.dcs.warwick.ac.uk/~hugh/TTM/DTATRM.pdf
3. A related book: http://www.dcs.warwick.ac.uk/~hugh/TTM/Database-Explorations-revision-2.pdf
4. The web site: http://www.dcs.warwick.ac.uk/~hugh/TTM contains much additional material.

This Document

The document broadly follows the structure of the Manifesto, including an initial section with definitions and explanations of terms.

The Manifesto expresses many of its requirements as references to a hypothetical language called D. In this document they are replaced by references to the requirements of ‘an implementation’ and references to ‘the system’ have been replaced by references to ‘built-in’ features.

The Manifesto makes use of the syntax of Tutorial D, a teaching implementation of D. This material has been omitted on the grounds that readers will not be familiar with it.

The Manifesto refers to the Inheritance Model, which is a model of type inheritance proposed by the same authors. It may be found by the above links but is not covered here.

Additional definitions have been included as needed, mainly drawn from other books by the same authors. Minor changes have been made in some terminology. Some notes have been added to clarify intent or draw attention to specific consequences. Many owe their existence to contributions from The Third Manifesto mailing list.

The original is written in terms that assume an imperative language. Some changes would be needed to provide better support for an applicative or functional implementation, but this is not the place for them.

Preamble and Definitions

This document is written as a series of requirements on an implementation that is a programming language, supported by system libraries and a relational database manager. Nothing here should be taken to mandate any particular design or exclude any approach or prohibit any additional capabilities beyond what is explicitly stated.

Terms that have particular meanings are underlined at the point where they are defined, or where first used if not defined.

A requirement for something in the singular or plural should generally be read to mean either, to avoid having such qualifications appear repeatedly in the text.

Definitions

The terms type, value, variable and operator are of particular significance as core concepts and the foundations of the language. Definitions are provided below, but the concepts should already be familiar.

A type is a named and non-empty set of values. Types with different names are different types. Any type may form the basis for defining any variable, component, attribute, argument or operator as set out below.

Every type is a scalar type or a non-scalar type. A non-scalar type is a tuple or relation type. A scalar type is any other type.

An ordered type is one for which a total ordering is defined.

An operator is a named entity that may be invoked to perform an operation. Operators have parameters, are invoked with arguments, may update variables and may return a value as a result.

Note: The term operator is intended to be inclusive of operators, procedures, functions and subroutines as found in other languages.

A parameter is a name by which an operator refers to an argument passed to it.

An argument is a value or a reference to a variable that is provided to an operator when it is invoked. It takes the syntactical form of a literal, an expression, or a symbol denoting a variable.

A variable is a named entity that holds a value, which may vary during the course of a program. It has a declared type and always contains a value of that type. Every access to the value of a variable returns a value of its type.

Assignment means setting a variable to a value by means of an update operator.

Note: Assignment and update are largely interchangeable terms.

Pseudo-variable assignment means a syntactic form similar to an assignment where the target is not a variable.

A statement is some minimal unit of program execution that results in a change in program or database state and can execute atomically. Atomic means that it either executes in its entirety or not at all.

An expression is a syntactic form that includes operators and values and when evaluated produces a value as a result.

A literal is a symbol or sequence of symbols that denotes a constant value, which is known at compile time.

Built-in means that something is provided as a standard part of the implementation. User-defined means that it is defined using means provided by the implementation.

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.

Other Orthogonal

These are requirements of an implementation that arise outside the Relational Model.

Note: this has nothing to do with ‘object oriented’.

Prescriptions

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

OO Pre 1 - Compile time type checking

An implementation should check the usage of all types at compile time to avoid type errors that might otherwise occur during execution. Note: this implies type inference by the compiler.

OO Pre 2 - Type inheritance

If an implementation supports type inheritance then it must be in accordance with the Manifesto Inheritance Model (see preamble).

OO Pre 3 - Computational completeness

A language is considered computationally complete if entire applications can be written in it, and that in particular it does not depend on another language for defining new types and operators.

An implementation must be computationally complete, for at least some useful set of applications. Note: An implementation that is a data sub-language would not satisfy this requirement.

An implementation may co-exist with other languages, including being called by a host program and/or calling upon another language to implement user-defined operators and types where there is reason to do so.

OO Pre 4 – Explicit transaction support

Transactions begin with start transaction and end with commit or rollback. Commit means that the updates in that transaction are made permanent in the database. Rollback means that they are discarded and the database state is unaffected by the transaction. These are the transaction boundaries.

Implicit commit means that each statement is treated as if it were preceded by start transaction and followed by commit, that is, as if there were transaction boundaries around each statement.

An implementation must provide explicit support for start transaction and commit, and automatic rollback if a commit fails. It may also provide explicit support for rollback, and implicit commit.

OO Pre 5 – Nested transactions

A nested transaction is one that has boundaries that lie entirely within those of another transaction. Overlapped transactions are not allowed.

An implementation must support nested transactions, which must interact with the same database. A rollback of the outer transaction must cause a rollback of the inner, even if it has already performed a commit. The order in which operations are carried out is not specified.

OO Pre 6 – Aggregation operators

An aggregation operator is one that takes as its arguments an attribute value (or values) from each of the tuples in a relation and returns a single value.

If an implementation provides such an operator which is dyadic, specifies an identity value and is allowed to return any value of its type then it must return a result equivalent to the successive application of the operator to the identity value and each of the values in the tuple, regardless of order.

Note: the result for an empty relation will be the identity value. An implementation may provide other unspecified aggregation operators.

Proscriptions

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

OO Pro 1 – Relvars are not domains

A domain means a relational type.

An implementation must not use individual relvars as if they were relational types.

OO Pro 2 – No pointers

A pointer is a machine address or a physical representation for one.

An implementation must not allow any attribute of any database relvar to be of type pointer.

Note: whether pointer types are allowed for scalar variables, attributes of tuple types and attributes of application relvars is not specified.

Very Strong Suggestions

These are features that an implementation should provide or at least consider providing, but fall short of being mandatory requirements.

Relational Model Very Strong Suggestions

These are recommended features that arise from the Relational Model.

RM VSS 1 – Built-in key value generator

An implementation should provide a built-in mechanism by which the values of certain attributes may be generated, and which are guaranteed to be unique (within limits). The intended purpose is to generate unique key values.

RM VSS 2 – Inferred candidate keys

Where possible an implementation should infer the candidate keys for a relvar from its definition. In particular it should do so for a virtual relvar based on an analysis of its defining expression and any base or other relvars it references.

RM VSS 3 – Transition constraints

A transition constraint is one that serves to define the permitted transitions that a database can make from one value to another.

An implementation should support transition constraints, and may associate them with specific update operators.

RM VSS 4 – Quota queries

A quota query is one that specifies a limit on the cardinality of the relational value that is the result of an expression.

An implementation should support quota queries, which may either be absolute or relative to the rank of some attribute value. In the latter case the actual result may contain more or less tuples than the specified limit.

RM VSS 5 – Generalised transitive closure

A transitive closure is a relational operation that takes as an argument a relation that represents a directed graph as individual arcs and returns one that lists all paths through the graph.

A generalised transitive closure is one that can perform calculations such as concatenation and aggregation along those paths.

An implementation should provide means to define generalised transitive closure operators.

RM VSS 6 – Generic operators

A generic operator is one that has arguments and results that are drawn from a specified set of types and are not just individual declared types. All built-in operators of the relational calculus are generic, in that they apply to all relational types.

An implementation should provide means for defining generic operators, particularly for relational types.

RM VSS 7 – Implementation of SQL

An implementation should be such that it may be used to implement a dialect of SQL (as a transition aid), or that existing SQL programs and databases may be converted to it (for migration).

Other Orthogonal Very Strong Suggestions

These are recommended features that arise outside the Relational Model.

OO VSS 1 – Type inheritance

An implementation should support type inheritance as described by the Inheritance Model.

OO VSS 2 – Operator and types unbundled

Bundling means the common object-oriented practice of defining operators inside a particular class, and thereby having a privileged receiver or self or this object for the operator.

An implementation should avoid bundling and instead provide operators that are separate from the types they act on, and that have no privileged receiver.

OO VSS 3 – Single level store

Single level store means the principle that database and application variables be interchangeable and indistinguishable for most programming purposes.

An implementation should support single level storage to the maximum extent possible.

Note: the consequences in a concurrent environment and means to address them are not specified.