Tag Archives: set theroy

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
5 INTERSECT SELECT F_Name FROM Employee WHERE Skill = ‘C#’ INTERSECT SELECT F_Name FROM Employee WHERE Skill = ‘SQL’
6 DIFFERENCE/MINUS SELECT F_Name FROM Employee WHERE Skill = ‘C#’ EXCEPT SELECT F_Name FROM Employee WHERE Skill = ‘SQL’
7 PRODUCT SELECT Y.YearID, S.SeasonFROM Season S CROSS JOIN Year Y
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 (https://www.simple-talk.com/sql/t-sql-programming/divided-we-stand-the-sql-of-relational-division/)
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

Conclusion

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.

Image 

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.

Next

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