Relational model: Difference between revisions

Revision as of 21:39, 24 December 2023

Latest revision as of 09:42, 29 July 2025

(43 intermediate revisions by 21 users not shown)

Line 1:

{{short description|Database model}}

The '''relational model''' ('''RM''') is an approach to managing [[data]] using a [[Structure (mathematical logic)|structure]] and language consistent with [[first-order logic|first-order predicate logic]], first described in 1969 by English computer scientist [[Edgar F. Codd]],<ref>{{Citation | title = Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks | first = E.F | last = Codd | publisher = IBM | series = Research Report | year = 1969}}.</ref><ref name="codd1970">{{cite journal |last= Codd |first= E.F |year= 1970 |title= A Relational Model of Data for Large Shared Data Banks |series= Classics |url= http://www.acm.org/classics/nov95/toc.html |journal= [[Communications of the ACM]] |volume= 13 |issue= 6 |pages= 377–87 |doi= 10.1145/362384.362685 |s2cid= 207549016 |url-status= dead |archive-url= https://web.archive.org/web/20070612235326/http://www.acm.org/classics/nov95/toc.html |archive-date= 2007-06-12 |doi-access= free }}</ref> where all data isare represented in terms of [[tuple]]s, grouped into [[relation (database)|relation]]s. A database organized in terms of the relational model is a [[relational database]].

The purpose of the relational model is to provide a [[Declarative programming|declarative]] method for specifying data and queries: users directly state what information the database contains and what information they want from it, and let the [[database management system|database management system software]] take care of describing data structures for storing the data and retrieval procedures for answering queries.

Most relational databases use the [[SQL]] data definition and query language; these systems implement what can be regarded as an engineering approximation to the relational model. A ''[[Table (database)|table]]'' in a SQL [[database schema]] corresponds to a predicate variable; the contents of a table to a relation; key constraints, other constraints, and SQL queries correspond to predicates. However, SQL databases [[#SQL and the relational model|deviate from the relational model in many details]], and Codd fiercely argued against deviations that compromise the original principles.<ref>{{Citation | first = E. F | last = Codd | title = The Relational Model for Database Management | publisher = Addison-Wesley | year = 1990 | isbn = 978-0-201-14192-4 | pages=371–388}}.</ref>

== OverviewHistory ==

The relational model was developed by [[Edgar F. Codd]] as a general model of data, and subsequently promoted by [[Christopher J. Date|Chris Date]] and [[Hugh Darwen]] among others. In their 1995 ''The Third Manifesto'', Date and Darwen try to demonstrate how the relational model can accommodate certain "desired" [[Object-oriented programming|object-oriented]] features.<ref>{{Cite web |title=Did Date and Darwen's "Third Manifesto" have a lasting impact? |url=https://cs.stackexchange.com/questions/99350/did-date-and-darwens-third-manifesto-have-a-lasting-impact |access-date=2024-08-03 |website=Computer Science Stack Exchange |language=en}}</ref>

The central idea of a relational model is to describe a database as a collection of [[Predicate (mathematical logic)|predicate]]s over a finite set of predicate variables, describing [[constraint (database)|constraints]] on the possible values and combinations of values. The content of the database at any given time is a finite (logical) [[model (logic)|model]] of the database, i.e. a set of [[Relation (database)|relation]]s, one per predicate variable, such that all predicates are satisfied. A request for information from the database (a [[database query]]) is also a predicate.

[[File:Relational model concepts.png|thumb|360px|Relational model concepts.]]

=== Extensions ===

Some years after publication of his 1970 model, Codd proposed a [[three-valued logic]] (True, False, Missing/[[Null (SQL)|NULL]]) 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.<ref>{{cite book| first =Christopher J. | last = Date|title=Date on Database: Writings 2000–2006|date= 2006 |publisher= Apress|isbn= 978-1-59059-746-0|pages=329–41|chapter= 18. Why Three- and Four-Valued Logic Don't Work}}</ref>

== Conceptualization ==

=== Basic concepts ===

[[File:Relational database terms.svg|thumb|A relation with 5 attributes (its degree) and 4 tuples (its cardinality) can be visualized as a table with 5 columns and 4 rows. However, unlike rows and columns in a table, a relation's attributes and tuples are unordered.]]

A ''relation'' consists of a ''heading'' and a ''body''. The heading defines a [[Set (mathematics)|set]] 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 ''[[arity]]''. 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.<ref>{{Cite web |date=2023-02-12 |title=Tuple in DBMS |url=https://www.geeksforgeeks.org/tuple-in-dbms/ |access-date=2024-08-03 |website=GeeksforGeeks |language=en-US}}</ref> The number of tuples in this set is the relation's ''[[cardinality]]''.<ref name="professionals"/>{{rp|17–22}}

== History ==

The relational model was developed by [[Edgar F. Codd]] as a general model of data, and subsequently promoted by [[Christopher J. Date|Chris Date]] and [[Hugh Darwen]] among others. In their 1995 ''The Third Manifesto'', Date and Darwen try to demonstrate how the relational model can accommodate certain "desired" [[object-oriented]] features.

=== Extensions ===

Some years after publication of his 1970 model, Codd proposed a [[three-valued logic]] (True, False, Missing/[[Null (SQL)|NULL]]) 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.<ref>{{cite book| first =Christopher J. | last = Date|title=Date on Database: Writings 2000–2006|date= 2006 |publisher= Apress|isbn= 978-1-59059-746-0|pages=329–41|chapter= 18. Why Three- and Four-Valued Logic Don't Work}}</ref>

== Topics ==

The fundamental assumption behind a relational model is that all [[data]] is represented as mathematical ''n''-[[arity|ary]] '''[[Relation (database)|relation]]s''', an ''n''-ary relation being a [[subset]] of the [[Cartesian product]] of ''n'' domains. In the mathematical model, [[reasoning]] about such data is done in two-valued [[predicate logic]], meaning there are two possible [[evaluation]]s for each [[proposition]]: either ''true'' or ''false'' (and in particular no third value such as ''unknown'', or ''not applicable'', either of which are often associated with the concept of [[Null (SQL)|NULL]]). Data are operated upon by means of a [[relational calculus]] or [[relational algebra]], these being equivalent in [[expressive power (computer science)|expressive power]].

Relations are represented by ''relational [[Variable (computer science)|variables]]'' or ''relvars'', which can be reassigned.<ref name="professionals"/>{{rp|22–24}} A ''[[database]]'' is a collection of relvars.<ref name="professionals"/>{{rp|112–113}}

The relational model of data permits the database designer to create a consistent, logical representation of [[information]]. Consistency is achieved by including declared '''''[[constraint (database)|constraint]]s''''' in the database design, which is usually referred to as the ''logical schema''. The theory includes a process of [[database normalization]] whereby a design with certain desirable properties can be selected from a set of [[Logical equivalence|logically equivalent]] alternatives. The [[access plan]]s and other implementation and operation details are handled by the [[DBMS]] engine, and are not reflected in the logical model.

In this model, databases follow the ''Information Principle'': At any given time, all [[Information theory|information]] in the database is represented solely by values within tuples, corresponding to attributes, in relations identified by relvars.<ref name="professionals"/>{{rp|111}}

The basic relational building block is the [[Data ___domain|___domain]] or [[data type]], usually abbreviated nowadays to '''''type'''''. A ''[[tuple]]'' is an unordered [[set (mathematics)|set]] of '''''attribute values'''''. An [[Attribute (computing)|attribute]] is an unordered pair of '''''attribute name''''' and '''''type name'''''. An attribute value is a specific valid value for the type of the attribute. This can be either a scalar value or a more complex type.

=== Constraints ===

A relation consists of a '''''heading''''' and a '''''body'''''. A heading is a set of attributes. A body (of an ''n''-ary relation) is a set of ''n''-tuples. The heading of the relation is also the heading of each of its tuples.

A database may define arbitrary [[boolean expressions]] as [[constraint (database)|constraints]]. 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.<ref name="professionals"/>{{rp|91}}

A relation is defined as a [[set (mathematics)|set]] of ''n''-tuples. In both mathematics and the relational database model, a set is an ''unordered'' collection of unique, non-duplicated items, although some DBMSs impose an order to their data. In mathematics, a [[tuple]] has an order, and allows for duplication. [[Edgar F. Codd|E.{{nbsp}}F. Codd]] originally defined tuples using this mathematical definition.<ref name= "codd1970"/> Later, it was one of [[Edgar F. Codd|E.{{nbsp}}F. Codd]]'s great insights that using attribute names instead of an ordering would be more convenient (in general) in a computer language based on relations {{Citation needed |date= February 2007}}. This insight is still being used today. Though the concept has changed, the name "tuple" has not. An immediate and important consequence of this distinguishing feature is that in the relational model the [[Cartesian product]] becomes [[Commutative operation|commutative]].

In general, constraints are expressed using relational comparison operators, of which just one, "is subset of" (⊆), is theoretically sufficient.{{Citation needed|reason=This should be explained, because it is interesting enough to read more about it|date=August 2010}}

A ''[[relvar]]'' is a named variable of some specific relation type, to which at all times some relation of that type is assigned, though the relation may contain zero tuples.

Two special cases of constraints are expressed as ''keys'' and ''foreign keys'':

The basic principle of the relational model is the [[Information Principle]]: all [[information]] is represented by data values in relations. In accordance with this Principle, a [[relational database]] is a set of relvars and the result of every query is presented as a relation.

==== Keys ====

The consistency of a relational database is enforced, not by rules built into the applications that use it, but rather by ''[[constraint (database)|constraint]]s'', declared as part of the logical schema and enforced by the [[DBMS]] for all applications. In general, constraints are expressed using relational comparison operators, of which just one, "is subset of" (⊆), is theoretically sufficient{{Citation needed|reason=This should be explained, because it is interesting enough to read more about it|date=August 2010}}. In practice, several useful shorthands are expected to be available, of which the most important are [[candidate key]] (really, [[superkey]]) and [[foreign key]] constraints.

A ''candidate key'', or simply a ''key'', is the smallest [[subset]] 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.<ref name="professionals"/>{{rp|31–33}}

=== Interpretation ===

To fully appreciate the relational model of data it is essential to understand the intended ''interpretation'' of a [[relation (database)|relation]].

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.<ref name="professionals"/>{{rp|31–33}}

The body of a relation is sometimes called its extension. This is because it is to be interpreted as a representation of the [[extension (predicate logic)|extension]] of some [[Predicate (logic)|predicate]], this being the set of true [[proposition]]s that can be formed by replacing each [[free variable]] in that predicate by a name (a term that designates something).

==== Foreign keys ====

There is a [[bijection|one-to-one correspondence]] between the free variables of the predicate and the attribute names of the relation heading. Each tuple of the relation body provides attribute values to instantiate the predicate by substituting each of its free variables. The result is a proposition that is deemed, on account of the appearance of the tuple in the relation body, to be true. Contrariwise, every tuple whose heading conforms to that of the relation, but which does not appear in the body is deemed to be false. This assumption is known as the [[closed world assumption]].

{{main|Foreign key}}

A ''foreign key'' is a subset of attributes ''A'' in a relation ''R₁'' that corresponds with a key of another relation ''R₂'', with the property that the [[Projection (relational algebra)|projection]] of ''R₁'' on ''A'' is a subset of the projection of ''R₂'' on ''A''. In other words, if a tuple in ''R₁'' contains values for a foreign key, there must be a corresponding tuple in ''R₂'' containing the same values for the corresponding key.<ref name="professionals"/>{{rp|34}}

For a formal exposition of these ideas, see the section [[Relational model#Set-theoretic formulation|Set-theoretic Formulation]], below.

=== Relational operations ===

Line 50 ⟶ 47:

Often, data from multiple tables are combined into one, by doing a [[Join (SQL)|join]]. Conceptually, this is done by taking all possible combinations of rows (the [[Cartesian product]]), 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&nbsp;– 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 [[relation (database)|relation]] 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.

Line 57 ⟶ 54:

{{Main|Database normalization}}

[[Relation (database)|Relation]]s are classified based upon the types of anomalies to which they're vulnerable. A database that is in the [[first normal form]] 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.<ref name="Normalization">David M. Kroenke, ''Database Processing: Fundamentals, Design, and Implementation'' (1997), Prentice-Hall, Inc., pages 130–144</ref>

== Logical interpretation ==

The relational model is a [[formal system]]. A relation's attributes define a set of [[logic]]al [[propositions]]. 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. [[Relational algebra]] is a set of logical rules that can [[Validity (logic)|validly]] [[inference|infer]] conclusions from these propositions.<ref name="professionals"/>{{rp|95–101}}

The definition of a ''tuple'' allows for a unique empty tuple with no values, corresponding to the [[empty set]] 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 [[Boolean ___domain|Boolean]] [[truth values]]. The relation with degree 0 and cardinality 0 is ''False'', while the relation with degree 0 and cardinality 1 is ''True''.<ref name="professionals"/>{{rp|221–223}}

=== Example ===

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).<ref name="professionals"/>{{rp|96–97}}

Furthermore, if ''{ID}'' is a key, then a relation containing the tuples ''{Alice, 1}'' and ''{Bob, 1}'' would represent the following [[contradiction]]:

# There exists an employee with the name ''Alice'' and the ID ''1''.

# There exists an employee with the name ''Bob'' and the ID ''1''.

# There do not exist multiple employees with the same ID.

Under the [[principle of explosion]], this contradiction would allow the system to prove that any arbitrary proposition is true. The database must enforce the key constraint to prevent this.<ref name="professionals"/>{{rp|104}}

== Examples ==

Line 94 ⟶ 108:

Now, the Order relvar has a ''[[One-to-many (data model)|one-to-many relationship]]'' 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 '''<u>Order ID</u>''' in the Order relation equals the '''<u>Order ID</u>''' in OrderInvoice, and where '''<u>Invoice ID</u>''' in OrderInvoice equals the '''<u>Invoice ID</u>''' in Invoice.

== Application to relational databases ==

A '''[[data ___domain|data type]]''' as used in a typical relational database might be the set of integers, the set of character strings, the set of dates, or the two [[Boolean value]]s ''true'' and ''false'', and so onetc. The corresponding '''type names''' for these types might be the strings "int", "char", "date", "boolean", etc. It is important to understand, though, that relational theorymodel does not dictate what types are to be supported; indeed, nowadays provisions are expected to be available for ''user-defined'' types in addition to the ''built-in'' ones provided by the system.

'''Attributes''' are commonly represented as '''[[Column (database)|Attributecolumns]]''', is the term used in the theory for what is commonly referred to'''tuples''' as a '''column[[row (database)|rows]]'''. Similarly, and '''tablerelations''' is commonly used in place of the theoretical termas '''relationtables''' (though in SQL the term is by no means synonymous with relation). A table data structure 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, such as "John Doe" or "35".

A database '''[[relvar]]''' (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.

A '''[[tuple]]''' is basically the same thing as a '''[[row (database)|row]]''', except in an SQL DBMS, where the column values in a row are ordered. (Tuples are not ordered; instead, each attribute value is identified solely by the '''attribute name''' and never by its ordinal position within the tuple.) An attribute name might be "name" or "age".

A '''[[relation (database)|relation]]''' is a '''[[table (database)|table]]''' structure definition (a set of column definitions) along with the data appearing in that structure. The structure definition is the '''heading''' and the data appearing in it is the '''body''', a set of rows. A database '''[[relvar]]''' (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 invoking some '''update operator''' (typically, INSERT, UPDATE, or DELETE). The heading and body of the table resulting from evaluation of some query are determined by the definitions of the operators used in the expression of that query. (Note that in SQL the heading is not always a set of column definitions as described above, because it is possible for a column to have no name and also for two or more columns to have the same name. Also, the body is not always a set of rows because in SQL it is possible for the same row to appear more than once in the same body.)

=== SQL and the relational model ===

SQL, initially pushed as the [[standardization|standard]] language for [[relational database]]s, deviates from the relational model in several places. The current [[International Organization for Standardization|ISO]] SQL standard doesn't mention the relational model or use relational terms or concepts.{{cncitation needed|date=December 2023}}

According to the relational model, a Relation's attributes and tuples are [[Set (mathematics)|mathematical sets]], 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 [[Null (SQL)|Null]] 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''.<ref name="professionals">{{cite book |last1=Date |first1=Chris J. |title=Relational Theory for Computer Professionals: What Relational Databases are Really All About |date=2013 |publisher=O'Reilly Media |___location=Sebastopol, Calif |isbn=978-1-449-36943-9 |edition=1.}}</ref>{{rp|153-155153–155,162}}

== Set-theoretic formulation ==

Line 201 ⟶ 213:

== Alternatives ==

Other [[Database model|models]] include the [[Hierarchical database model|hierarchical model]] and [[network model]]. Some [[system]]s using these older architectures are still in use today in [[data center]]s 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 [[object database|object-oriented databases]].{{cn}}<ref>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.</ref> and [[Datalog]].<ref>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).</ref>

''Datalog'' is a database definition language, which combines a relational view of data, as in the relational model, with a logical view, as in [[logic programming]]. Whereas relational databases use a relational calculus or relational algebra, with [[Relational database#Relational operations|relational operations]], 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,<ref>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).</ref> recursive relations can be defined in Datalog, without introducing any new logical connectives or operators.

== See also ==

Line 215 ⟶ 231:

* [[Tuple-versioning]]

{{div col end}}

== HistoryNotes ==

{{reflist|group=nb}}

== References ==

Line 227 ⟶ 246:

* {{Citation | publisher = Handle | title = Feasibility of a set-theoretic data structure: a general structure based on a reconstituted definition of relation | last = Childs | year = 1968 | type = research| hdl = 2027.42/4164 }} cited in Codd's 1970 paper.

* {{Citation | last = Darwen | first = Hugh | url = http://www.thethirdmanifesto.com/ | title = The Third Manifesto (TTM)}}.

* {{dmoz|Computers/Software/Databases/Relational|Relational Databases}}

* {{Citation | contribution-url = http://c2.com/cgi/wiki?RelationalModel | contribution = Relational Model | title = C2}}.

* {{Citation | url = http://blogs.sun.com/bblfish/entry/why_binary_relations_beat_tuples | title = Binary relations and tuples compared with respect to the semantic web | publisher = Sun | type = [[World Wide Web]] log}}.

Line 239 ⟶ 257:

[[Category:Articles with example pseudocode]]

[[Category:Programming paradigms]]

[[Category:Database management systems]]