Relational model

<h2 id="history">History</h2>
The relational model was developed by <a href="/facts/Edgar_F._Codd/QCSbPYkK">Edgar F. Codd</a> as a general model of data, and subsequently promoted by <a href="/facts/Christopher_J._Date/qA9FDQuB">Chris Date</a> and <a href="/facts/Hugh_Darwen/pVF2Iact">Hugh Darwen</a> among others. In their 1995 The Third Manifesto, Date and Darwen try to demonstrate how the relational model can accommodate certain "desired" <a href="/facts/Object-oriented/TxNMEcao">object-oriented</a> features.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h3>Extensions</h3>
Some years after publication of his 1970 model, Codd proposed a <a href="/facts/Three-valued_logic/k4vMkwRL">three-valued logic</a> (True, False, Missing/<a href="/facts/Null_(SQL)/RBnXTe7k">NULL</a>) version of it to deal with missing information, and in his The Relational Model for Database Management Version 2 (1990) he went a step further with a four-valued logic (True, False, Missing but Applicable, Missing but Inapplicable) version.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="conceptualization">Conceptualization</h2>
<h3>Basic concepts</h3>

A relation consists of a heading and a body. The heading defines a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of attributes, each with a name and data type (sometimes called a domain). The number of attributes in this set is the relation's degree or <a href="/facts/Arity/zSVuwHvP">arity</a>. The body is a set of tuples. A tuple is a collection of n values, where n is the relation's degree, and each value in the tuple corresponds to a unique attribute.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> The number of tuples in this set is the relation's <a href="/facts/Cardinality/m6VPojwT">cardinality</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>: 17–22 
Relations are represented by relational <a href="/facts/Variable_(computer_science)/VoCKtwml">variables</a> or relvars, which can be reassigned.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>: 22–24  A <a href="/facts/Database/VYcpkevb">database</a> is a collection of relvars.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>: 112–113 
In this model, databases follow the Information Principle: At any given time, all <a href="/facts/Information_theory/qNLH3U5P">information</a> in the database is represented solely by values within tuples, corresponding to attributes, in relations identified by relvars.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>: 111 

<h3>Constraints</h3>
A database may define arbitrary <a href="/facts/Boolean_expressions/qWS7Ef6n">boolean expressions</a> as <a href="/facts/Constraint_(database)/pEKGmJLy">constraints</a>. If all constraints evaluate as true, the database is consistent; otherwise, it is inconsistent. If a change to a database's relvars would leave the database in an inconsistent state, that change is illegal and must not succeed.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>: 91 
In general, constraints are expressed using relational comparison operators, of which just one, "is subset of" (⊆), is theoretically sufficient.
Two special cases of constraints are expressed as keys and foreign keys:

<h4>Keys</h4>
A candidate key, or simply a key, is the smallest <a href="/facts/Subset/SJGERmbA">subset</a> of attributes guaranteed to uniquely differentiate each tuple in a relation. Since each tuple in a relation must be unique, every relation necessarily has a key, which may be its complete set of attributes. A relation may have multiple keys, as there may be multiple ways to uniquely differentiate each tuple.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>: 31–33 
An attribute may be unique across tuples without being a key. For example, a relation describing a company's employees may have two attributes: ID and Name. Even if no employees currently share a name, if it is possible to eventually hire a new employee with the same name as a current employee, the attribute subset {Name} is not a key. Conversely, if the subset {ID} is a key, this means not only that no employees currently share an ID, but that no employees will ever share an ID.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>: 31–33 

<h4>Foreign keys</h4>
Main article: <a href="/facts/Foreign_key/52Ns8RTD">Foreign key</a>
A foreign key is a subset of attributes A in a relation R1 that corresponds with a key of another relation R2, with the property that the <a href="/facts/Projection_(relational_algebra)/YgQm2wgA">projection</a> of R1 on A is a subset of the projection of R2 on A. In other words, if a tuple in R1 contains values for a foreign key, there must be a corresponding tuple in R2 containing the same values for the corresponding key.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>: 34 

<h3>Relational operations</h3>
Users (or programs) request data from a relational database by sending it a <a href="/facts/Database_query/VYcpkevb">query</a>. In response to a query, the database returns a result set.
Often, data from multiple tables are combined into one, by doing a <a href="/facts/Join_(SQL)/Cxl5lxcR">join</a>. Conceptually, this is done by taking all possible combinations of rows (the <a href="/facts/Cartesian_product/BfqBWzdL">Cartesian product</a>), and then filtering out everything except the answer.
There are a number of relational operations in addition to join. These include project (the process of eliminating some of the columns), restrict (the process of eliminating some of the rows), union (a way of combining two tables with similar structures), difference (that lists the rows in one table that are not found in the other), intersect (that lists the rows found in both tables), and product (mentioned above, which combines each row of one table with each row of the other). Depending on which other sources you consult, there are a number of other operators – many of which can be defined in terms of those listed above. These include semi-join, outer operators such as outer join and outer union, and various forms of division. Then there are operators to rename columns, and summarizing or aggregating operators, and if you permit <a href="/facts/Relation_(database)/Sj67AUyD">relation</a> values as attributes (relation-valued attribute), then operators such as group and ungroup.
The flexibility of relational databases allows programmers to write queries that were not anticipated by the database designers. As a result, relational databases can be used by multiple applications in ways the original designers did not foresee, which is especially important for databases that might be used for a long time (perhaps several decades). This has made the idea and implementation of relational databases very popular with businesses.

<h3>Database normalization</h3>
Main article: <a href="/facts/Database_normalization/uLCKbIBz">Database normalization</a>
<a href="/facts/Relation_(database)/Sj67AUyD">Relations</a> are classified based upon the types of anomalies to which they're vulnerable. A database that is in the <a href="/facts/First_normal_form/tUqnBUlt">first normal form</a> is vulnerable to all types of anomalies, while a database that is in the domain/key normal form has no modification anomalies. Normal forms are hierarchical in nature. That is, the lowest level is the first normal form, and the database cannot meet the requirements for higher level normal forms without first having met all the requirements of the lesser normal forms.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

<h2 id="logical-interpretation">Logical interpretation</h2>
The relational model is a <a href="/facts/Formal_system/KaeDAjK7">formal system</a>. A relation's attributes define a set of <a href="/facts/Logic/8JnpJLtt">logical</a> <a href="/facts/Propositions/0877MFMD">propositions</a>. Each proposition can be expressed as a tuple. The body of a relation is a subset of these tuples, representing which propositions are true. Constraints represent additional propositions which must also be true. <a href="/facts/Relational_algebra/7tjTFXdf">Relational algebra</a> is a set of logical rules that can <a href="/facts/Validity_(logic)/oMGkywGC">validly</a> <a href="/facts/Inference/RBbe95bP">infer</a> conclusions from these propositions.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>: 95–101 
The definition of a tuple allows for a unique empty tuple with no values, corresponding to the <a href="/facts/Empty_set/ffEk3eA6">empty set</a> of attributes. If a relation has a degree of 0 (i.e. its heading contains no attributes), it may have either a cardinality of 0 (a body containing no tuples) or a cardinality of 1 (a body containing the single empty tuple). These relations represent <a href="/facts/Boolean_domain/9cYq9TC1">Boolean</a> <a href="/facts/Truth_values/SY4e2w8l">truth values</a>. The relation with degree 0 and cardinality 0 is False, while the relation with degree 0 and cardinality 1 is True.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>: 221–223 

<h3>Example</h3>
If a relation of Employees contains the attributes {Name, ID}, then the tuple {Alice, 1} represents the proposition: "There exists an employee named Alice with ID 1". This proposition may be true or false. If this tuple exists in the relation's body, the proposition is true (there is such an employee). If this tuple is not in the relation's body, the proposition is false (there is no such employee).<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>: 96–97 
Furthermore, if {ID} is a key, then a relation containing the tuples {Alice, 1} and {Bob, 1} would represent the following <a href="/facts/Contradiction/PQHH5a2J">contradiction</a>:

<ol><li>There exists an employee with the name Alice and the ID 1.</li>
<li>There exists an employee with the name Bob and the ID 1.</li>
<li>There do not exist multiple employees with the same ID.</li></ol>
Under the <a href="/facts/Principle_of_explosion/qMyRl2Ya">principle of explosion</a>, this contradiction would allow the system to prove that any arbitrary proposition is true. The database must enforce the key constraint to prevent this.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>: 104 

<h2 id="examples">Examples</h2>
<h3>Database</h3>
An idealized, very simple example of a description of some <a href="/facts/Relvar/egcFY101">relvars</a> (<a href="/facts/Relation_(database)/Sj67AUyD">relation</a> variables) and their attributes:

<ul><li>Customer (Customer ID, Name)</li>
<li>Order (Order ID, Customer ID, Invoice ID, Date)</li>
<li>Invoice (Invoice ID, Customer ID, Order ID, Status)</li></ul>
In this <a href="/facts/Design/kR4GNeja">design</a> we have three relvars: Customer, Order, and Invoice. The bold, underlined attributes are <a href="/facts/Candidate_key/1SyxFj7C">candidate keys</a>. The non-bold, underlined attributes are <a href="/facts/Foreign_key/52Ns8RTD">foreign keys</a>.
Usually one <a href="/facts/Candidate_key/1SyxFj7C">candidate key</a> is chosen to be called the <a href="/facts/Primary_key/veT9mAbo">primary key</a> and used in <a href="/facts/Preference/hWCEmfuX">preference</a> over the other candidate keys, which are then called <a href="/facts/Alternate_key/veT9mAbo">alternate keys</a>.
A candidate key is a unique <a href="/facts/Identifier/pPaQPLhj">identifier</a> enforcing that no <a href="/facts/Tuple/BI1HIxL8">tuple</a> will be duplicated; this would make the <a href="/facts/Relation_(database)/Sj67AUyD">relation</a> into something else, namely a <a href="/facts/Bag_(mathematics)/bPFJGMDo">bag</a>, by violating the basic definition of a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a>. Both foreign keys and superkeys (that includes candidate keys) can be composite, that is, can be composed of several attributes. Below is a tabular depiction of a relation of our example Customer relvar; a relation can be thought of as a value that can be attributed to a relvar.

<h3>Customer relation</h3>
<table><tbody><tr><th>Customer ID</th><th>Name</th></tr><tr><td>123</td><td>Alice</td></tr><tr><td>456</td><td>Bob</td></tr><tr><td>789</td><td>Carol</td></tr></tbody></table>
If we attempted to insert a new customer with the ID 123, this would violate the design of the relvar since Customer ID is a primary key and we already have a customer 123. The <a href="/facts/DBMS/VYcpkevb">DBMS</a> must reject a <a href="/facts/Database_transaction/q1Etrsl8">transaction</a> such as this that would render the <a href="/facts/Database/VYcpkevb">database</a> inconsistent by a violation of an <a href="/facts/Database_integrity/g3XGbKIH">integrity constraint</a>. However, it is possible to insert another customer named Alice, as long as this new customer has a unique ID, since the Name field is not part of the primary key.
<a href="/facts/Foreign_key/52Ns8RTD">Foreign keys</a> are <a href="/facts/Integrity_constraint/g3XGbKIH">integrity constraints</a> enforcing that the <a href="/facts/Value_(computer_science)/QgQPbewf">value</a> of the attribute set is drawn from a <a href="/facts/Candidate_key/1SyxFj7C">candidate key</a> in another <a href="/facts/Relation_(database)/Sj67AUyD">relation</a>. For example, in the Order relation the attribute Customer ID is a foreign key. A <a href="/facts/Join_(SQL)/Cxl5lxcR">join</a> is the <a href="/facts/Operation_(mathematics)/Yplv602Q">operation</a> that draws on <a href="/facts/Information/3LdrzXtJ">information</a> from several relations at once. By joining relvars from the example above we could query the database for all of the Customers, Orders, and Invoices. If we only wanted the tuples for a specific customer, we would specify this using a restriction condition. If we wanted to retrieve all of the Orders for Customer 123, we could <a href="/facts/Information_retrieval/MFSmpeNw">query</a> the database to return every row in the Order table with Customer ID 123 .
There is a flaw in our <a href="/facts/Database_design/Hdb9LRFX">database design</a> above. The Invoice relvar contains an Order ID attribute. So, each tuple in the Invoice relvar will have one Order ID, which implies that there is precisely one Order for each Invoice. But in reality an invoice can be created against many orders, or indeed for no particular order. Additionally the Order relvar contains an Invoice ID attribute, implying that each Order has a corresponding Invoice. But again this is not always true in the real world. An order is sometimes paid through several invoices, and sometimes paid without an invoice. In other words, there can be many Invoices per Order and many Orders per Invoice. This is a <a href="/facts/Many-to-many_(data_model)/2MtUxMVt">many-to-many</a> relationship between Order and Invoice (also called a non-specific relationship). To represent this relationship in the database a new relvar should be introduced whose <a href="/facts/Role/LDthMhoD">role</a> is to specify the correspondence between Orders and Invoices:

OrderInvoice (Order ID, Invoice ID)

Now, the Order relvar has a <a href="/facts/One-to-many_(data_model)/mUE7lwbd">one-to-many relationship</a> to the OrderInvoice table, as does the Invoice relvar. If we want to retrieve every Invoice for a particular Order, we can query for all orders where Order ID in the Order relation equals the Order ID in OrderInvoice, and where Invoice ID in OrderInvoice equals the Invoice ID in Invoice.

<h2 id="application-to-relational-databases">Application to relational databases</h2>
A <a href="/facts/Data_domain/4oDqjYsd">data type</a> in a relational database might be the set of integers, the set of character strings, the set of dates, etc. The relational model does not dictate what types are to be supported.
Attributes are commonly represented as <a href="/facts/Column_(database)/WB91xSVs">columns</a>, tuples as <a href="/facts/Row_(database)/PIpv7c9e">rows</a>, and relations as tables. A table is specified as a list of column definitions, each of which specifies a unique column name and the type of the values that are permitted for that column. An attribute value is the entry in a specific column and row.
A database <a href="/facts/Relvar/egcFY101">relvar</a> (relation variable) is commonly known as a base table. The heading of its assigned value at any time is as specified in the table declaration and its body is that most recently assigned to it by an update operator (typically, INSERT, UPDATE, or DELETE). The heading and body of the table resulting from evaluating a query are determined by the definitions of the operators used in that query.

<h3>SQL and the relational model</h3>
SQL, initially pushed as the <a href="/facts/Standardization/vS9AhNMS">standard</a> language for <a href="/facts/Relational_database/pEKGmJLy">relational databases</a>, deviates from the relational model in several places. The current <a href="/facts/International_Organization_for_Standardization/IacYR7Yg">ISO</a> SQL standard doesn't mention the relational model or use relational terms or concepts.
According to the relational model, a Relation's attributes and tuples are <a href="/facts/Set_(mathematics)/BfucfHMq">mathematical sets</a>, meaning they are unordered and unique. In a SQL table, neither rows nor columns are proper sets. A table may contain both duplicate rows and duplicate columns, and a table's columns are explicitly ordered. SQL uses a <a href="/facts/Null_(SQL)/RBnXTe7k">Null</a> value to indicate missing data, which has no analog in the relational model. Because a row can represent unknown information, SQL does not adhere to the relational model's Information Principle.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>: 153–155, 162 

<h2 id="set-theoretic-formulation">Set-theoretic formulation</h2>

Basic notions in the relational model are <a href="/facts/Relation_(database)/Sj67AUyD">relation</a> names and attribute names. We will represent these as strings such as "Person" and "name" and we will usually use the variables 
 
 
 
 r
 ,
 s
 ,
 t
 ,
 …
 
 
 {\displaystyle r,s,t,\ldots }
 
 and 
 
 
 
 a
 ,
 b
 ,
 c
 
 
 {\displaystyle a,b,c}
 
 to range over them. Another basic notion is the set of atomic values that contains values such as numbers and strings.
Our first definition concerns the notion of tuple, which formalizes the notion of row or record in a table:

<a href="/facts/Tuple/BI1HIxL8">Tuple</a>
A tuple is a <a href="/facts/Partial_function/0vJMw0Nm">partial function</a> from attribute names to atomic values.
Header
A header is a finite set of attribute names.
<a href="/facts/Projection_(relational_algebra)/YgQm2wgA">Projection</a>
The projection of a tuple 
 
 
 
 t
 
 
 {\displaystyle t}
 
 on a <a href="/facts/Finite_set/za1newlP">finite set</a> of attributes 
 
 
 
 A
 
 
 {\displaystyle A}
 
 is 
 
 
 
 t
 [
 A
 ]
 =
 {
 (
 a
 ,
 v
 )
 :
 (
 a
 ,
 v
 )
 ∈
 t
 ,
 a
 ∈
 A
 }
 
 
 {\displaystyle t[A]=\{(a,v):(a,v)\in t,a\in A\}}
 
.
The next definition defines relation that formalizes the contents of a table as it is defined in the relational model.

<a href="/facts/Relation_(database)/Sj67AUyD">Relation</a>
A relation is a tuple 
 
 
 
 (
 H
 ,
 B
 )
 
 
 {\displaystyle (H,B)}
 
 with 
 
 
 
 H
 
 
 {\displaystyle H}
 
, the header, and 
 
 
 
 B
 
 
 {\displaystyle B}
 
, the body, a set of tuples that all have the domain 
 
 
 
 H
 
 
 {\displaystyle H}
 
.
Such a relation closely corresponds to what is usually called the extension of a predicate in <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a> except that here we identify the places in the predicate with attribute names. Usually in the relational model a <a href="/facts/Logical_schema/K0EbrogL">database schema</a> is said to consist of a set of relation names, the headers that are associated with these names and the <a href="/facts/Constraint_(database)/pEKGmJLy">constraints</a> that should hold for every instance of the database schema.

Relation universe
A relation universe 
 
 
 
 U
 
 
 {\displaystyle U}
 
 over a header 
 
 
 
 H
 
 
 {\displaystyle H}
 
 is a non-empty set of relations with header 
 
 
 
 H
 
 
 {\displaystyle H}
 
.
Relation schema
A relation schema 
 
 
 
 (
 H
 ,
 C
 )
 
 
 {\displaystyle (H,C)}
 
 consists of a header 
 
 
 
 H
 
 
 {\displaystyle H}
 
 and a predicate 
 
 
 
 C
 (
 R
 )
 
 
 {\displaystyle C(R)}
 
 that is defined for all relations 
 
 
 
 R
 
 
 {\displaystyle R}
 
 with header 
 
 
 
 H
 
 
 {\displaystyle H}
 
. A relation satisfies a relation schema 
 
 
 
 (
 H
 ,
 C
 )
 
 
 {\displaystyle (H,C)}
 
 if it has header 
 
 
 
 H
 
 
 {\displaystyle H}
 
 and satisfies 
 
 
 
 C
 
 
 {\displaystyle C}
 
.
<h3>Key constraints and functional dependencies</h3>
One of the simplest and most important types of relation <a href="/facts/Constraint_(database)/pEKGmJLy">constraints</a> is the key constraint. It tells us that in every instance of a certain relational schema the tuples can be identified by their values for certain attributes.

<a href="/facts/Superkey/SbRlIoXN">Superkey</a>
A superkey is a set of column headers for which the values of those columns concatenated are unique across all rows. Formally:

A superkey is written as a finite set of attribute names.
A superkey 
 
 
 
 K
 
 
 {\displaystyle K}
 
 holds in a relation 
 
 
 
 (
 H
 ,
 B
 )
 
 
 {\displaystyle (H,B)}
 
 if:
<ul><li>
 
 
 
 K
 ⊆
 H
 
 
 {\displaystyle K\subseteq H}
 
 and</li>
<li>there exist no two distinct tuples 
 
 
 
 
 t
 
 1
 
 
 ,
 
 t
 
 2
 
 
 ∈
 B
 
 
 {\displaystyle t_{1},t_{2}\in B}
 
 such that 
 
 
 
 
 t
 
 1
 
 
 [
 K
 ]
 =
 
 t
 
 2
 
 
 [
 K
 ]
 
 
 {\displaystyle t_{1}[K]=t_{2}[K]}
 
.</li></ul>
A superkey holds in a relation universe 
 
 
 
 U
 
 
 {\displaystyle U}
 
 if it holds in all relations in 
 
 
 
 U
 
 
 {\displaystyle U}
 
.
Theorem: A superkey 
 
 
 
 K
 
 
 {\displaystyle K}
 
 holds in a relation universe 
 
 
 
 U
 
 
 {\displaystyle U}
 
 over 
 
 
 
 H
 
 
 {\displaystyle H}
 
 if and only if 
 
 
 
 K
 ⊆
 H
 
 
 {\displaystyle K\subseteq H}
 
 and 
 
 
 
 K
 →
 H
 
 
 {\displaystyle K\rightarrow H}
 
 holds in 
 
 
 
 U
 
 
 {\displaystyle U}
 
.
<a href="/facts/Candidate_key/1SyxFj7C">Candidate key</a>
A candidate key is a superkey that cannot be further subdivided to form another superkey.

A superkey 
 
 
 
 K
 
 
 {\displaystyle K}
 
 holds as a candidate key for a relation universe 
 
 
 
 U
 
 
 {\displaystyle U}
 
 if it holds as a superkey for 
 
 
 
 U
 
 
 {\displaystyle U}
 
 and there is no <a href="/facts/Proper_subset/SJGERmbA">proper subset</a> of 
 
 
 
 K
 
 
 {\displaystyle K}
 
 that also holds as a superkey for 
 
 
 
 U
 
 
 {\displaystyle U}
 
.
<a href="/facts/Functional_dependency/aLfwfUNk">Functional dependency</a>
Functional dependency is the property that a value in a tuple may be derived from another value in that tuple.

A functional dependency (FD for short) is written as 
 
 
 
 X
 →
 Y
 
 
 {\displaystyle X\rightarrow Y}
 
 for 
 
 
 
 X
 ,
 Y
 
 
 {\displaystyle X,Y}
 
 finite sets of attribute names.
A functional dependency 
 
 
 
 X
 →
 Y
 
 
 {\displaystyle X\rightarrow Y}
 
 holds in a relation 
 
 
 
 (
 H
 ,
 B
 )
 
 
 {\displaystyle (H,B)}
 
 if:
<ul><li>
 
 
 
 X
 ,
 Y
 ⊆
 H
 
 
 {\displaystyle X,Y\subseteq H}
 
 and</li>
<li>
 
 
 
 ∀
 
 
 {\displaystyle \forall }
 
 tuples 
 
 
 
 
 t
 
 1
 
 
 ,
 
 t
 
 2
 
 
 ∈
 B
 
 
 {\displaystyle t_{1},t_{2}\in B}
 
, 
 
 
 
 
 t
 
 1
 
 
 [
 X
 ]
 =
 
 t
 
 2
 
 
 [
 X
 ]
  
 ⇒
  
 
 t
 
 1
 
 
 [
 Y
 ]
 =
 
 t
 
 2
 
 
 [
 Y
 ]
 
 
 {\displaystyle t_{1}[X]=t_{2}[X]~\Rightarrow ~t_{1}[Y]=t_{2}[Y]}
 
</li></ul>
A functional dependency 
 
 
 
 X
 →
 Y
 
 
 {\displaystyle X\rightarrow Y}
 
 holds in a relation universe 
 
 
 
 U
 
 
 {\displaystyle U}
 
 if it holds in all relations in 
 
 
 
 U
 
 
 {\displaystyle U}
 
.
Trivial functional dependency
A functional dependency is trivial under a header 
 
 
 
 H
 
 
 {\displaystyle H}
 
 if it holds in all relation universes over 
 
 
 
 H
 
 
 {\displaystyle H}
 
.
Theorem: An FD 
 
 
 
 X
 →
 Y
 
 
 {\displaystyle X\rightarrow Y}
 
 is trivial under a header 
 
 
 
 H
 
 
 {\displaystyle H}
 
 if and only if 
 
 
 
 Y
 ⊆
 X
 ⊆
 H
 
 
 {\displaystyle Y\subseteq X\subseteq H}
 
.
Closure
<a href="/facts/Armstrong%27s_axioms/HRmVPKFh">Armstrong's axioms</a>: The closure of a set of FDs 
 
 
 
 S
 
 
 {\displaystyle S}
 
 under a header 
 
 
 
 H
 
 
 {\displaystyle H}
 
, written as 
 
 
 
 
 S
 
 +
 
 
 
 
 {\displaystyle S^{+}}
 
, is the smallest superset of 
 
 
 
 S
 
 
 {\displaystyle S}
 
 such that:
<ul><li>
 
 
 
 Y
 ⊆
 X
 ⊆
 H
  
 ⇒
  
 X
 →
 Y
 ∈
 
 S
 
 +
 
 
 
 
 {\displaystyle Y\subseteq X\subseteq H~\Rightarrow ~X\rightarrow Y\in S^{+}}
 
 (reflexivity)</li>
<li>
 
 
 
 X
 →
 Y
 ∈
 
 S
 
 +
 
 
 ∧
 Y
 →
 Z
 ∈
 
 S
 
 +
 
 
  
 ⇒
  
 X
 →
 Z
 ∈
 
 S
 
 +
 
 
 
 
 {\displaystyle X\rightarrow Y\in S^{+}\land Y\rightarrow Z\in S^{+}~\Rightarrow ~X\rightarrow Z\in S^{+}}
 
 (transitivity) and</li>
<li>
 
 
 
 X
 →
 Y
 ∈
 
 S
 
 +
 
 
 ∧
 Z
 ⊆
 H
  
 ⇒
  
 (
 X
 ∪
 Z
 )
 →
 (
 Y
 ∪
 Z
 )
 ∈
 
 S
 
 +
 
 
 
 
 {\displaystyle X\rightarrow Y\in S^{+}\land Z\subseteq H~\Rightarrow ~(X\cup Z)\rightarrow (Y\cup Z)\in S^{+}}
 
 (augmentation)</li></ul>
Theorem: Armstrong's axioms are sound and complete; given a header 
 
 
 
 H
 
 
 {\displaystyle H}
 
 and a set 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of FDs that only contain subsets of 
 
 
 
 H
 
 
 {\displaystyle H}
 
, 
 
 
 
 X
 →
 Y
 ∈
 
 S
 
 +
 
 
 
 
 {\displaystyle X\rightarrow Y\in S^{+}}
 
 if and only if 
 
 
 
 X
 →
 Y
 
 
 {\displaystyle X\rightarrow Y}
 
 holds in all relation universes over 
 
 
 
 H
 
 
 {\displaystyle H}
 
 in which all FDs in 
 
 
 
 S
 
 
 {\displaystyle S}
 
 hold.
Completion
The completion of a finite set of attributes 
 
 
 
 X
 
 
 {\displaystyle X}
 
 under a finite set of FDs 
 
 
 
 S
 
 
 {\displaystyle S}
 
, written as 
 
 
 
 
 X
 
 +
 
 
 
 
 {\displaystyle X^{+}}
 
, is the smallest superset of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 such that:
<ul><li>
 
 
 
 Y
 →
 Z
 ∈
 S
 ∧
 Y
 ⊆
 
 X
 
 +
 
 
  
 ⇒
  
 Z
 ⊆
 
 X
 
 +
 
 
 
 
 {\displaystyle Y\rightarrow Z\in S\land Y\subseteq X^{+}~\Rightarrow ~Z\subseteq X^{+}}
 
</li></ul>
The completion of an attribute set can be used to compute if a certain dependency is in the closure of a set of FDs.
Theorem: Given a set 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of FDs, 
 
 
 
 X
 →
 Y
 ∈
 
 S
 
 +
 
 
 
 
 {\displaystyle X\rightarrow Y\in S^{+}}
 
 if and only if 
 
 
 
 Y
 ⊆
 
 X
 
 +
 
 
 
 
 {\displaystyle Y\subseteq X^{+}}
 
.
Irreducible cover
An irreducible cover of a set 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of FDs is a set 
 
 
 
 T
 
 
 {\displaystyle T}
 
 of FDs such that:
<ul><li>
 
 
 
 
 S
 
 +
 
 
 =
 
 T
 
 +
 
 
 
 
 {\displaystyle S^{+}=T^{+}}
 
</li>
<li>there exists no 
 
 
 
 U
 ⊂
 T
 
 
 {\displaystyle U\subset T}
 
 such that 
 
 
 
 
 S
 
 +
 
 
 =
 
 U
 
 +
 
 
 
 
 {\displaystyle S^{+}=U^{+}}
 
</li>
<li>
 
 
 
 X
 →
 Y
 ∈
 T
  
 ⇒
 Y
 
 
 {\displaystyle X\rightarrow Y\in T~\Rightarrow Y}
 
 is a singleton set and</li>
<li>
 
 
 
 X
 →
 Y
 ∈
 T
 ∧
 Z
 ⊂
 X
  
 ⇒
  
 Z
 →
 Y
 ∉
 
 S
 
 +
 
 
 
 
 {\displaystyle X\rightarrow Y\in T\land Z\subset X~\Rightarrow ~Z\rightarrow Y\notin S^{+}}
 
.</li></ul>
<h3>Algorithm to derive candidate keys from functional dependencies</h3>
algorithm derive candidate keys from functional dependencies is
 input: a set S of FDs that contain only subsets of a header H
 output: the set C of superkeys that hold as candidate keys in
 all relation universes over H in which all FDs in S hold

C := ∅ // found candidate keys
 Q := { H } // superkeys that contain candidate keys
 while Q <> ∅ do
 let K be some element from Q
 Q := Q – { K }
 minimal := true
 for each X->Y in S do
 K' := (K – Y) ∪ X // derive new superkey
 if K' ⊂ K then
 minimal := false
 Q := Q ∪ { K' }
 end if
 end for
 if minimal and there is not a subset of K in C then
 remove all supersets of K from C
 C := C ∪ { K }
 end if
 end while

<h2 id="alternatives">Alternatives</h2>
Other <a href="/facts/Database_model/1okm9rHu">models</a> include the <a href="/facts/Hierarchical_database_model/vLzcNqVo">hierarchical model</a> and <a href="/facts/Network_model/3YU8MDPB">network model</a>. Some <a href="/facts/System/hmqQ4ASX">systems</a> using these older architectures are still in use today in <a href="/facts/Data_center/DS5wJY41">data centers</a> with high data volume needs, or where existing systems are so complex and abstract that it would be cost-prohibitive to migrate to systems employing the relational model. Also of note are newer <a href="/facts/Object_database/Vfej0eDT">object-oriented databases</a>.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> and <a href="/facts/Datalog/67jbYWDb">Datalog</a>.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>
Datalog is a database definition language, which combines a relational view of data, as in the relational model, with a logical view, as in <a href="/facts/Logic_programming/Xgh8lj3F">logic programming</a>. Whereas relational databases use a relational calculus or relational algebra, with <a href="/facts/Relational_database/pEKGmJLy">relational operations</a>, such as union, intersection, set difference and cartesian product to specify queries, Datalog uses logical connectives, such as if, or, and and not to define relations as part of the database itself.
In contrast with the relational model, which cannot express recursive queries without introducing a least-fixed-point operator,<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> recursive relations can be defined in Datalog, without introducing any new logical connectives or operators.

<h2 id="see-also">See also</h2>

<ul><li><a href="/facts/Domain_relational_calculus/lwXJ4xEU">Domain relational calculus</a></li>
<li><a href="/facts/List_of_relational_database_management_systems/rWrTfJ7Y">List of relational database management systems</a></li>
<li><a href="/facts/Query_language/Sa6K4xXM">Query language</a>
<ul><li><a href="/facts/Database_query_language/Sa6K4xXM">Database query language</a></li>
<li><a href="/facts/Information_retrieval_query_language/FKShBeSS">Information retrieval query language</a></li></ul></li>
<li><a href="/facts/Relation_(mathematics)/HjblDaMy">Relation</a></li>
<li><a href="/facts/Relational_database/pEKGmJLy">Relational database</a></li>
<li><a href="/facts/Relational_database_management_system/pEKGmJLy">Relational database management system</a></li>
<li><a href="/facts/Tuple-versioning/uwF32kg8">Tuple-versioning</a></li></ul>

<h2 id="notes">Notes</h2>

<h2 id="further-reading">Further reading</h2>
<ul><li><a href="/facts/Christopher_J_Date/qA9FDQuB">Date, Christopher J.</a>; <a href="/facts/Hugh_Darwen/pVF2Iact">Darwen, Hugh</a> (2000). Foundation for future database systems: the third manifesto; a detailed study of the impact of type theory on the relational model of data, including a comprehensive model of type inheritance (2 ed.). Reading, <a href="/facts/Massachusetts/9uumCbFI">MA</a>: Addison-Wesley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-201-70928-5.</li>
<li>——— (2007). <a href="https://archive.org/details/introductiontoda0000date">An Introduction to Database Systems</a> (8 ed.). Boston: Pearson Education. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-321-19784-9.</li></ul>
<h2 id="external-links">External links</h2>

Wikimedia Commons has media related to Relational models.

<ul><li>Childs (1968), Feasibility of a set-theoretic data structure: a general structure based on a reconstituted definition of relation (research), Handle, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/2027.42%2F4164">2027.42/4164</a> cited in Codd's 1970 paper.</li>
<li>Darwen, Hugh, <a href="http://www.thethirdmanifesto.com/">The Third Manifesto (TTM)</a>.</li>
<li><a href="http://c2.com/cgi/wiki?RelationalModel">"Relational Model"</a>, C2.</li>
<li><a href="http://blogs.sun.com/bblfish/entry/why_binary_relations_beat_tuples">Binary relations and tuples compared with respect to the semantic web</a> (<a href="/facts/World_Wide_Web/wvnTrWFq">World Wide Web</a> log), Sun.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Codd, E.F (1969), Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks, Research Report, IBM. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Codd, E.F (1970). "A Relational Model of Data for Large Shared Data Banks". Communications of the ACM. Classics. 13 (6): 377–87. doi:10.1145/362384.362685. S2CID 207549016. <a href="https://doi.org/10.1145%2F362384.362685" target="_blank">https://doi.org/10.1145%2F362384.362685</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Codd, E. F (1990), The Relational Model for Database Management, Addison-Wesley, pp. 371–388, ISBN 978-0-201-14192-4. <a href="978-0-201-14192-4" target="_blank">978-0-201-14192-4</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"Did Date and Darwen's "Third Manifesto" have a lasting impact?". Computer Science Stack Exchange. Retrieved 2024-08-03. <a href="https://cs.stackexchange.com/questions/99350/did-date-and-darwens-third-manifesto-have-a-lasting-impact" target="_blank">https://cs.stackexchange.com/questions/99350/did-date-and-darwens-third-manifesto-have-a-lasting-impact</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Date, Christopher J. (2006). "18. Why Three- and Four-Valued Logic Don't Work". Date on Database: Writings 2000–2006. Apress. pp. 329–41. ISBN 978-1-59059-746-0. <a href="978-1-59059-746-0" target="_blank">978-1-59059-746-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"Tuple in DBMS". GeeksforGeeks. 2023-02-12. Retrieved 2024-08-03. <a href="https://www.geeksforgeeks.org/tuple-in-dbms/" target="_blank">https://www.geeksforgeeks.org/tuple-in-dbms/</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">David M. Kroenke, Database Processing: Fundamentals, Design, and Implementation (1997), Prentice-Hall, Inc., pages 130–144 <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Date, Chris J. (2013). Relational Theory for Computer Professionals: What Relational Databases are Really All About (1. ed.). Sebastopol, Calif: O'Reilly Media. ISBN 978-1-449-36943-9. <a href="978-1-449-36943-9" target="_blank">978-1-449-36943-9</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Atkinson, M., Dewitt, D., Maier, D., Bancilhon, F., Dittrich, K. and Zdonik, S., 1990. The object-oriented database system manifesto. In Deductive and object-oriented databases (pp. 223-240). North-Holland. <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Maier, D., Tekle, K.T., Kifer, M. and Warren, D.S., 2018. Datalog: concepts, history, and outlook. In Declarative Logic Programming: Theory, Systems, and Applications (pp. 3-100). <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Aho, A.V. and Ullman, J.D., 1979, January. Universality of data retrieval languages. In Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (pp. 110-119). <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
</ol>

Relational model open-in-new

Relational model