4 Relational Model
Dr R. Baskaran
One of the most important applications for computers is storing and managing information. The manner in which information is organized can have a profound effect on how easy it is to access and manage. Perhaps the simplest but most versatile way to organize information is to store it in tables.
The relational model is centered on this idea: the organization of data into collections of two-dimensional tables called “relations.” We can also think of the relational model as a generalization of the set data model extending binary relations to relations of arbitrary structure. Originally, the relational data model was developed for databases — that is, information stored over a long period of time in a computer system — and for database management systems, the software that allows people to store, access, and modify this information. Databases still provide us with important motivation for understanding the relational data model. They are found today not only in their original, large-scale applications such as airline reservation systems or banking systems, but in desktop computers handling individual activities such as maintaining expense records, homework grades, and many other uses.
Other kinds of software besides database systems can make good use of tables of information as well, and the relational data model helps us design these tables and develop the data structures that we need to access them efficiently. For example, such tables are used by compilers to store information about the variables used in the program, keeping track of their data type and of the functions for which they are defined.
A collection of relations is called a database. The first thing we need to do when designing a database for some application is to decide on how the information to be stored should be arranged into tables. Design of a database, like all design problems, is a matter of business needs and judgment. In an example to follow, we shall expand our application of a registrar’s database involving courses, and thereby expose some of the principles of good database design. Some of the most powerful operations on a database involve the use of several relations to represent coordinated types of data. By setting up appropriate data structures, we can jump from one relation to another efficiently, and thus obtain information from the database that we could not uncover from a single relation. The data structures and algorithms involved in “navigating” among relations .
The set of schemes for the various relations in a database is called the scheme of the database. Notice the difference between the scheme for the database, which tells us something about how information is organized in the database, and the set of tuples in each relation, which is the actual information stored in the database.
1.{StudentId, Name, Address, Phone}. The student whose ID appears in the first component of a tuple has name, address, and phone number equal to the values appearing in the second, third, and fourth components, respectively.
2. {Course, Prerequisite}. The course named in the second component of a tuple is a prerequisite for the course named in the first component of that tuple.
3. {Course, Day, Hour}. The course named in the first component meets on the day specified by the second component, at the hour named in the third component.
4. {Course, Room}. The course named in the first component meets in the room indicated by the second component.
The same structures work when the relation is not binary. In place of a single attribute for the domain, we may have a combination of k attributes, which we call the domain attributes or just the “domain” when it is clear we are referring to a set of attributes. Then, domain values are k-tuples, with one component for each attribute of the domain. The range attributes are all those attributes other than the domain attributes. The range values may also have several components, one for each attribute of the range. In general, we have to pick which attributes we want for the domain. The easiest case occurs when there is one or a small number of attributes that serve as a key for the relation. Then it is common to choose the key attribute(s) as the domain and the rest as the range. In cases where there is no key (except the set of all attributes, which is not a useful key), we may pick any set of attributes as the domain. For example, we might consider typical operations that we expect to perform on the relation and pick for the domain an attribute we expect will be specified frequently. We shall see some concrete examples shortly.
Once we have selected a domain, we can select any of the four data structures just named to represent the relation, or indeed we could select another structure. However, it is common to choose a hash table based on domain values as the index, and we shall generally do so here. The chosen structure is said to be the primary index structure for the relation. The adjective “primary” refers to the fact that the location of tuples is determined by this structure. An index is a data structure that helps find tuples, given a value for one or more components of the desired tuples. In the next section, we shall discuss “secondary” indexes, which help answer queries but do not affect the location of the data.
The way in which we use a primary index structure to perform the operations insert, delete, and lookup should be obvious. To review the ideas, let us focus on a hash table as the primary index structure. If the operation specifies a value for the domain, then we hash this value to find a bucket.
1. To insert a tuple t, we examine the bucket to check that t is not already there, and we create a new cell on the bucket’s list for t if it is not.
2. To delete tuples that match a specification X, we find the domain value from X, hash to find the proper bucket, and run down the list for this bucket, deleting each tuple that matches the specification X.
3. To lookup tuples according to a specification X, we again find the domain value from X and hash that value to find the proper bucket. We run down the list for that bucket, producing as an answer each tuple on the list that matches the specification X.
If the operation does not specify the domain value, we are not so fortunate. An insert operation always specifies the inserted tuple completely, but a delete or lookup might not. In those cases,we must search all the bucket lists for matching tuples and delete or list them, respectively.
When there are one or more secondary indexes for a relation, the insertion and deletion of tuples becomes more difficult. In addition to updating the primary index structure as outlined in Section 8.4, we may need to update each of the secondary index structures as well. The following methods can be used to update a secondary index structure for A when a tuple involving attribute A is inserted or deleted.
1. Insertion. If we insert a new tuple with value v in the component for attribute A, we must create a pair (v, p), where p points to the new record in the primary structure. Then, we insert the pair (v, p) into the secondary index.
2. Deletion. When we delete a tuple that has value v in the component for A, we must first remember a pointer — call it p — to the tuple we have just deleted. Then, we go into the secondary index structure and examine all the pairs with first component v, until we find the one with second component p. That pair is then deleted from the secondary index structure.
The relational model (RM) for database management is an approach to managing data using a structure and language consistent with first-order predicate logic, first described in 1969 by Edgar F. Codd. In the relational model of a database, all data is represented in terms of tuples, grouped into relations. A database organized in terms of the relational model is a relational database.In the relational model, related records are linked together with a “key”.
The purpose of the relational model is to provide a 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 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 in an 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 deviate from the relational model in many details, and Codd fiercely argued against deviations that compromise the original principles.
The fundamental assumption of the relational model is that all data is 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). Data are operated upon by means of a relational calculus or relational 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 ordered 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 unique, non-duplicated 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. 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[citation needed]. 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 a row.
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.
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 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”.
Each row in a table has its own unique key. Rows in a table can be linked to rows in other tables by adding a column for the unique key of the linked row (such columns are known as foreign keys). Codd showed that data relationships of arbitrary complexity can be represented using this simple set of concepts.
Part of this processing involves consistently being able to select or modify one and only one row in a table. Therefore, most physical implementations have a system-assigned, unique primary key for each table. When a new row is written to the table, the system generates and writes the new, unique value for the primary key (PK); this is the key that the system uses primarily for accessing the table. System performance is optimized for PKs. Other, more natural keys may also be identified and defined as alternate keys (AK). Often several columns may be needed to form an AK (this is one reason why a single integer column is usually made the PK). Both PKs and AKs have the ability to uniquely identify one row within a table. Additional technology may be applied that will significantly assure a unique ID across the world, a globally unique identifier; these are used when there are broader system requirements.
The primary keys within a database are used to define the relationships among the tables. When a PK migrates to another table, it becomes a foreign key in the other table. When each cell can contain only one value and the PK migrates into a regular entity table, this design pattern can represent either a one-to-one, or a one-to-many relationship. Most relational database designs resolve many-to-many relationships by creating an additional table that contains the PKs from both of the other entity tables—the relationship becomes an entity; the resolution table is then named appropriately and is often assigned its own PK while the two FKs are combined to form an AK. The migration of PKs to other tables is the second major reason why system-assigned integers are used normally as PKs; there usually is neither efficiency nor clarity in migrating a bunch of other types of columns.
