العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolRELATIONAL MODEL
(Redirected from Relational model of database management)
The 'relational model' for database management is a database model based on predicate logic and set theory. It was first formulated and proposed in 1969 by Edgar Codd with aims that included avoiding, without loss of completeness, the need to write computer programs to express database queries and enforce database integrity constraints. "Relation" is a mathematical term for "table", and thus "relational" roughly means "based on tables". It does not refer to the links or "keys" between tables, contrary to popular belief.
Codd's original description of the relational model, ''"Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks"'', was published in an IBM Research Report in 1969. A revised version of this paper, the highly acclaimed ''"A Relational Model of Data for Large Shared Data Banks"'', was published in Communications of the ACM the following year.[1]
The fundamental assumption of the relational model is that all data are represented as mathematical ''n''-ary 'relations', 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 evaluations 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). Some think that logic (which is inherently two-valued) is an important part of the relational model, where others think that a system that uses a form of three-valued logic can still be considered relational.
Data are operated upon by means of a relational calculus or algebra, these being equivalent in expressive power.
The relational model of data permits the database designer to create a consistent, logical representation of information. Consistency is achieved by including declared '''constraints''' 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 logically equivalent alternatives. The access plans and other implementation and operation details are handled by the DBMS engine, and are not reflected in the logical model. This contrasts with common practice for SQL DBMSs in which performance tuning often requires changes to the logical model.
The basic relational building block is the domain or data type, usually abbreviated nowadays to '''type'''. A ''tuple'' is an unordered set of '''attribute values'''. An attribute is an ordered 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.
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 relation is defined as a set of ''n''-tuples. In both mathematics and the relational database model, a set is an ''unordered'' collection of items, although some DBMSs impose an order to their data. In mathematics, a tuple has an order, and allows for duplication. E.F. Codd originally defined tuples using this mathematical definition.[2] Later, it was one of E.F. Codd's great insights that using attribute names instead of an ordering would be so much more convenient (in general) in a computer language based on relations . 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.
A table is an accepted visual representation of a relation; a tuple is similar to the concept of ''row'', but note that in the database language SQL the columns and the rows of a table are ordered.
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.
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.
The consistency of a relational database is enforced, not by rules built into the applications that use it, but rather by ''constraints'', 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. In practice, several useful shorthands are expected to be available, of which the most important are candidate key (really, superkey) and foreign key constraints.
To fully appreciate the relational model of data it is essential to understand the intended '''interpretation''' of a relation.
The body of a relation is sometimes called its extension. This is because it is to be interpreted as a representation of the extension of some predicate, this being the set of true propositions that can be formed by replacing each free variable in that predicate by a name (a term that designates something).
There is a 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.
For a formal exposition of these ideas, see the section 'Set Theory Formulation', below.
A '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 values ''true'' and ''false'', and so on. The corresponding 'type names' for these types might be the strings "int", "char", "date", "boolean", etc. It is important to understand, though, that relational theory 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.
'Attribute' is the term used in the theory for what is commonly referred to as a 'column'. Similarly, 'table' is commonly used in place of the theoretical term 'relation' (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 'tuple' is basically the same thing as a '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' is a '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.)
Other models are the hierarchical model and network model. Some systems using these older architectures are still in use today in data centers with high data volume needs or where existing systems are so complex and abstract it would be cost prohibitive to migrate to systems employing the relational model; also of note are newer object-oriented databases, even though many of them are DBMS-construction kits, rather than proper DBMSs.
The relational model was the first formal database model. After it was defined, informal models were made to describe hierarchical databases (the hierarchical model) and network databases (the network model). Hierarchical and network databases existed ''before'' relational databases, but were only described as models ''after'' the relational model was defined, in order to establish a basis for comparison.
The relational model was invented by E.F. (Ted) Codd as a general model of data, and subsequently maintained and developed by Chris Date and Hugh Darwen among others. In The Third Manifesto (first published in 1995) Date and Darwen show how the relational model can accommodate certain desired object-oriented features without compromising its fundamental principles.
The foundation for the relational model included important works published by Georg Cantor (1874) and D.L. Childs (1968). Cantor was a 19th century German mathematician who published a number of articles and was the principal creator of set theory. Childs is an American mathematician whose "Description of a Set-Theoretic Data Structure" was cited by Codd in his seminal 1970 paper "A Relational Model of Data for Large Shared Data Banks". Childs' STDS uses set theory as the basis for querying data using set operations such as union, intersection, domain, range, restriction, cardinality and Cartesian product. The use of sets and set operations provided independence from physical data structures, a pioneering concept at the time.
SQL, initially pushed as the standard language for relational databases, deviates from the relational model in several places. The current ISO SQL standard doesn't mention the relational model or use relational terms or concepts. However, it is possible to create a database conforming to the relational model using SQL if one does not use certain SQL features.
The following deviations from the relational model have been noted in SQL. Note that few database servers implement the entire SQL standard and in particular do not allow some of these deviations. Whereas NULL is nearly ubiquitous, for example, allowing duplicate column names within a table or anonymous columns is uncommon.
;Duplicate rows
:The same row can appear more than once in an SQL table. The same tuple cannot appear more than once in a relation.
;Anonymous columns
:A column in an SQL table can be unnamed and thus unable to be referenced in expressions. The relational model requires every attribute to be named and referenceable.
;Duplicate column names
:Two or more columns of the same SQL table can have the same name and therefore cannot be referenced, on account of the obvious ambiguity. The relational model requires every attribute to be referenceable.
;Column order significance
:The order of columns in an SQL table is defined and significant, one consequence being that SQL's implementations of Cartesian product and union are both noncommutative. The relational model requires there to be no significance to any ordering of the attributes of a relation.
;Views without CHECK OPTION
:Updates to a view defined without CHECK OPTION can be accepted but the resulting update to the database does not necessarily have the expressed effect on its target. For example, an invocation of INSERT can be accepted but the inserted rows might not all appear in the view, or an invocation of UPDATE can result in rows disappearing from the view. The relational model requires updates to a view to have the same effect as if the view were a base relvar.
;Columnless tables unrecognized
:SQL requires every table to have at least one column, but there are two relations of degree zero (of cardinality one and zero) and they are needed to represent extensions of predicates that contain no free variables.
;NULL
:This special mark can appear instead of a value wherever a value can appear in SQL, in particular in place of a column value in some row. The deviation from the relational model arises from the fact that the implementation of this ''ad hoc'' concept in SQL involves the use of three-valued logic, under which the comparison of NULL with itself does not yield ''true'' but instead yields the third truth value, ''unknown''; similarly the comparison NULL with something other than itself does not yield ''false'' but instead yields ''unknown''. It is because of this behaviour in comparisons that NULL is described as a mark rather than a value. The relational model depends on the law of excluded middle under which anything that is not true is false and anything that is not false is true; it also requires every tuple in a relation body to have a value for every attribute of that relation. This particular deviation is disputed by some if only because E.F. Codd himself eventually advocated the use of special marks and a 4-valued logic, but this was based on his observation that there are two distinct reasons why one might want to use a special mark in place of a value, which led opponents of the use of such logics to discover more distinct reasons and at least as many as 19 have been noted, which would require a 21-valued logic. SQL itself uses NULL for several purposes other than to represent "value unknown". For example, the sum of the empty set is NULL, meaning zero, the average of the empty set is NULL, meaning undefined, and NULL appearing in the result of a LEFT JOIN can mean "no value because there is no matching row in the right-hand operand".
;Concepts
:SQL uses concepts "table", "column", "row" instead of "relvar", "attribute", "tuple". These are not merely differences in terminology. For example, a "table" may contain duplicate rows, whereas the same tuple cannot appear more than once in a relation.
There have been several attempts to produce a true implementation of the relational database model as originally defined by Codd and explained by Date, Darwen and others, but none have been popular successes so far. Rel is one of the more recent attempts to do this.
Codd himself, some years after publication of his 1970 model, proposed a three-valued logic (True, False, Missing or NULL) version of it in order 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. But these have never been implemented, presumably because of attending complexity. SQL's NULL construct was intended to be part of a three-valued logic system, but fell short of that due to logical errors in the standard and in its implementations. See the section "SQL standard", above.
Database normalization is usually performed when designing a relational database, to improve the logical consistency of the database design and the transactional performance.
There are two commonly used systems of diagramming to aid in the visual representation of the relational model: the entity-relationship diagram (ERD), and the related IDEF diagram used in the IDEF1X method created by the U.S. Air Force based on ERDs.
The tree structure of data may enforce hierarchical model organization, with parent-child relationship table.
An idealized, very simple example of a description of some relvars and their attributes:
★ Customer('Customer ID', Tax ID, Name, Address, City, State, Zip, Phone)
★ Order('Order No', Customer ID, Invoice No, Date Placed, Date Promised, Terms, Status)
★ Order Line('Order No', 'Order Line No', Product Code, Qty)
★ Invoice('Invoice No', Customer ID, Order No, Date, Status)
★ Invoice Line('Invoice No', 'Line No', Product Code, Qty Shipped)
★ Product('Product Code', Product Description)
In this design we have six relvars: Customer, Order, Order Line, Invoice, Invoice Line and Product. The bold, underlined attributes are ''candidate keys''. The non-bold, underlined attributes are ''foreign keys''.
Usually one candidate key is arbitrarily chosen to be called the primary key and used in preference over the other candidate keys, which are then called alternate keys.
A ''candidate key'' is a unique identifier enforcing that no tuple will be duplicated; this would make the relation into something else, namely a bag, by violating the basic definition of a set. Both foreign keys and superkeys (which 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.
If we attempted to ''insert'' a new customer with the ID ''1234567890'', this would violate the design of the relvar since 'Customer ID' is a ''primary key'' and we already have a customer ''1234567890''. The DBMS must reject a transaction such as this that would render the database inconsistent by a violation of an integrity constraint.
''Foreign keys'' are integrity constraints enforcing that the value of the attribute set is drawn from a ''candidate key'' in another relation, for example in the Order relation the attribute 'Customer ID' is a foreign key. A ''join'' is the operation that draws on information 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 ''1234567890'', we could query the database to return every row in the Order table with 'Customer ID' ''1234567890'' and join the Order table to the Order Line table based on 'Order No'.
There is a flaw in our database design above. The Invoice relvar contains an Order No attribute. So, each tuple in the Invoice relvar will have one Order No, 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 No 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 'many-to-many' 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 role is to specify the correspondence between Orders and Invoices:
OrderInvoice('Order No','Invoice No')
Now, the Order relvar has a ''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 'Order No' in the Order relation equals the 'Order No' in OrderInvoice, and where 'Invoice No' in OrderInvoice equals the 'Invoice No' in Invoice.
Basic notions in the relational model are ''relation names'' and ''attribute names''. We will represent these as strings such as "Person" and "name" and we will usually use the variables and 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:
; Tuple
: A tuple is a partial function from attribute names to atomic values.
; Header
: A header is a finite set of attribute names.
; Projection
: The projection of a tuple on a finite set of attributes is .
The next definition defines ''relation'' which formalizes the contents of a table as it is defined in the relational model.
; Relation
: A relation is a tuple with , the header, and , the body, a set of tuples that all have the domain .
Such a relation closely corresponds to what is usually called the extension of a predicate in first-order logic except that here we identify the places in the predicate with attribute names. Usually in the relational model a database schema is said to consist of a set of relation names, the headers that are associated with these names and the constraints that should hold for every instance of the database schema.
; Relation universe
: A relation universe over a header is a non-empty set of relations with header .
; Relation schema
: A relation schema consists of a header and a predicate that is defined for all relations with header . A relation satisfies a relation schema if it has header and satisfies .
One of the simplest and most important types of relation constraints 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.
; Superkey
: A superkey is written as a finite set of attribute names.
: A superkey holds in a relation if:
:
★ and
:
★ there exist no two distinct tuples such that .
: A superkey holds in a relation universe if it holds in all relations in .
: 'Theorem:' A superkey holds in a relation universe over if and only if and holds in .
; Candidate key
: A superkey holds as a candidate key for a relation universe if it holds as a superkey for and there is no proper subset of that also holds as a superkey for .
; Functional dependency
: A functional dependency (FD for short) is written as for finite sets of attribute names.
: A functional dependency holds in a relation if:
:
★ and
:
★ tuples ,
: A functional dependency holds in a relation universe if it holds in all relations in .
; Trivial functional dependency
: A functional dependency is trivial under a header if it holds in all relation universes over .
: 'Theorem:' An FD is trivial under a header if and only if .
; Closure
: Armstrong's axioms: The closure of a set of FDs under a header , written as , is the smallest superset of such that:
:
★ (reflexivity)
:
★ (transitivity) and
:
★ (augmentation)
: 'Theorem:' Armstrong's axioms are sound and complete; given a header and a set of FDs that only contain subsets of , if and only if holds in all relation universes over in which all FDs in hold.
; Completion
: The completion of a finite set of attributes under a finite set of FDs , written as , is the smallest superset of such that:
:
★
: 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 of FDs, if and only if .
; Irreducible cover
: An irreducible cover of a set of FDs is a set of FDs such that:
:
★
:
★ there exists no such that
:
★ is a singleton set and
:
★ .
'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
'begin'
''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'
'end'
1. White, Colin. ''In the Beginning: An RDBMS History''. Teradata Magazine Online. September 2004 edition. URL: [http://www.teradata.com/t/page/127057]
2. A Relational Model of Data for Large Shared Data Banks, , E.F., Codd, Communications of the ACM, 1970
★ Codd, E. F. (1970). "A relational model of data for large shared data banks". ''Communications of the ACM'', 13(6):377–387. (Retrieved from ACM, September 4, 2004.)
★ Date, C. J., Darwen, H. (2000). ''Foundation for Future Database Systems: The Third Manifesto'', 2nd edition, Addison-Wesley Professional. ISBN 0-201-70928-7.
★ Date, C. J. (2003). ''Introduction to Database Systems''. 8th edition, Addison-Wesley. ISBN 0-321-19784-4.
★ The Third Manifesto (TTM)
★ DMoz category
★ Relational Model
The 'relational model' for database management is a database model based on predicate logic and set theory. It was first formulated and proposed in 1969 by Edgar Codd with aims that included avoiding, without loss of completeness, the need to write computer programs to express database queries and enforce database integrity constraints. "Relation" is a mathematical term for "table", and thus "relational" roughly means "based on tables". It does not refer to the links or "keys" between tables, contrary to popular belief.
Codd's original description of the relational model, ''"Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks"'', was published in an IBM Research Report in 1969. A revised version of this paper, the highly acclaimed ''"A Relational Model of Data for Large Shared Data Banks"'', was published in Communications of the ACM the following year.[1]
The model
The fundamental assumption of the relational model is that all data are represented as mathematical ''n''-ary 'relations', 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 evaluations 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). Some think that logic (which is inherently two-valued) is an important part of the relational model, where others think that a system that uses a form of three-valued logic can still be considered relational.
Data are operated upon by means of a relational calculus or algebra, these being equivalent in expressive power.
The relational model of data permits the database designer to create a consistent, logical representation of information. Consistency is achieved by including declared '''constraints''' 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 logically equivalent alternatives. The access plans and other implementation and operation details are handled by the DBMS engine, and are not reflected in the logical model. This contrasts with common practice for SQL DBMSs in which performance tuning often requires changes to the logical model.
The basic relational building block is the domain or data type, usually abbreviated nowadays to '''type'''. A ''tuple'' is an unordered set of '''attribute values'''. An attribute is an ordered 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.
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 relation is defined as a set of ''n''-tuples. In both mathematics and the relational database model, a set is an ''unordered'' collection of items, although some DBMSs impose an order to their data. In mathematics, a tuple has an order, and allows for duplication. E.F. Codd originally defined tuples using this mathematical definition.[2] Later, it was one of E.F. Codd's great insights that using attribute names instead of an ordering would be so much more convenient (in general) in a computer language based on relations . 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.
A table is an accepted visual representation of a relation; a tuple is similar to the concept of ''row'', but note that in the database language SQL the columns and the rows of a table are ordered.
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.
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.
The consistency of a relational database is enforced, not by rules built into the applications that use it, but rather by ''constraints'', 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. In practice, several useful shorthands are expected to be available, of which the most important are candidate key (really, superkey) and foreign key constraints.
Interpretation
To fully appreciate the relational model of data it is essential to understand the intended '''interpretation''' of a relation.
The body of a relation is sometimes called its extension. This is because it is to be interpreted as a representation of the extension of some predicate, this being the set of true propositions that can be formed by replacing each free variable in that predicate by a name (a term that designates something).
There is a 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.
For a formal exposition of these ideas, see the section 'Set Theory Formulation', below.
Application to databases
A '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 values ''true'' and ''false'', and so on. The corresponding 'type names' for these types might be the strings "int", "char", "date", "boolean", etc. It is important to understand, though, that relational theory 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.
'Attribute' is the term used in the theory for what is commonly referred to as a 'column'. Similarly, 'table' is commonly used in place of the theoretical term 'relation' (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 'tuple' is basically the same thing as a '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' is a '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.)
Competition
Other models are the hierarchical model and network model. Some systems using these older architectures are still in use today in data centers with high data volume needs or where existing systems are so complex and abstract it would be cost prohibitive to migrate to systems employing the relational model; also of note are newer object-oriented databases, even though many of them are DBMS-construction kits, rather than proper DBMSs.
The relational model was the first formal database model. After it was defined, informal models were made to describe hierarchical databases (the hierarchical model) and network databases (the network model). Hierarchical and network databases existed ''before'' relational databases, but were only described as models ''after'' the relational model was defined, in order to establish a basis for comparison.
History
The relational model was invented by E.F. (Ted) Codd as a general model of data, and subsequently maintained and developed by Chris Date and Hugh Darwen among others. In The Third Manifesto (first published in 1995) Date and Darwen show how the relational model can accommodate certain desired object-oriented features without compromising its fundamental principles.
The foundation for the relational model included important works published by Georg Cantor (1874) and D.L. Childs (1968). Cantor was a 19th century German mathematician who published a number of articles and was the principal creator of set theory. Childs is an American mathematician whose "Description of a Set-Theoretic Data Structure" was cited by Codd in his seminal 1970 paper "A Relational Model of Data for Large Shared Data Banks". Childs' STDS uses set theory as the basis for querying data using set operations such as union, intersection, domain, range, restriction, cardinality and Cartesian product. The use of sets and set operations provided independence from physical data structures, a pioneering concept at the time.
SQL standard
SQL, initially pushed as the standard language for relational databases, deviates from the relational model in several places. The current ISO SQL standard doesn't mention the relational model or use relational terms or concepts. However, it is possible to create a database conforming to the relational model using SQL if one does not use certain SQL features.
The following deviations from the relational model have been noted in SQL. Note that few database servers implement the entire SQL standard and in particular do not allow some of these deviations. Whereas NULL is nearly ubiquitous, for example, allowing duplicate column names within a table or anonymous columns is uncommon.
;Duplicate rows
:The same row can appear more than once in an SQL table. The same tuple cannot appear more than once in a relation.
;Anonymous columns
:A column in an SQL table can be unnamed and thus unable to be referenced in expressions. The relational model requires every attribute to be named and referenceable.
;Duplicate column names
:Two or more columns of the same SQL table can have the same name and therefore cannot be referenced, on account of the obvious ambiguity. The relational model requires every attribute to be referenceable.
;Column order significance
:The order of columns in an SQL table is defined and significant, one consequence being that SQL's implementations of Cartesian product and union are both noncommutative. The relational model requires there to be no significance to any ordering of the attributes of a relation.
;Views without CHECK OPTION
:Updates to a view defined without CHECK OPTION can be accepted but the resulting update to the database does not necessarily have the expressed effect on its target. For example, an invocation of INSERT can be accepted but the inserted rows might not all appear in the view, or an invocation of UPDATE can result in rows disappearing from the view. The relational model requires updates to a view to have the same effect as if the view were a base relvar.
;Columnless tables unrecognized
:SQL requires every table to have at least one column, but there are two relations of degree zero (of cardinality one and zero) and they are needed to represent extensions of predicates that contain no free variables.
;NULL
:This special mark can appear instead of a value wherever a value can appear in SQL, in particular in place of a column value in some row. The deviation from the relational model arises from the fact that the implementation of this ''ad hoc'' concept in SQL involves the use of three-valued logic, under which the comparison of NULL with itself does not yield ''true'' but instead yields the third truth value, ''unknown''; similarly the comparison NULL with something other than itself does not yield ''false'' but instead yields ''unknown''. It is because of this behaviour in comparisons that NULL is described as a mark rather than a value. The relational model depends on the law of excluded middle under which anything that is not true is false and anything that is not false is true; it also requires every tuple in a relation body to have a value for every attribute of that relation. This particular deviation is disputed by some if only because E.F. Codd himself eventually advocated the use of special marks and a 4-valued logic, but this was based on his observation that there are two distinct reasons why one might want to use a special mark in place of a value, which led opponents of the use of such logics to discover more distinct reasons and at least as many as 19 have been noted, which would require a 21-valued logic. SQL itself uses NULL for several purposes other than to represent "value unknown". For example, the sum of the empty set is NULL, meaning zero, the average of the empty set is NULL, meaning undefined, and NULL appearing in the result of a LEFT JOIN can mean "no value because there is no matching row in the right-hand operand".
;Concepts
:SQL uses concepts "table", "column", "row" instead of "relvar", "attribute", "tuple". These are not merely differences in terminology. For example, a "table" may contain duplicate rows, whereas the same tuple cannot appear more than once in a relation.
Implementation
There have been several attempts to produce a true implementation of the relational database model as originally defined by Codd and explained by Date, Darwen and others, but none have been popular successes so far. Rel is one of the more recent attempts to do this.
Controversies
Codd himself, some years after publication of his 1970 model, proposed a three-valued logic (True, False, Missing or NULL) version of it in order 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. But these have never been implemented, presumably because of attending complexity. SQL's NULL construct was intended to be part of a three-valued logic system, but fell short of that due to logical errors in the standard and in its implementations. See the section "SQL standard", above.
Design
Database normalization is usually performed when designing a relational database, to improve the logical consistency of the database design and the transactional performance.
There are two commonly used systems of diagramming to aid in the visual representation of the relational model: the entity-relationship diagram (ERD), and the related IDEF diagram used in the IDEF1X method created by the U.S. Air Force based on ERDs.
The tree structure of data may enforce hierarchical model organization, with parent-child relationship table.
Example database
An idealized, very simple example of a description of some relvars and their attributes:
★ Customer('Customer ID', Tax ID, Name, Address, City, State, Zip, Phone)
★ Order('Order No', Customer ID, Invoice No, Date Placed, Date Promised, Terms, Status)
★ Order Line('Order No', 'Order Line No', Product Code, Qty)
★ Invoice('Invoice No', Customer ID, Order No, Date, Status)
★ Invoice Line('Invoice No', 'Line No', Product Code, Qty Shipped)
★ Product('Product Code', Product Description)
In this design we have six relvars: Customer, Order, Order Line, Invoice, Invoice Line and Product. The bold, underlined attributes are ''candidate keys''. The non-bold, underlined attributes are ''foreign keys''.
Usually one candidate key is arbitrarily chosen to be called the primary key and used in preference over the other candidate keys, which are then called alternate keys.
A ''candidate key'' is a unique identifier enforcing that no tuple will be duplicated; this would make the relation into something else, namely a bag, by violating the basic definition of a set. Both foreign keys and superkeys (which 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.
Example: customer relation
Customer ID Tax ID Name Address [More fields....]
1234567890 555-5512222 Munmun 323 Broadway ...
2223344556 555-5523232 Vijeta 1200 Main Street ...
3334445563 555-5533322 Ekta 871 1st Street ...
4232342432 555-5325523 E. F. Codd 123 It Way ...
If we attempted to ''insert'' a new customer with the ID ''1234567890'', this would violate the design of the relvar since 'Customer ID' is a ''primary key'' and we already have a customer ''1234567890''. The DBMS must reject a transaction such as this that would render the database inconsistent by a violation of an integrity constraint.
''Foreign keys'' are integrity constraints enforcing that the value of the attribute set is drawn from a ''candidate key'' in another relation, for example in the Order relation the attribute 'Customer ID' is a foreign key. A ''join'' is the operation that draws on information 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 ''1234567890'', we could query the database to return every row in the Order table with 'Customer ID' ''1234567890'' and join the Order table to the Order Line table based on 'Order No'.
There is a flaw in our database design above. The Invoice relvar contains an Order No attribute. So, each tuple in the Invoice relvar will have one Order No, 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 No 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 'many-to-many' 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 role is to specify the correspondence between Orders and Invoices:
OrderInvoice('Order No','Invoice No')
Now, the Order relvar has a ''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 'Order No' in the Order relation equals the 'Order No' in OrderInvoice, and where 'Invoice No' in OrderInvoice equals the 'Invoice No' in Invoice.
Set-theoretic formulation
Basic notions in the relational model are ''relation names'' and ''attribute names''. We will represent these as strings such as "Person" and "name" and we will usually use the variables and 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:
; Tuple
: A tuple is a partial function from attribute names to atomic values.
; Header
: A header is a finite set of attribute names.
; Projection
: The projection of a tuple on a finite set of attributes is .
The next definition defines ''relation'' which formalizes the contents of a table as it is defined in the relational model.
; Relation
: A relation is a tuple with , the header, and , the body, a set of tuples that all have the domain .
Such a relation closely corresponds to what is usually called the extension of a predicate in first-order logic except that here we identify the places in the predicate with attribute names. Usually in the relational model a database schema is said to consist of a set of relation names, the headers that are associated with these names and the constraints that should hold for every instance of the database schema.
; Relation universe
: A relation universe over a header is a non-empty set of relations with header .
; Relation schema
: A relation schema consists of a header and a predicate that is defined for all relations with header . A relation satisfies a relation schema if it has header and satisfies .
Key constraints and functional dependencies
One of the simplest and most important types of relation constraints 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.
; Superkey
: A superkey is written as a finite set of attribute names.
: A superkey holds in a relation if:
:
★ and
:
★ there exist no two distinct tuples such that .
: A superkey holds in a relation universe if it holds in all relations in .
: 'Theorem:' A superkey holds in a relation universe over if and only if and holds in .
; Candidate key
: A superkey holds as a candidate key for a relation universe if it holds as a superkey for and there is no proper subset of that also holds as a superkey for .
; Functional dependency
: A functional dependency (FD for short) is written as for finite sets of attribute names.
: A functional dependency holds in a relation if:
:
★ and
:
★ tuples ,
: A functional dependency holds in a relation universe if it holds in all relations in .
; Trivial functional dependency
: A functional dependency is trivial under a header if it holds in all relation universes over .
: 'Theorem:' An FD is trivial under a header if and only if .
; Closure
: Armstrong's axioms: The closure of a set of FDs under a header , written as , is the smallest superset of such that:
:
★ (reflexivity)
:
★ (transitivity) and
:
★ (augmentation)
: 'Theorem:' Armstrong's axioms are sound and complete; given a header and a set of FDs that only contain subsets of , if and only if holds in all relation universes over in which all FDs in hold.
; Completion
: The completion of a finite set of attributes under a finite set of FDs , written as , is the smallest superset of such that:
:
★
: 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 of FDs, if and only if .
; Irreducible cover
: An irreducible cover of a set of FDs is a set of FDs such that:
:
★
:
★ there exists no such that
:
★ is a singleton set and
:
★ .
Algorithm to derive candidate keys from functional dependencies
'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
'begin'
''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'
'end'
See also
References
1. White, Colin. ''In the Beginning: An RDBMS History''. Teradata Magazine Online. September 2004 edition. URL: [http://www.teradata.com/t/page/127057]
2. A Relational Model of Data for Large Shared Data Banks, , E.F., Codd, Communications of the ACM, 1970
★ Codd, E. F. (1970). "A relational model of data for large shared data banks". ''Communications of the ACM'', 13(6):377–387. (Retrieved from ACM, September 4, 2004.)
★ Date, C. J., Darwen, H. (2000). ''Foundation for Future Database Systems: The Third Manifesto'', 2nd edition, Addison-Wesley Professional. ISBN 0-201-70928-7.
★ Date, C. J. (2003). ''Introduction to Database Systems''. 8th edition, Addison-Wesley. ISBN 0-321-19784-4.
External links
★ The Third Manifesto (TTM)
★ DMoz category
★ Relational Model
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
