# Tuple relational calculus

﻿
Tuple relational 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. Lacroix and Pirotte proposed 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.

Definition of the calculus

Relational database

Since the calculus is a query language for relational databases we first have to define a relational database. The basic relational building block is the domain, or data type. A tuple is an ordered multiset of attributes, which are ordered pairs of domain and value. A relvar (relation variable) is a set of ordered pairs of domain and name, which serves as the header for a relation. A relation is a set of tuples. Although these relational concepts are mathematically defined, those definitions map loosely to traditional database concepts. A table is an accepted visual representation of a relation; a tuple is similar to the concept of "row".

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" → 2"C"

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 "T""D". 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" → 2"T""D"

that maps the relation names in "R" to finite subsets of "T""D", 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.

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" -> 2"C" that defines a "type assignment" that assigns headers to some tuple variables. We then define the "set of atomic formulas" "A" ["S","type"] with the following rules:

# if "v" and "w" in "V", "a" in "type"("v") and "b" in "type"("w") 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".age = "s".age) — "t" has an age attribute and "s" has an age attribute with the same value
* ("t".name = "Codd") — tuple "t" has a name attribute and its value is "Codd"
* 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" -> "T""D" that maps tuple variables to tuples over the domain in "S":
# " "v"."a" = "w"."b" " is true if and only if "val"("v")("a") = "val"("w")("b")
# " "v"."a" = "k" " is true if and only if "val"("v")("a") = "k"
# " "r"("v") " is true if and only if "val"("v") is in "db"("r")

Formulas

The atoms can be combined into formulas, as is usual in first-order logic, with the logical operators ∧ (and), ∨ (or) and ¬ (not), and we can use the existential quantifier (∃) and the universal quantifier (∀) to bind the variables. We define the "set of formulas" "F" ["S","type"] inductively with the following rules:
# every atom in "A" ["S","type"] is also in "F" ["S","type"]
# if "f"1 and "f"2 are in "F" ["S","type"] then the formula " "f"1 ∧ "f"2 " is also in "F" ["S","type"]
# if "f"1 and "f"2 are in "F" ["S","type"] then the formula " "f"1 ∨ "f"2 " is also in "F" ["S","type"]
# if "f" is in "F" ["S","type"] then the formula " ¬ "f" " is also in "F" ["S","type"]
# if "v" in "V", "H" a header and "f" a formula in "F" ["S","type" ["v"->"H"] ] then the formula " ∃ "v" : "H" ( "f" ) " is also in "F" ["S","type"] , where "type" ["v"->"H"] denotes the function that is equal to "type" except that it maps "v" to "H",
# if "v" in "V", "H" a header and "f" a formula in "F" ["S","type" ["v"->"H"] ] then the formula " ∀ "v" : "H" ( "f" ) " is also in "F" ["S","type"]

Examples of formulas:

* "t".name = "C. J. Date" ∨ "t".name = "H. Darwen"
* Book("t") ∨ Magazine("t")
* ∀ "t" : {author, title, subject} ( ¬ ( Book("t") ∧ "t".author = "C. J. Date" ∧ ¬ ( "t".subject = "relational model")))Note that the last formula states that all books that are written by C. J. Date have as their subject the relational model. As usual we omit brackets if this causes no ambiguity about the semantics of the formula.

We will assume that the quantifiers quantify over the universe of all tuples over the domain in the schema. This leads to the following formal semantics for formulas given a database "db" over "S" and a tuple variable binding "val" : "V" -> "T""D":

# " "f"1 ∧ "f"2 " is true if and only if " "f"1 " is true and " "f"2 " is true,
# " "f"1 ∨ "f"2 " is true if and only if " "f"1 " is true or " "f"2 " is true or both are true,
# " ¬ "f" " is true if and only if " "f" " is not true,
# " ∃ "v" : "H" ( "f" ) " is true if and only if there is a tuple "t" over "D" such that "dom"("t") = "H" and the formula " "f" " is true for "val" ["v"->"t"] , and
# " ∀ "v" : "H" ( "f" ) " is true if and only if for all tuples "t" over "D" such that "dom"("t") = "H" the formula " "f" " is true for "val" ["v"->"t"] .

Queries

Finally we define what a query expression looks like given a schema "S" = ("D", "R", "h"):

: { "v" : "H" | "f"("v") }

where "v" is a tuple variable, "H" a header and "f"("v") a formula in "F" ["S","type"] where "type" = { ("v", "H") } and with "v" as its only free variable. The result of such a query for a given database "db" over "S" is the set of all tuples "t" over "D" with "dom"("t") = "H" such that "f" is true for "db" and "val" = { ("v", "t") }.

Examples of query expressions are:

* { "t" : {name} | ∃ "s" : {name, wage} ( Employee("s") ∧ "s".wage = 50.000 ∧ "t".name = "s".name ) }
* { "t" : {supplier, article} | ∃ "s" : {s#, sname} ( Supplier("s") ∧ "s".sname = "t".supplier ∧ ∃ "p" : {p#, pname} ( Product("p") ∧ "p".pname = "t".article ∧ ∃ "a" : {s#, p#} ( Supplies("a") ∧ "s".s# = "a".s# ∧ "a".p# = "p".p# ) }

Semantic and syntactic restriction of the calculus

Domain-independent queries

Because the semantics of the quantifiers is such that they quantify over all the tuples over the domain in the schema it can be that a query may return a different result for a certain database if another schema is presumed. For example, consider the two schemas "S1" = ( "D1", "R", "h" ) and "S2" = ( "D2", "R", "h" ) with domains "D1" = { 1 }, "D2" = { 1, 2 }, relation names "R" = { "r1" } and headers "h" = { ("r1", {"a"}) }. Both schemas have a common instance:: "db" = { ( "r1", { ("a", 1) } ) }If we consider the following query expression: { "t" : {a} | "t".a = "t".a }then its result on "db" is either { (a : 1) } under "S1" or { (a : 1), (a : 2) } under "S2". It will also be clear that if we take the domain to be an infinite set, then the result of the query will also be infinite. To solve these problems we will restrict our attention to those queries that are "domain independent", i.e., the queries that return the same result for a database under all of its schemas.

An interesting property of these queries is that if we assume that the tuple variables range over tuples over the so-called "active domain" of the database, which is the subset of the domain that occurs in at least one tuple in the database or in the query expression, then the semantics of the query expressions does not change. In fact, in many definitions of the tuple calculus this is how the semantics of the quantifiers is defined, which makes all queries by definition domain independent.

Safe queries

In order to limit the query expressions such that they express only domain-independent queries a syntactical notion of "safe query" is usually introduced. To determine whether a query expression is safe we will derive two types of information from a query. The first is whether a variable-column pair "t"."a" is "bound" to the column of a relation or a constant, and the second is whether two variable-column pairs are directly or indirectly equated (denoted "t"."v" = "s"."w").

For deriving boundedness we introduce the following reasoning rules:

# in " "v"."a" = "w"."b" " no variable-column pair is bound,
# in " "v"."a" = "k" " the variable-column pair "v"."a" is bound,
# in " "r"("v") " all pairs "v"."a" are bound for "a" in "type"("v"),
# in " "f"1 ∧ "f"2 " all pairs are bound that are bound either in "f"1 or in "f"2,
# in " "f"1 ∨ "f"2 " all pairs are bound that are bound both in "f"1 and in "f"2,
# in " ¬ "f" " no pairs are bound,
# in " ∃ "v" : "H" ( "f" ) " a pair "w"."a" is bound if it is bound in "f" and "w" <> "v", and
# in " ∀ "v" : "H" ( "f" ) " a pair "w"."a" is bound if it is bound in "f" and "w" <> "v".

For deriving equatedness we introduce the following reasoning rules (next to the usual reasoning rules for equivalence relations: reflexivity, symmetry and transitivity):

# in " "v"."a" = "w"."b" " it holds that "v"."a" = "w"."b",
# in " "v"."a" = "k" " no pairs are equated,
# in " "r"("v") " no pairs are equated,
# in " "f"1 ∧ "f"2 " it holds that "v"."a" = "w"."b" if it holds either in "f"1 or in "f"2,
# in " "f"1 ∨ "f"2 " it holds that "v"."a" = "w"."b" if it holds both in "f"1 and in "f"2,
# in " ¬ "f" " no pairs are equated,
# in " ∃ "v" : "H" ( "f" ) " it holds that "w"."a" = "x"."b" if it holds in "f" and "w"<>"v" and "x"<>"v", and
# in " ∀ "v" : "H" ( "f" ) " it holds that "w"."a" = "x"."b" if it holds in "f" and "w"<>"v" and "x"<>"v".

We then say the a query expression { v : H | f(v) } is "safe" if
* for every column name "a" in "H" we can derive that "v"."a" is equated with a bound pair in "f",
* for every subexpression of "f" of the form " ∀ "w" : "G" ( "g" ) " we can derive that for every column name "a" in "G" we can derive that "w"."a" is equated with a bound pair in "g", and
* for every subexpression of "f" of the form " ∃ "w" : "G" ( "g" ) " we can derive that for every column name "a" in "G" we can derive that "w"."a" is equated with a bound pair in "g".

The restriction to safe query expressions does not limit the expressiveness since all domain-independent queries that could be expressed can also be expressed by a safe query expression. This can be proven by showing that for a schema "S" = ("D", "R", "h"), a given set "K" of constants in the query expression, a tuple variable "v" and a header "H" we can construct a safe formula for every pair "v"."a" with "a" in "H" that states that its value is in the active domain. For example, assume that "K"={1,2}, "R"={"r"} and "h" = { ("r", {"a, "b"}) } then the corresponding safe formula for "v".b is:: "v".b = 1 ∨ "v".b = 2 ∨ ∃ "w" ( r(w) ∧ ( "v".b = "w".a ∨ "v".b = "w".b ) )This formula, then, can be used to rewrite any unsafe query expression to an equivalent safe query expression by adding such a formula for every variable "v" and column name "a" in its type where it is used in the expression. Effectively this means that we let all variables range over the active domain, which, as was already explained, does not change the semantics if the expressed query is domain independent.

*Relational algebra
*Relational calculus
**Domain relational calculus (DRC)

References

* Edgar F. Codd: [http://doi.acm.org/10.1145/362384.362685 A Relational Model of Data for Large Shared Data Banks] . "Communications of the ACM", 13(6):377–387, 1970.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Relational calculus — consist of two calculi, the tuple relational calculus and the domain relational calculus, that are part of the relational model for databases and provide a declarative way to specify database queries. This in contrast to the relational algebra… …   Wikipedia

• Domain relational calculus — In computer science, domain relational calculus (DRC) is a calculus that was introduced by Michel Lacroix and Alain Pirotte as a declarative database query language for the relational data model.[1] In DRC, queries have the form: where each Xi is …   Wikipedia

• Relational algebra — Not to be confused with Relation algebra. Relational algebra, an offshoot of first order logic (and of algebra of sets), deals with a set of finitary relations (see also relation (database)) that is closed under certain operators. These operators …   Wikipedia

• Calculus (disambiguation) — Calculus is Latin for pebble, and has a number of meanings in English: In mathematics and computer science Calculus , in its most general sense, is any method or system of calculation. To modern theoreticians the answer to the question what is a… …   Wikipedia

• Relational model — The relational model for database management is a database model based on first order predicate logic, first formulated and proposed in 1969 by Edgar Codd. [ Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks , E.F …   Wikipedia

• Relational database — A visual diagram showing the relationship between the two tables, as indicated by the arrow A relational database matches data by using common characteristics found within the data set. The resulting groups of data uses the relational model (a… …   Wikipedia

• Tuple — This article is about the mathematical concept. For the musical term, see Tuplet. For the achievement in Association Football, see The Sextuple. In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an… …   Wikipedia