Home > Tuple calculus
The tuple calculus is a calculus that was introduced by Edgar F. Codd as part of the relational model in order to give a declarative database query language for this data model. It formed the inspiration for the database query languages QUEL and SQL of which the latter, although far less faithful to the original relational model and calculus, is now used in almost all relational database management systems as the ad-hoc query language. Along with the tuple calculus Codd also introduced the domain calculus which is closer to first-order logic and showed that these two calculi (and the relational algebra) are equivalent in expressive power. Subsequently query languages for the relational model were called relationally complete if they could express at least all these queries.1 Definition of the Calculus
1.1 Relational Database
Since the calculus is a query language for relational databases we first have to define a relational database. We first assume the existence of a set C of column names, examples of which are "name", "author", "address" et cetera. We define headers as finite subsets of C. A relational database schema is defined as a tuple S = (D, R, h) where D is the domain of atomic values (see relational model for more on the notions of domain and atomic value), R is a finite set of relation names, and h : R -> 2C a function that associates a header with each relation name in R. (Note that this is a simplification from the full relational model where there is more than one domain and a header is not just a set of column names but also maps these column names to a domain.) Given a domain D we define a tuple over D as a partial function t : C -> D that maps some column names to an atomic value in D. An example would be (name : "Harry", age : 25). The set of all tuples over D is denoted as TD. The subset of C for which a tuple t is defined is called the domain of t (not to be confused with the domain in the schema) and denoted as dom(t).
Finally we define a relational database given a schema S = (D, R, h) as a function db : R -> 2TD that maps the relation names in R to finite subsets of TD such that for every relation name r in R and tuple t in db(r) it holds that dom(t) = h(r). The latter requirement simply says that all the tuples in a relation should contain the same column names, namely those defined for it in the schema.
1.2 Atoms
For the construction of the formulas we will assume an infinite set V of tuple variables. The formulas are defined given a database schema S = (D, R, h) and a partial function type : V -> 2C that defines a type assignment that assigns headers to some tuple variables. We then define the set of atomic fomulas A[S,type] with the following rules:
- if v and w in V, a in type(v) and b in type(v) then the formula " v.a = w.b " is in A[S,type],
- if v in V, a in type(v) and k denotes a value in D then the formula " v.a = k " is in A[S,type], and
- if v in V, r in R and type(v) = h(r) then the formula " r(v) " is in A[S,type].
Examples of atoms are
- (t.name = "Codd") -- tuple t has a name attribute and its value is "Codd"
- (t.age = s.age) -- t has an age attribute and s has an age attrbute with the same value
- Book(t) -- tuple t is present in relation Book.
The formal semantics of such atoms is defined given a database db over S and a tuple variable binding val : V -> TD that maps tuple variables to tuples over the domain in S:
- " v.a = w.b " is true iff val(v)(a) = val(w)(b)
- " v.a = k " is true iff val(v)(a) = k
- " r(v) " is true iff val(v) is in db(r)
