Category Archives: Theory

Jim Gray’s analogy on Database Logging

Jim Gray was a computer scientist and Turing Award recipient pioneered in database and transaction processing system. His major contributions are implemented in major relational database systems as logging, locking, and he proposed the ACID properties of a transactional database system (though the acronym is coined by Andreas Reuter and Theo Härder in 1983) to name a few.

Hansel & Gretel and breadcrumb

He presented a paper in Proceedings of Seventh International Conference on Very Large Databases, in 1981, titled ‘The Transaction Concept: Virtues and Limitations’. In this paper he explained the concept of database transactions and different methods to implement it. His analogy on transaction logging is very interesting to read and help to understand the concept clearly and easily. This is as follows.

The legendary Greeks, Ariadne and Theseus, invented logging. Ariadne gave Theseus a magic ball of string which he unraveled as he searched the Labyrinth for the Minotaur. Having slain the Minotaur, Theseus followed the string back to the entrance rather then remaining lost in the Labyrinth. This string was his log allowing him to undo the process of entering the Labyrinth. But the Minotaur was not a protected object so its death was not undone by Theseus’ exit.

Hansel and Gretel copied Theseus’ trick as they wandered into the woods in search of berries. They left behind a trail of crumbs that would allow them to retrace their steps by following the trail backwards, and would allow their parents to find them by following the trail forwards. This was the first undo and redo log. Unfortunately, a bird ate the crumbs and caused the first log failure.”

Leave a comment

July 23, 2014 · 12:59 PM

Learning the Relational Model – Implementation of Relational Model (Part IV)

In this fourth part of the series we will briefly discuss how the relational model has been implemented in relational databases.

We are now familiar with the conceptual relational model. The conceptual model deals with unordered sets. In practical aspect, specifically in computer, we cannot physically represent an unordered set. So a practical implementation is a bit different from the relational model.

  • A named relation (relvar) is implemented as Table. A table has a predefined internal structure. The structure has variance in implementation by the different RDBMS vendors
  • An attribute is formed by a name, data type (can be different for different vendors), and constraints (enforcing domain integrity) and is called a column. The lists of columns form the heading of the relation (table).
  • A tuple is implemented as a row. Each row in a table also has fixed format (still vendor specific) and has some order (“… row has some order” is actually a misnomer. A row is usually identified by a row pointer or RID. Though the pointers or RIDs have some order, due to the implementations of data manipulation statements and data concurrency models, we cannot expect an order for row when we fetch data from a table)

Data is stored in a table and in respective columns as a series of rows.

How do you manipulate the data? How do you save and retrieve information from tables? We have already a seen a language to retrieve information from the relational model; i.e. relational algebra! But for the practical purposes, a new special purpose language is required to query the relational model. So IBM has developed a query language called SEQUEL (Structured English Query Language) based upon the relational algebra for their System R database system that is considered to be the first implementation of Codd’s relational model. This name was later changed to SQL (Structured Query Language).

SQL is still based on relational model and relational algebra (but not fully). However some features are added to the language. For example, based on set theory, the elements in a set are unique. When applying some combinations of relational operators on relations, the resulting relation may contain duplicate tuples. Avoiding duplicates is not practical since this may degrade performance of database applications. So another mathematical concept called Multiset (bag) is introduced to solve this problem. A multiset is very much similar to set; the difference is elements in a multiset may not necessarily be unique. The SQL language is then extend to support multisets and introduced more operators to manage the multisets and other real world functionalities. Some of them are;

  • Rename operator – to rename and attribute (column) name
  • Extended projection operator – new attributes are creating from existing attributes of relations. This can be arithmetic operations or applying function on attributes.
  • Aggregate operator (grouping operator)  –produces new relation by summarizing attributes. Usually this grouping is followed by applying aggregate functions on attributes such as sum, average, count, minimum, and maximum to get new insight of data.
  • Duplicate elimination (δ) – Returns relation by elimination all but exactly one copy of each tuple. SQL is using DISTINCT and UNION language operators to eliminate duplicates
  • Outer join – The outer join is defined in such a way that every tuple from either of the original relations appears in some way in the joined relation. The outer join operator addresses the fact that some tuples in a relation are not represented in a natural join involving the relation.  This is because there is no matching tuple in the relation being joined. This is called ‘dangling tuple’
  • Data modification operators – These are used for inserting, updating and deleting data.

Based on these basic and extended operators, the SQL language is standardized by ANSI and ISO and still expanding to add new language features. Some features include, Common Table Expressions, read-only INFORMATION_SCHEMA tables for metadata (data dictionary) querying, temporal data retrieval etc. Each RDBMS vendor is actually may or may not implement all the ANSI/ISO version of SQL and add their own features to the SQL language implementation for user’s ease-of-use. So this is up to the individual to select a particular RDBMS based on the requirement and the features.

There is no commercial RDBMS product that we can call as truly or fully relational model complaint. There are some implementation challenges that hinder the RDBMS product become fully relational. Hope I can write another post on this subject in the future.

One more important point is relational algebra and SQL is declarative; i.e. you are asking what you want from the data stored instead of how you want to retrieve the data stored. This is a big paradigm change for a procedural language developer. Thinking in sets and relation is important when working with RDBMS and SQL, though procedural elements are included in RDBMS by many vendors in the form of cursors and loops.

Series Summary

  • RDBMS products are built on top of strong mathematical foundations on set and predicate theory
  • By applying basic and extended relational operators we can retrieve many complex information from data stored in a relational model
  • SQL is used to query and manipulate data from RDBMS is based on strong mathematical language called relational algebra and extended to support practical applications
  • SQL is based on multiset (bag) theory and hence SQL is a multiset theoretic language
  • A multiset result can be converted to a set by applying duplicate elimination operators like DISTINCT or UNION. However performance may affect

The below table lists the relational algebra operators and SQL syntax similar to that

 No. Relational Operator SQL syntax
1 SELECT  SELECT * FROM Employee WHERE Dept_ID = 18
2 PROJECT  SELECT JoinDate, F_Name FROM Employee WHERE Dept_ID = 18
3 RENAME SELECT F_Name AS FirstName FROM Employee
4 UNION SELECT F_Name FROM Contract_Emp UNION ALL SELECT F_Name FROM Permenant_Emp
8 JOIN SELECT E.Name, E.EmpID, E.DeptName, D.ManagerName FROM Employee E INNER JOIN Dept D ON D.DeptName = E.DeptName
9 DIVISON There is no SQL operator that translates to a DIVISION operator. However we can implement relational division using many SQL statements available. A full discussion of relational division is out of the scope of this article. Read Joe Celko’s excellent article on this subject here (
10 Extended Project SELECT F_Name + ‘ ‘ + L_Name AS EmpName, BasicPay * (12.0 / 100.0) AS TravelAllowance FROM Employee
11 Aggregate SELECT DeptName, AVG(Salary) AS AverageSalary FROM EmpSalary GROUP BY DeptName
12 Duplicate removal SELECT DISTINCT Dept_ID FROM Employee or SELECT EmpName FROM Permenant_Emp UNION SELECT EmpName FROM ManagementCouncil


If you learn the relational model and relational algebra and the operators, you can design good databases and make the queries simple and portable. When you execute a query, the RDBMS’ query optimizer is converting the SQL dialect to a relational algebra tree and retrieving the data from the underlying physical tables based on the algebra tree (though I’ve simply said it, the query optimization and creating efficient and simple algebra tree is a big topic and still researches are going on in this area). Hope you enjoyed the series.

Leave a comment

Filed under Basics, Theory

Learning the Relational Model – The Model (Part III)

In the previous two parts we have seen the concept of Set theory and predicate logic. In this third part we will discuss how these two theories combined to form the relational model.

The path to relational model

Here is a fictional conversation between two people met in the cafeteria of the office floor.

“Excuse me! I’m Fred. Do you work in Accounts?”

“No I’m in Purchase Dept.”

“I haven’t seen you before. I’m in Marketing”

“I’m Mark and I just joined last week on 16th as the manager”

“Oh! So how do you feel about the new job?”

… and the conversation continues…

There some data points hiding in the above conversation. There is a set of department like Accounts, Purchase, and Marketing etc. and there is a set of employee like Fred, Mark etc. Every employee is related to any one of the department from the set of departments. Each employee has a name and a data of join.

In natural language we make assertions about entities of interest by statements of fact—or, in logic, by propositions. For example, this is a proposition:

“The employee with ID number 215 is named Mark, works in Purchase department, and was hired on December 16th, 2013.”

Generalized forms of propositions are predicates. For example, this is a predicate :

P: The employee with ID number (Emp#) is named (Name), works in department (Dept#), and was joined on (Joindate).

The four terms in parentheses are placeholders or parameters that correspond to the four values in the preceding proposition. We can substitute values to the parameters. When you substitute parameters with specific values, a predicate reduces to an individual proposition. For the above predicate let me substitute the below parameter values respectively:

 (215; Mark; Purchase; December 16th, 2013)

You can immediately see that the above set of parameters form a tuple! (We have discussed about tuple in Part I). Let us call this set as Employee relation E. The relation E can be a set of tuple as below.

E =       {

            (215; Mark; Purchase; December 16th, 2013),

            (107; Fred; Marketing; April 08th, 2005),

            (183; Bob; Sales; October 10th, 2010),


Each tuple’s values when replaced with the parameters in the above predicate satisfy the proposition or we can say the proposition is true for the above relation E. In other words a relation E expressing the predicate P would be the set of all sets of values which satisfy the predicate truthfully (in our enterprise or universe).

So how do you define your data model? Just describe a business problem, find predicates, and write them down— the data to the predicate parameters forms a set – you have your data model. Now we can relate the set theory and predicate logic to describe data.

 However there are still missing pieces to make the relational model. Is the 215 for the parameter Emp#, a numeric value or a literal text value? Is the Joindate December 16th, 2013 represents a date or a text? So a formal definition of type of each parameter is required now.

 Type and Domain

 The type that usually called as a data type is a classification identifying the various types of data like integer, real valued, string, date, Boolean (representing true or false) etc., the operations that can be done on values of that type; the meaning of the data; and the way values of that type can be stored. For example an int data type in a relational database system represents an exact numeric data type and this type supports addition, subtraction, multiplication, and division on the values of that type.

 In addition to data type, there can be a possible list of value applicable to support by the data type or the business requirement. A data domain refers to all the unique values which a data element may contain. For example the Emp# parameter can have values ranging from 1 to 500 for a medium organization. So type of Emp# is int and domain ranges from 1 to 500.

Type is the basic building block of relational model. Domain is usually confused with the term data type. To make the distinction let us consider an example of Age. The age can be represented using the data type int. However the domain of age for a company can have values ranging from 18, the minimum age for employment and 60, the retirement age.

The parameters Emp#, Name, Joineddate etc. we can call it attribute names. Each attribute name has a data type and a domain. A set of an attribute name, corresponding data type, and associated domain is called an attribute. So an attribute A for storing gender information can be represented by the below set:

 A = { (Gender, CHAR, {‘M’, ‘F’}) }

 In other words an attribute is an ordered set of attribute name, type and domain.

Each attribute is associated with a value. The value can be a scalar value (single value) and can have a complex values. For example the value of attribute Gender will be ‘M’.

A set of attribute is called a heading. So the heading for Employee E can be represented as the below set:

 HE =     {

             (Emp#, int, {1,2,3,4…..498,499,500}),

             (Name, char, {alphabets and space}),

             (Dept, char, {Purchase, Marketing, Sales, IT, Admin}),

             (Joindate, date, {01/01/2002 to 12/31/2022})


Note that the header mathematically represents the predicate.

A set of n-Tuple is called a body: so the body B of employee can be represented by the below set:

B = {E1, E2, ….. En}

A relation consists of a heading and a body. The heading of the relation is also the heading of each of its tuples. A named relation is called a relational variable or relvar.

 Here is a pictorial representation of the relation named R, we have learned so far.


Strength of the relational model

 Several times I have mentioned that the relational model’s power lies in the mathematical foundations of set theory and predicate logic. From the granular level to higher levels this is visible.

 Attribute           = a set of attribute name, type and domain

Tuple                = a set of attributes and values

Body                = a set of tuples

Heading           = a set of attributes

Relation            = a set of heading and body

Based on predicate logic;

Relation            = AND (^) of tuples;

The employee with ID 215 is named Mark, works in department Purchase, was joined on December 16th, 2013 AND

The employee with ID 107 is named Fred, works in department Marketing, was joined on April 8th , 2005 AND

The employee with ID 283 is named Bob, works in department Sales, was joined on October 10th, 2010 AND


This can also be extended to any level, viz. a tuple is the logical AND of all the attributes and values, an attribute is a logical AND of attribute name, type and domain etc.

 If each tuple represents an axiom (a statement of truth or a fact about our universe) we can combine these axioms with mathematical operators, and using logical rules of inference and we can derive new facts that are mathematically provable.

Extracting information from relational model 

E.F Codd introduced two different languages to query the relational model. One is relational algebra, which is a procedural language and the second one is relational calculus, which is a declarative language. In relational algebra a collection of relational operators are applied to the relations, resulting in another relation. The following are the basic relational operators 

Set Operators 

  1. Union (U) – it takes two relations, say, Bike B and Car C, both of which must have the same set of attributes. The union, B U C, consists of all the tuples in B and all the tuples in C and result in a relation Vehicle V. 
  1. Cartesian Product (X) – Cartesian product of A X B, result in a relation in which all possible ordered pairs (a,b) where a is a member of A and b is a member of B. 
  1. Intersection (∩) – The intersection, A ∩ B, consists of those tuples that are both in A and B. 
  1. Difference (-) – The difference, A – B, consists of those tuples in A which are not in B.

 Relational Operators

   5. Selection (σ) – (also called restrict) operator is used to choose a subset of tuples.

          σDept = Sales (E), will return a relation from Employee E in which Dept is Sales. 

  1. Projection (π) – when applied to a relation, the projection operator do the following
  • Removes all attributes from the relation that do not appear in the attribute list
  • Reorder the attribute based on the order in attribute list
  • Eliminate any duplicate rows 

     πEmp#, Name(Employee), will return a relation from Employee E, in which only the Emp# and Name available in that order 

  1. Join (|><|) – Join is a binary operator that combines Cartesian product and Selection operator in a single operation. The result of A |><| B is combination of tuples a from A and b from B where certain conditions are satisfied. 
  1. Division (/) – Extract rows whose column values match those in the second table, but only returns columns that don’t exist in the second table. Suitable for queries that include “for all”. Example, let A represents all the assignments, C represented completed assignments of students, then C / A represents the students who completed “all” the assignments.

 By combining these basic operators we can retrieve information from relational model.


In the next part of this series we will how the above described concepts are actually implemented in relational database systems.


Leave a comment

Filed under Basics, Theory

Learning the Relational Model – Predicate Logic (Part II)

In the first part we have seen the concept of Set theory and relational theory. In this part we are going to learn about the concept of predicate logic.

Part II – Predicate Logic

What is logic?

Logic is a language for reasoning and is a collection of rules we use when doing reasoning. In logic we are interested in true or false of statements, and how the truth/falsehood of a statement can be determined from other statements. There are various types of logic such as logic of sentences (propositional logic), logic of objects (predicate logic), logic involving uncertainties, logic dealing with fuzziness, temporal logic etc.

Propositional logic is logic at the sentential level. The smallest unit we deal with in propositional logic is a sentence. Sentences considered in this logic are not arbitrary sentences but are the ones that are true or false. This kind of sentences is called proposition. For example, “Grass is green”, and “2 + 5 = 5” are propositions. The first proposition has the truth value of “true” and the second “false”. But “Close the door”, and “Is it hot outside?” are not propositions. Also “x is greater than 2”, where x is a variable representing a number, is not a proposition, because unless a specific value is given to x we cannot say whether it is true or false, nor do we know what x represents.

Let P be the proposition “It is snowing”, Q be the proposition “I will go the beach”, and R be the proposition “I have time”, then the English sentence, “I will go to the beach if it is not snowing” is restated as “If it is not snowing, I will go to the beach”. This can be represented as symbols as below:

¬P -> Q

The symbols are called connectives and below is the list of connectives and there meaning.

¬ – NOT

^ – AND

v – OR

-> – IF THEN (or IMPLY)


Similarly, “It is not snowing and I have time only if I will go to the beach” is restated as “If it is not snowing and I have time, then I will go to the beach”, and it is translated as (¬P ^ R)  -> Q.

Predicate Logic


The propositional logic is not powerful enough to represent all types of assertions that are used in computer science and mathematics, or to express certain types of relationship between propositions such as equivalence. For example, the assertion “x is greater than 1”, where x is a variable, is not a proposition because you cannot tell whether it is true or false unless you know the value of x. Thus the propositional logic cannot deal with such sentences. However, such assertions appear quite often in mathematics and we want to do inference on those assertions.

A predicate is a verb phrase template that describes a property of objects, or a relationship among objects represented by the variables.

Consider the following sentences:

  1. “John gives the book to Mary”
  2. “Jim gives a loaf of bread to Tom”
  3. “Jane gives a lecture to Mary”

We can derive a template here. The template is “……gives……to…..”. This template is called a predicate and it describes a relationship among three objects. The predicate can be written as G(x, y, z). The x, y, and z are the variables. So G(John, Book, Mary) represents “John gives the book to Mary and G(Jane, lecture, Mary) represents “Jane gives a lecture to Mary”.

I’m omitted some other aspects of predicate logic like, quantifiers, well-formed formula (wff) etc. since these are not relevant in our discussions on relational model at present.


So we have covered two fundamental theories of relational model viz. set theory and predicate logic. In the next section we will merge these concepts to build the relational model

Leave a comment

Filed under Basics, Theory

Learning the Relational Model – Basic Set Theory (Part I)

This blog series on Relational Model is my attempt to understand the foundation of relational model of database. My intention is to learn and understand how Edgar F Codd designed the relational model, the basis of the model and how this is implemented in the relational database.


Edgar F Codd built the foundation of relational model of database above two fundamental mathematical concepts viz. Set theory and predicate logic. The basic set theory is explained in this part of the series.

Sets and Relations

A set is a collection of distinct objects. For example a fruit basket is a collection of fruits and can be represented as B = {Apple, Orange, Grape}. Set of employees in a particular firm E = {Alice, Bob, Charlie}. There can be empty sets as well. For example an empty fruit basket, B = {}.

We know that the algebra of numbers include many operators like addition (+), subtraction (-), multiplication (X), division (/) etc. Likewise algebra of sets includes its own collection of useful operators. Like the operators of arithmetic, some of the set operators combine two sets and yield a set. These are the set operators.

  1. Union

Let A and B be sets with the same universe U. The union of A and B, denoted AB, is the set containing those elements of U that are either elements of A or elements of B (or elements of both). The union of {1, 2, 3} and {2, 3, 4} is the set {1, 2, 3, 4}

  1. Intersection

Let A and B be sets with the same universe U. The intersection of A and B, denoted A∩B, is the set containing those elements of U that are both elements of A and elements of B. The intersection of {1, 2, 3} and {2, 3, 4} is the set {2, 3}

  1. Set Difference

Let A and B be sets with the same universe U. The set difference of A and B, denoted A\B, is the set containing those elements of U that both elements of A and non-elements of B. The set difference {1,2,3} \ {2,3,4} is {1}

  1. Cartesian Product

Let A and B be sets with the same universe U. The Cartesian product of A and B, denoted by A X B, is the set whose members are all possible ordered pairs (a,b) where a is a member of A and b is a member of B. The Cartesian product of {1, 2} and {red, white} is {(1, red), (1, white), (2, red), (2, white)}.

  1. Power Set

Power set of a set A is the set whose members are all possible subsets of A. For example, the power set of {1, 2} is { {}, {1}, {2}, {1,2} }

 How can we apply this to data? What it says is everything can be collected to a set. That is a set of employees, a set of customers, a set of orders, a set of addresses, a set of products etc. If we can define an entity as a set of data, then we can also apply the set operators! For example, we can derive a set of vehicle by applying the union operator on a set of cars and set of bikes. We can find a set of both English speaking and Hindi speaking people by applying the intersect operator on the set of English speaking people and the set of Hindi speaking people. Since set operations are also associative and commutative we can combine the sets in many combinations and get different result sets (I am not going in detail to the associative and commutative properties of sets, since we have already studied this for numbers in high school classes).


Based on the definition, set do not allow duplicates. However the idea of multiset has been introduced to allow more than one similar object (or duplicate object). Multiset is also called bag. Multiset and operations on multisets are very much similar to set. I will explain the practical importance of multiset later in this series.

From Set to Relation

A relation in mathematics is an association between various objects. Relation can also be represented by a set. A relation is a set of ordered pair and the pair has certain association. For example, let us consider a set of employee, E = {Alice, Bob, Charlie}, and a set of department D = {Sales, Purchase, Marketing}. So a relationship “is of department”, R can be represented as R = {(Bob, Marketing), (Alice, Sales), (Charlie, Sales)} and this can be read in English as ‘Bob is of department Marketing’, ‘Charlie is of department Sales’ etc. There are two elements in the result set, employee name and department name, a set of double. This can be triple, quadruple, quintuple, sextuple, septuple, etc. to n-tuple. This is generalized to a term called tuple. So in the above relation (Bob, Marketing) is a tuple and (Alice, Sales) is another tuple and so (Charlie, Sales).


In the next part of the series we will see the predicate logic, the next fundamental concept of relational model.


Leave a comment

Filed under Basics, Theory