Editing Tuple relational calculus (section)

== Definition ==
=== Relational database ===

Since the calculus is a [[query language]] for [[relational database]]s we first have to define a relational database. The basic relational building block is the [[Data domain|domain]] (somewhat similar, but not equal to, a [[data type]]).  A [[tuple]] is a finite sequence of [[Attribute (computing)|attribute]]s, which are [[ordered pair]]s of domains and values. A [[relational model|relation]] is a set of (compatible) tuples.  Although these relational concepts are mathematically defined, those definitions map loosely to traditional database concepts.  A [[table (database)|table]] is an accepted visual representation of a relation; a tuple is similar to the concept of a [[row (database)|row]].

We first assume the existence of a set ''C'' of column names, examples of which are "name", "author", "address", etcetera. 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<sup>''C''</sup>

a [[function (mathematics)|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]] that maps some column names to an atomic value in ''D''. An example would be (name : "Harry", age : 25).

:''t'' : ''C'' ⇸ ''D''

The set of all tuples over ''D'' is denoted as ''T''<sub>''D''</sub>. 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<sup>''T''<sub>''D''</sub></sup>

that maps the relation names in ''R'' to finite subsets of ''T''<sub>''D''</sub>, 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<sup>''C''</sup>, called at ''type assignment'', that assigns headers to some tuple variables. We then define the ''set of [[atomic formula]]s'' ''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''<sub>''D''</sub> 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''<sub>1</sub> and ''f''<sub>2</sub> are in ''F''[''S'',''type''] then the formula  ''f''<sub>1</sub> ∧ ''f''<sub>2</sub>  is also in ''F''[''S'',''type'']
# if ''f''<sub>1</sub> and ''f''<sub>2</sub> are in ''F''[''S'',''type''] then the formula  ''f''<sub>1</sub> ∨ ''f''<sub>2</sub>  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''<sub>[''v''->''H'']</sub>] then the formula  ∃ ''v'' : ''H'' ( ''f'' )  is also in ''F''[''S'',''type''], where ''type''<sub>[''v''->''H'']</sub> 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''<sub>[''v''->''H'']</sub>] 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''<sub>''D''</sub>:

#  ''f''<sub>1</sub> ∧ ''f''<sub>2</sub>  is true if and only if  ''f''<sub>1</sub>  is true and  ''f''<sub>2</sub>  is true,
#  ''f''<sub>1</sub> ∨ ''f''<sub>2</sub>  is true if and only if  ''f''<sub>1</sub>  is true or  ''f''<sub>2</sub>  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''<sub>[''v''->''t'']</sub>, 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''<sub>[''v''->''t'']</sub>.

=== 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# ))) }