Saturday 31 March 2012

What are Tablespaces?

"Tablespace" is part of storage architecture of some of the commercial database systems like Oracle or DB2. Some of the database systems (like Microsoft SQL Server) are not known to use the concept of tablespace (I invite MS SQL Server or other database system users to elaborate on this in comments or provide links to a detail information if they know). Here we are considering Oracle as the model for learning the concept of tablespaces, which provides a layer of abstraction between physical and logical data. Rather, the cause of discussion about the tablespaces is that we are going to study the storage architecture of Oracle database system.

Oracle Storage Architecture -

We all know, there are two agencies at work when we come to storing and accessing the data in the databases - The OS (Operating System) and DBMS (Oracle). The calls are made for the data handling / manipulation from the DBMS in the form of (SQL) statements which requires a "view level" abstraction for referring to the data, whereas when it actually comes to read/write operation, it is the OS which plays that role, has to deal with "physical level" of the data storage. And thus the overall study of storage architecture would involve "Logical" and "Physical" perspective, the former from DBMS point of view and later from OS's side. Incidentally, we formally define the terms - "Physical" as something, the existence of which can be proved in terms of it occupying some space (area or volume) and "Logical" which exists in terms of an assumption or idea that does not have a shape.

As such the OS identifies files as the containers to hold or store the data. The files (datafiles) have an area and occupy a certain space on the storage device (hard drive), hence physical. "Tablespace" however is the logical storage as perceived by the DBMS and is well defined as "group of datafiles".

The concept of "group" itself is logical which exists in terms of its members (physical). For example your friend circle - each member is physical and the notion of belonging to the "circle" is there in the mind of each friend and has no physical existence. I have been insisting on this analogy for this would help you understand and digest the forthcoming discussion.

Why use Tablespaces? -

Having defined the tablespaces and accepting it as "group of datafiles", there are two main reasons, among others for using the tablespaces - Optimize the performance and provide virtually unlimited size of the segment (say Table) to grow.

Tablespace allows its data files to be located on different physical hard drives (do all you friends always move together?) and this arrangement comes as a great relief in reducing read/write contention in different parts of the segment in a multi-user environment, as the segment can spread within the imaginary boundary of the tablespace which contains (read groups) those data files. Simply put, a segment can not remain confined to a data file but to a tablespace. So the "chunks of spaces" (say extents) allocated to a segment scatter over all the data files belonging to a tablespace. For example consider a tablespace named "tbs1" has datafiles named "df1", "df2" and "df3" and they may be residing on hard drives "hd1", "hd2" and "hd3", then for some table "T" the extents will scatter over those datafiles (and hence on multiple drives) and as such will reduce the R/W contention. So for creating a tablespace of a size of say 500MB (just example), instead of creating a single file of that size to become part of this tablespace, have 5 files of 100MB each located on different drives. It has been observed some times that a lot of query optimization efforts go in vain if this basic tip about the tablespace layout is not followed.

Secondly, you may have virtually unlimited size of a segment (table) as it may no more remain confined to the maximum allowable size of the file. A segment can spread over all the files of a tablespace which may potentially have 1023 datafiles. Moreover partitioning of tables or indexes also allow them to be stored over multiple tablespaces with each partition being treated as a segment and hence can reside in different tablespace.


The other few advantages of tablespace are -
  • Database systems provide the facility of performing the backup / recovery at the tablespace level.
  • A tablespace may be taken offline for addressing any maintenance issues or reorganization of data files, so no need to stop entire database.
  • Tablespaces with "read only" status help reduce the backup time, size, resources and efforts as such tablespaces need not be backed up in every backup cycle (as they do not allow any change in the data in the segments stored in them).
  • Tablespaces allow tables / indexes with different access patterns to group them.

Tablespace Types -

Oracle has classified the tablespaces in different ways -
  • System & Non-System - This fundamental classification identifies the "system" tablespace as the first, mandatory and single tablespace with the same name as its type created in the database (created at the time of creation of the database, rather creating database summarily is creating a system tablespace at its minimum), which houses the data dictionary or database repository or catalog. Theoretically it is possible to have this only one tablespace in the database to also hold user's tables, but that is something discouraged in practice and hence a set of tablespaces created for holding users' data are called "non-system" tablespaces. There may be several of them in the database.
  • Permanent, Temporary and Undo- A "Permanent" tablespace is that contains "permanent" type of segments i.e. those which are created using an explicit "create ..." statement and dropped using an explicit "drop ..." statement. Such segments are for example Tables, Indexes, Clusters and Partitions which are created / dropped with an explicit command. The "Temporary" tablespaces are used to hold the "temporary" segments, which are used as scratchpad during a sorting event and only created implicitly whenever required as a SQL statement needs to sort (Query statements with distinct, group by or order by clauses). The "Undo" tablespace category was introduced in Oracle 9i to support automatic undo management feature i.e rollback segments and its contents and creation are managed implicitly by the system and also it supports Flashback Query (FBQ); a feature which allows to "view" the data as it was at particular time in past within the scope of "retention time". Prior to version 9i Oracle DBA's would store the rollback segments in some "permanent" type of tablespaces by creating them explicitly. The "temporary" tablespaces are said to contain "tempfiles" rather than data files, which have same format & structure as data files but only do not generate "redo" (history of changes to the data, required for future recovery of database) as the same is not required to be stored for a trivial event like sorting of the data that does not amount to any change to the database as such.
  • Dictionary Managed and Locally Managed - The later type was only introduced in 8i (version 8.1.5) as option and now in later versions used mostly as default type of tablespaces created in Oracle database. "Dictionary Managed" tablespaces had to "consult" the data dictionary for the account of allocation / de-allocation of the extents. This would involve some "recursive sql" to be fired (at data dictionary) to fetch and/or update the catalog and also would, in a volatile database, tend to serialize the operation causing overheads and delays in operations which particularly required extension of space (for segments). Another fact with the "Dictionary Managed" tablespaces was a marginal under-utilization of space due to "bubble free space" getting trapped in non-uniform sized extents of different segments. The problems are removed in "Locally Managed" tablespace by having a bitmap stored in headers of the datafiles to indicate vacancy or occupancy of the extents and also by uniformly sizing the extents or auto allocation feature(system will decide the size of extent) has eliminated the possibility of under utilization. However some DBAs have reservations about this new type as they opine that space management and growth of segments is their job as administrator and to that scope locally managed tablespaces are an encroachment on their role of space administration.

Data Files -

The discussion could be incomplete without considering the "Data Files" which are the "Physical" entities which make the tablespaces and it is here where the data is actually stored and read from. There is no free existence of the data file and it has to belong to some tablespace as Oracle refers to storage from its own stand point of view as we have discussed so far. Data files in Oracle are formatted according to Oracle's own block size as specified in db_block_size parameter. The standard allowable sizes are 2K, 4K, 8K, 16K, 32K. Normally only one of these block sizes should be used but as from Oracle version 9i onwards, Oracle allows multiple block sizes and hence there may be tablespaces with different block sizes created in latest of the databases mounted on these versions. These block sizes must be in multiples of OS block sizes as the data is ultimately read/written by the OS and for an abnormal size of Oracle block (not in multiple of OS block) there may be wastage of space and increased I/O for same amount of data.

How to determine the data block size -

The choice of the correct block size is a very critical decision. And there are certain guidelines to be followed to arrive at the most appropriate size. 

In general Oracle recommends 2K & 4K sizes for an OLTP type of database, because the applications which run from them usually has fair mix of all types of data access statements and deal with small amount of data for each operation. The larger range 16K & 32K are recommended for DSS systems (Decision Support Systems aka data warehouses) as the access pattern is mostly in the form of "select" statements with aggregate functions which require bulk of data to be read in the memory. And of course for mixed workload environment 8K is normally preferred.


The block size should also be large enough to accommodate entire size of the rows and the rows need not to be fragmented. The phenomenon is called "row chaining" and has to be avoided to reduce the I/O or otherwise the fragments have to be read from different blocks.

Small range of blocks are also considered to be suitable for random access for small average row sizes, whereas for sequential access pattern for the same small sized rows, larger range of block sizes may be recommended.

You have to also consider the volatility of the databases and density of operations, since small block size with high density of operations may cause contention and hence may not be suitable for highly volatile data tables.

Larger block sizes are obviously more suitable for LOB type columns. 


Conclusion -
The knowledge of the storage structure of the database is extremely crucial not only from the point of view of space management but also from performance optimization.

Thursday 29 March 2012

Transaction Locks

In a previous post we discussed about why we need our databases to allow for concurrent transactions and the related problems and different transaction isolation levels, their outcome with respect to data integrity/consistency, as part of basics of "Transaction Concurrency". This post is supposed to take it further by considering how databases use data locks for providing such concurrency, and the implications of such locks, if any, for writing multi-user applications, multi-version read consistency and granularity to which locks may be implemented. Again wherever required, this discussion will refer to implementation in Oracle DBMS as an example.

Concurrency Control -

There are different methods database systems may use in combination to implement the concurrency; they include locking mechanisms to guarantee exclusive use of a table by a transaction, time-stamping methods that enable serialization of transactions, and the validation-based scheduling of transactions.

Locking methods prevent unserializable schedules by keeping away more than one transaction from accessing the same data elements. Time-stamping methods assign timestamps to each transaction and enforce serializability by ensuring that the transaction timestamps match the schedule for transactions. Validation methods maintain a record of transaction activity and the changed data is "validated" against the changed items of all currently active transactions to eliminate any unserialized schedules, before committing a transaction. Most of popular commercial databases like Oracle use a combination of available methods.

What are Locks ? -

Simply put, a "lock" is a mechanism used to regulate concurrent access to a "shared resource". The term "shared resource" has a very wide meaning - it not only includes the table rows but everything that should be required to be accessed concurrently at any level. There are two methods of locking - Pessimistic Locking and Optimistic Locking - depending upon how the applications would like to go about changing the data.

Pessimistic Locking -

"Pessimistic Locking" method allows for declaring an intention to "update" a row(s) from a set of preselected rows fetched without locking. The sequence of operations is thus -
  1. Application simply queries a set of rows from a table (a plain select statement).
  2. Then user picks a row(s) which he/she wants to update and then declares intent for update by some means (may be hitting some relevant button in the form interface).
  3. The system re-queries the picked row(s) from the database with a difference this time that locks are requested on the row(s) for protection against update by other sessions.
  4. An update statement actually updates the row(s).
There are three possible outcomes of this sequence of operations in "Pessimistic Locking" -
  1. The re-query (step 3) as above is successful and now our user locks the rows (to prevent others from updating).
  2. The re-query is blocked for other session has already started with a transaction on the same row(s) and system makes us wait for other session to finish.
  3. If the row(s) have been changed (and committed) by other session meanwhile which our user re-queried, then no rows will show up (the data queried in step 1 is stale) and our user has to start over again from step 1 as listed above.
Thus using "Pessimistic Locking" our user could safely change the row(s), without any possibility of overwriting some other user's changes as it has been already verified in the session of our user that the data did not change meanwhile before requesting for the lock (in step 3 of sequence of operations).

Optimistic Locking -

"Optimistic Locking" method is based on the belief that data in the rows is not changing / changed by other session while our user is trying to update. The chances are that our user may or may not have luck to update the row(s) - in later of the cases our user will have to re-key the transaction.

Pessimistic v/s Optimistic -

The question is difficult to answer and will be answered by DBMS vendor as each have different approach. However wherever possible, to use "Pessimistic" locking mode would work better. It provides the users with the confidence that the data they are modifying are on their screen and hence currently "owned" by them. However the chances in this case may be a user may not further update and finish the transaction immediately after the locks have been obtained, which has to be taken care by killing such idle (non-performing) session after a reasonable time. Oracle favors the applications to use this approach as the locking of a row does not prevent any normal activity like reading of the same rows etc. The other databases are known to have NO favor with Pessimistic, but this needs to be authenticated by long term users of other databases in the comments to this post or posting a link to a similar blog post explaining the same.

Lock Escalation -

Concept of "Lock Escalation" relates to "granularity". Granularity is the level at which the data is locked in the database / tables. For example Oracle implements "row level" locking, which means that locks are placed on rows, NOT on page (block) or table. So in this case granularity is "row". "Lock Escalation" is the name given to decrease in the granularity. In some databases locks are considered to be scarce resource and hence considered as overhead to be avoided if they happen to be many in number. For example if for users operation say 100 rows are locked then the system may prefer to lock the entire table instead of each of 100 rows. So this is the case of "lock escalation".

Oracle DOES NOT use lock escalation. However it does use "lock conversion" or "lock promotion", the terms which are considered synonyms. This allows Oracle to make a "less restrictive" lock to "more restrictive". A case of "lock conversion" has been described below as an example -


  • You select a row(s) from a table with "FOR UPDATE" clause.
  • One "exclusive lock" is placed on the row while "row share table" lock is placed on the table to allow to perform any operation on the table except changing its structure (which will lock the entire table itself).
  • When the actual command to update the locked row(s) is issued Oracle will convert "row share table" lock to more restrictive "row exclusive table" lock.
Actually "lock escalation" is not considered as a good feature in database systems because it implies there is some inherent overhead in its locking mechanism.

In this post we have discussed about general theory behind the "locking" mechanism. Visit again for explanation on some more database related concepts. Coming back shortly.

Tuesday 27 March 2012

Transaction Concurrency

Introduction -

Consistent read / write operation while maximising the concurrent access is the key challenge in developing multi-user database-driven applications. The database management systems implement different schemes of "locking" and "concurrency" control to achieve this feat. It is very important to understand that there are as many ways to implement locking as there are different database management systems (from different vendors). While the entire scope of this subject being extremely vast and the mathematical models of those schemes are beyond the scope of not just one or two posts like this but may require an entire book to define, we shall have to remember that here we are not creating a database management system but only understanding an ideal implementation. Again what is ideal is really a big debatable question; we shall consider the implementation with reference to most widely used commercial database management system, Oracle where ever required.

Transaction -

A "transaction" is a logical unit of work consisting of one or more SQL statements and more importantly concerned with the changes to the data or database. It is traditionally defined in terms of its 4 properties described as an acronym - ACID
  • Atomicity - smallest unit of changes, which either has to happen completely or not happen at all and which does not have a subset with respect to following (next) property.
  • Consistency - it takes the data from one consistent state to next consistent state. The consistent state of the data is definable and justified in terms of validity of the data with respect to certain obvious, natural or mundane rules.
  • Isolation - it ensures that the effect of one transaction are not visible or potentially impact the other concurrent transaction, as if the each transaction is alone being carried out the entire database.
  • Durability - assures that the transactions once committed are saved permanently in the database and are not subject to loss under any condition (including cycles of failure and recovery).

What is concurrency control ? -

"Concurrency Control" are the collection of functions that the database provides in order to allow many people to access and modify data simultaneously. Concurrency obviously increase the throughput of a database management system, but it brings along its own set of problems as following -
  • Dirty Read - A "dirty read" is said to have occurred in a transaction when it reads an "updated" data from another transaction before it is committed. The reason this should not be allowed is because the data that has just been updated is in the intermediate phase of change and has the potential to be rolled back by the transaction who made the change; so in case of a reversal another transaction had already read the changed data which is really now incorrect.
  • Phantom Read - "Phantom read" causes new rows to appear in the result when the same query is run second time after a gap when it was run the first time. It differs from "non-repeatable read" (explained below) in the sense that this is not about the change in the data but rather more data satisfies the same criteria of selection of data as compared to first query.
  • Non-Repeatable Read - "Non-Repeatable Read" causes the same rows that were read in previous operation appear changed when queried after a time gap. It is possible even that the rows might disappear in the second read operation rather than just appear to have changed.
  • Lost Update - "Lost Update" problem causes a transaction to overwrite a pending transaction started earlier by another transaction and hence make it disappear (say Lost).

What are Transaction Isolation Levels ? -

The ANSI/ISO transaction standards use the term "Isolation Level" to indicate the extent to which the databases either permit or not permit top 3 of the 4 of concurrency phenomena  (say outcome of a concurrent pair of transactions) as described above. The "Lost Update" is invariably NOT permitted in any of the standard isolation levels.
  • Read Uncommitted transaction isolation level is the most non-restrictive of all the transaction isolation levels. It permits all the three reads - Dirty Read, Phantom Read and Non-Repeatable Read. In any case the "Dirty Read" should not be allowed to happen. So this isolation level is not used in any of the known commercial database systems. However it is interesting to know that "Read Uncommitted" isolation is to provide a standards-based definition that caters for non-blocking reads. However, commercial databases like Oracle do not need "dirty read" since it has been designed to take a detour around the lock (the changed data is locked until the transaction is complete) and it can reconstruct it from a place called "Rollback Segments" (where original version of data is stored for facilitating rollback) and so Oracle can make consistent data available to the user without waiting for the transaction to commit.
  • Read Committed transaction isolation level allows a statement to see only the data that was committed prior to its commencement. There are NO dirty reads allowed but non-repeatable reads and phantom read are. "Read Committed" isolation level is the most widely used transaction isolation level in commercial databases. However there is NO reason to perceive that all is well with "Read Committed" isolation level. It will still require non-blocking reads as designed in Oracle (detour around the lock... as said above) for transaction to produce acceptable output.
  • Repeatable Read transaction isolation level guarantees read consistency i.e. a transaction that reads the data twice from a table at two different points in time will find the same value each time. It only allows "phantom read". You avoid both - the "dirty read" and "non-repeatable read" problems through this level of isolation. Some databases except Oracle achieve "Repeatable Reads" via the use of row level shared "read" locks, which prevents other sessions from modifying the data that a user has read. This is in addition to the fact that, in these systems, writers of data will bock readers of the data. This of course decreases concurrency. A "Repeatable Read" may be used optionally using "SELECT FOR UPDATE".
  • Serializable transaction isolation level is the most restrictive level of transaction isolation (NO dirty, non-repeatable and phantom reads allowed) and obviously to provide the highest degree of isolation. "Serializable transaction" isolation level only means that each transaction executes as if it is the only transaction executing in the database at that point of time. It does NOT imply that there is some serial ordering of the transactions. Rather it is based on the concept of "Schedule". A "schedule" is a sequence of operations from one or more transactions. If all the transactions executed serially, one after another, the schedule will also be "serial". If you can produce a schedule that is equivalent in its effect to a serial schedule, even though it may be derived from a set of concurrent transactions, is called a "serializable schedule". In short "serializable schedule" consists of a series of intermingled database operations drawn from several transactions, and the final outcome of a serializable sequence is a consistent database. Database systems like Oracle allows to use "Serializable isolation level" as an option.

Read Committed v/s Serializable level of isolation -

"Read committed" isolation level provides transaction consistency on a per-statement basis which means that non-repeatable read and phantom read problem is present in this level of isolation. Ideally we require transaction level consistency. Readers will not block writers and vice-versa. So we can consider that "read committed" isolation level only provides a good trade off between data consistency and data concurrency and hence suitable for standard OLTP applications, which consist of high-volume, concurrent, short-lived transactions, with few transactions likely to conflict with each other (and close to NO repeatation of queries), but provides better performance. A "serializable isolation level" is suited for databases where multiple consistent queries need to be issued. The overall throughput is much less this being a blocking isolation. As such serializable mode of concurrency is more appropriate for databases with mostly read-only transactions that run for a long time (OLAP systems).

Read-Only transaction -

Oracle provides a variation of the "serializable isolation level" in the form of "Read-Only transaction" which permits a transaction to only "see" the data that was committed before the transaction started and does not allow any changes to be done once started. The only difference between "read-only" and "serializable" is that, the later also allows the changes to be done. Read-only transactions are intended to support reporting needs, where the contents of the report needs to be consistent with respect to a single point in time (when the generation of report is started). If a certain database system does not implement "Read-Only" transactions then they use "Repeatable Read" isolation level and suffer the associated effect of shared "read" lock as said before.

So to conclude, we had discussion on the transaction concurrency in this post. The concurrency has to be implemented through different "Locking" schemes. Click Here to continue reading on locking.

Friday 23 March 2012

Distributed Database System - Principles

Please spend a moment to read the previous post "Distributed Database System - Introduction" as the text below may contain some references to it.

Continuing from the last post where we underlined the need for the Distributed Database Management Systems (DDBMS) for the today's world of universal dependence on information systems in which all sorts of people; the company's management, employees, customers, shareholders, franchisees, channel partners, including general public (potential customers / investors) need to have a quick access to the company's data; we now need to understand the technology that works behind the DDBMS.

However, since this blog is entitled "Cool Database Fundas" and the target audience includes the curious apart from the professionals, I have decided to drive through using an example which I hope will make the various technical terms understand easily for some even technically challenged readers.

Our example Distributed Database -
We have to implement a distributed database system for a fictitious company having its offices at Los Angeles, Singapore, New York (HQ), Paris and Tokyo. We have six large tables in our database namely A, B, C, D, E, and F and the motivation behind our client asking us to implement DDBMS solution is the response time has to be reasonably small apart from ensuring maximum availability, reducing the network traffic and providing the site autonomy.

Centralized Database approach -
Though our aim here is to build a DDB, we start our approach with a non-distributed centralized database at just one site say New York, it being the Head Quarter of the company and everybody else may access this data over the net. Though there are lot of problems arising out of concurrency implementation, making joins on the tables, security implementation etc. NOT showing up in this setup, the major issue being that if this single site fails then the entire system will come to stand still and of course there will be huge network traffic involved from other locations to the centralized database and no site autonomy for data is applicable in this approach.

Distribution based on data access frequency -
In our next approach, it makes sense to locate the tables at the sites where they are more frequently accessed than the other sites. Accordingly we are locating our tables - A & B at New York, C at Singapore, D & E at Tokyo, F at Paris and no tables at Los Angeles. This distribution has brought about "local autonomy" over the data, each site taking responsibility for its security, backup and recovery and concurrency control (for local transactions). However, the problems of centralized database don't seem to have been solved, rather escalated.

The system is still prone to single point failure - for example if the Paris site is down the table F is not available to anybody (so also same case with the other tables). Secondly, the problem may arise with joins if the query requires tables located at different sites. With the dispersed data the security is also vulnerable to a little extent as compared to when all the tables were in centralized database.

Distribution with replication -
"Replication" is the name given to the practice of maintaining synchronized copies of an object (say table) at multiple locations (say sites). We can have two considerations while replicating the tables -
  1. A table may be best replicated to another site where it is frequently required to minimize the network traffic.
  2. A table may be replicated to a site where it is convenient to join it with the table on that site when users use join queries again not only to minimize the network traffic than otherwise if the tables were to be stored on different sites, but also remove the complexity in join when tables are dispersed.
Of course now we get advantage of replication in availability; if a table is replicated at two or more sites and one of those sites goes down, still nobody (users) is affected since the table is accessible from other site(s).

The replication however had introduced another problem; the problem of concurrency control and data consistency across multiple copies of the tables. The security risk is also higher than the preceding case of "distribution based on data access frequency".
If we decide to have only one another copy of each table at a different site with the entire six tables at New York (being HQ), then the security and concurrency exposures are limited (as compared to replicating a table at more than one location). So here we have all tables at New York (A, B, C, D, E). Then we have B & F at Paris, D at Singapore, A & E at Los Angeles, and C at Tokyo. There are two bottlenecks in this arrangement -
  1. If a table is accessed heavily at more than two sites then we violate our own premise. (security and concurrency control exposure will escalate).
  2. The centralized place where all the tables are residing (New York) will be heavily loaded for all join requests will have to be handled there along with many of the other access requests.
So going by the considerations of locating the replications (earlier two points) and avoid the bottlenecks (the just preceding two points) we may arrive at a solution - We may have tables A, B & F at New York, D & E at Singapore, C & D at Los Angeles, A & F at Tokyo and B, D & E at Paris. Here we are considering table C is only single (not replicated as we think the table is not very important and infrequently used but only mostly accessed at Los Angeles. Also this is a case to show that there is a flexibility that not each of the tables must be replicated).

Concurrency Control with Two Phase Commit -
"Concurrency" is the name given to allowing two more users to perform transactions concurrently on the database rows without violating the integrity and consistency of the data. Databases use transaction locks to limit the concurrent operations by many different users from causing inconsistency in the data. The implementation of the concurrency is much more difficult in the replicated environment such as above than dealing with all the tables in a single server and only accessed from there. For example if a user at New York updates a particular value in a record of table B while at the same time another user updates the very same value in the very same record in Paris may result into an inconsistency according to the definition of transaction.

It is possible to implement the transmission of update on a table to its copies in different ways, particularly if the nature of the data and of the applications that use it can tolerate delay (backlash) in such update. Those methods are said to be "asynchronous". It could be either done by sending the message from site of actual update to the remote site where copy of the table exists and apply it there right away, or alternatively choosing one of the sites to accumulate all the updates (for all the tables) and transmission of changes may be scheduled. In a third "asynchronous" approach, each table may have one of the sites declared as "dominant" (for that table) to which all of the updates may be sent and from there transmit it to other copies of the table on scheduled basis.

However some popular commercial DBMS systems like Oracle use Two Phase Commit (2PC) process which is a "synchronous" algorithm. The "2PC" consists of two phases namely "Prepare Phase" and "Commit" phase. The mechanism uses a special "log" file to hold the update temporarily at all the sites. When an update is initialized at one site in a certain table (say D at Singapore) then the actual update is first written temporarily to the log file at every site (say Los Angeles & Paris) and NOT the copies of the table anywhere at this stage. The "Prepare Phase" first confirms with the remote locations (LA & Paris) having the copies of a table (D) under update at one site (update initializing site, Singapore) if they are in an operating condition and if they could lock the respective data to be updated (Oracle implements row level locking) in their copy of the table (D at LA & Paris) and if any of this condition is not met then either the transaction waits until favorable conditions are reached or transaction is aborted or otherwise (if conditions are met) the data makes way to the copies of the tables at all sites from the respective log files; which is part of the "commit" phase. So in this way all the copies of the table either stay at the original state if the update proceeds to fail at any location or get updated "synchronously".


Distributed Joins -
"Distributed Joins" involve tables at discreet locations required to be joined to satisfy a "join query" (query that required data being combined from two or more tables in a join condition). Various permutations and combinations may emerge for transmitting the data from one location to another or even third depending upon -
  1. if or not the location from where the request for join originated has copy of any of the tables involved in the join.
  2. the location where the join may be actually performed, transmitting the final or intermediate result.
A DDBMS system comes with a query optimizer which works hand-in-hand with relational query optimizer to determine the optimal way of performing the join operation in consideration to the following -
  1. The number and size of the records from each table involved in the join.
  2. The distances and costs of transmitting the records from one location to another to execute the join.
  3. The distance and cost of shipping the result of the join back to the location that initialized the join query.
Partitioning or Fragmentation -
When a table is divided then it is called as "partitioning" or "Fragmenting". There are two basic ways in which the tables in the DDBMS could be fragmented - Horizontally and Vertically. There may be third type that is hybrid of these both.
 
In the "horizontal partitioning" a table may be split in such a way that each site may contain some records. Essentially the structure of the table at each site is exactly the same. For example, for our fictitious company we may have an employee table horizontally at each location to store the data of employees working in the vicinity of that location. So the structure of the "employee" table will be identical at every site but only the records. This arrangement makes sense in such case when a site has to deal more with particularly their employees and say location like New York (HQ) requires to access the data of all the employees of the enterprise and so it has to be fetched from all the different locations and had to be put together (Union).

In the "vertical partitioning" we divide the columns of a table among several sites. However each such fragment of table containing a subset of columns of the full large table must include a primary key column of the full large table and rows in each such fragment are coordinated through the common value of primary key. This arrangement can make sense when different sites are responsible for processing different columns (attribute functions) of same entity. However in such case a multi-site join will have to processed if some site requires all the data of each entity.

Distributed Directory -
The notion of "location transparency"  in DDBMS comes from that when a query is fired then the system simply knows the location of different tables, their partitions, columns (or objects in general and their privilege sets etc.) and the other metadata required to satisfy the query. The set of system tables (data dictionary, directory or catalog) provides this knowledge to the system. However the question of location of the directory is as complex as the distributed data itself in the DDBMS and there are n number of possibilities. However in most cases maintaining a "synchronously updatabase" copy of the directory at each location is considered to be the best option.
 
So here we have walked through the "principles" of the DDBMS with a example and practical approach, however there is a systematic mathematical treatment to each of the concept discussed here.

Next time we meet with a new topic and it will be equally interesting one. Keep coming back.

Wednesday 21 March 2012

Distributed Database System - Introduction

Introduction -
Today's business environment has an increasing need for distributed databases as the desire for reliable, scalable and accessible information is steadily rising. Distributed Database Management Systems (say DDBMS) are an extension of the client / server technology where machine (say Node) takes a role as a client or server or both. DDBMS consists of several databases running on different servers and while being networked together and locally accessed as independent databases in their own right allow some privileged users to look upon this set up as logically a single large database. Rather, the users have no knowledge of those multiple databases running on different servers and they may perform the transactions and manipulations on the data in the same way as they would when connected to a normal single database set up.

Distributed Database Architecture -
Oracle's Distributed Database Architecture
On the right hand side is the diagram which represents the Oracle's Distributed Database Architecture and has been reproduced here from Oracle's documentation for our discussion and reference (DDBMS from other vendors use more or less the similar concept if not exact) -

At the center of the idea of DDBMS is the concept of communication channel between the databases called "Database Link" (say dblink). It is a logical object defined in the database (local database) which wants to share the data from a remote database on the request of the user (say application). It is unidirectional in the sense that the data over a dblink can flow from remote database toward the database (local database) which has defined the dblink (in the opposite of the direction of the link in the picture). However, the name of the dblink is derived with "Global Database Name" of the remote database. The global database name is formed by prefixing the database name with the database's domain name so that the global database name becomes unique throughout the world. For example sales.etrixdatasolutions.com. Further, an object "name resolution" is done in distributed environment by using unique object name qualifier formed by combining schema name and object name with an address of the global database name in which the object resides. For example - a table "emp" in "scott" schema in "sales" database may be referenced as scott.emp@sales.etrixdatasolutions.com. All the nodes apart from wired in any basic network protocol (like TCP/IP) of choice have Oracle's own network protocol NET8 riding over the basic protocols to provide heterogeneous network / communication environment among all the nodes. In general terms, the node which requests for the data is termed as "client" and the one which serves the request is called "server" which typically has installed Database Management System Software managing a database. There may be several servers (databases) networked together as above with appropriate dblinks created among them.

How Distributed Database System (DDBMS) works -
In the figure above we may consider the application to be running on a PC (say Client), issuing some statements seeking to perform the "transaction" (say Operation on data) in local database (HQ database to which it is physically connected) together with a few statements directed towards remote database (Sales database). Then for the part of the transaction statements and the tables residing on the local database (HQ) it acts as a server and takes the role as a client (say broker) while "brokering" the request for the remote database (Sales). In the same way the changes which are part of one transaction may be "committed" with a single "commit" statement by the user (application) and changes will be saved to the respective databases. The whole transaction mechanism as such works in a "seamless" manner, transparent to the application.


Why use Distributed Database System -
The motivation for using the DDBMS comes from the following advantages -
  • The development of computer networks promote decentralization - Networks allow the data sharing from remote servers and so there is no need all the data of an organization to be stored on a single server (and hence rely on that single server).
  • The organizational structure of the company might be reflected in the database organization - A company consists of different units (say departments) for carrying out its business and it is possible that each department may be provided with a database to work from it.
  • Capacity and Incremental growth - Expand as you go is always an economical option for every business instead of investing in the hardware with anticipated growth.
  • Reliability and availability - DDBMS allow the replication of the data across several nodes. Hence the failure of a node still allows access to the replicated copy of the data from another node.
  • Reduced communication overhead - Equally advantageous is the characteristic of the data replication to store the data close to its anticipated use. This also helps in reducing communication overhead.
The above list of reasons for adaption of the DDBMS system may not be exhaustive but may give an idea about its importance for an organization whose business may not be limited by a geographical limit.

"Distributed Database" Vs. "Distributed Processing" -
These two terms have distinct meanings yet closely related to each other. While "Distributed Databases" are well defined here before, the "Distributed Processing" occurs when an application system distributes its tasks among multiple computers in a network. For example an application designating the server (local) to which it is connected as "broker" to process its data request from the remote database, so the local server apart from being a server becomes a client to serve the application's such requests.

"Distributed Database" Vs. "Database Replication" -
Distributed Database System does not always mean replication of the data. However Database Replication is a possibility in the DDBMS. In a pure DDBMS, there is a single copy of data and supportive objects on the respective servers, whereas replication is the process of copying and maintaining database objects in multiple databases that makeup a distributed database system.

DDBMS characteristics in nutshell -
  • Collection of logically related shared data.
  • Data split into fragments.
  • Fragments may be replicated.
  • Fragments / replicas allocated to sites (nodes).
  • Sites linked by communication network.
  • Data at each site is under control of DBMS.
  • DBMSs handle local operations autonomously.
  • Each DBMS participates in at-least one global application.
So here was a brief introduction to the DDBMS, however there is technological side to the operation of the Distributed Database Management System. Click Here for continued reading to "Distributed Database System - Principles"

Monday 19 March 2012

IT Certifications - How much they're worth

The Background -
This time I am touching a seemingly non-technical topic, but important one; at times controversial and almost always leads to hot debates in the industry. I am myself a successful Oracle DBA, Corporate trainer, mentor and member-by-invitation on interview panels of few fortune IT companies, working in the industry for about 17+ years, without any educational background in IT and any formal training in Oracle, let alone certification, in first place joined IT industry after about working for equal number of years as maintenance engineer in power generation utility. The purpose of giving that little autobiography is the proof enough to some of the points that I will be making here. Did I mention about a part of my activities is also IT career counselling? Yes, I do that too, for an obvious consideration by my friends and acquaintances that it must have been an essential part of my life with that kind of my overall background.

As a part of my activity as IT career counsellor, I have to answer a volley of questions about the certifications - Is the certification really such a hot commodity? How much value a certification will add to my resume? Are certifications really worth the time and expenses? How important are they over an academic degree? What is the comparison between hands-on knowledge and certification? etc...

In general the tone of IT career aspirants seems to have been set as the certification is everything and the ONLY thing they require to take leap into this career. My purpose here is NOT to prove certifications are good, bad, mandatory, useless or worthless but just to put the things straight, discuss their appropriateness, validity, worthiness, importance and necessity and that to from my own experience and observations in the industry and also from most of the authors on this same subject who also have already endorsed my view.

What is Certification ? -
There is no doubt that the birth of idea of "certification" and motive behind it is very much pious. With the proliferation of IT, the company managers (who may not be so techie), always wanted that there should be some agency to assure the competency level of IT professionals they wanted to hire. Of course, the best judgement would be done by the vendors/originators of particular technology. So major IT giants like Microsoft, Oracle, Cisco, Linux, Sun etc. picked up this demand and planned in their own way and criteria some definite curriculum and on line exams, or practical exams or a combination of both and deputed some third party agencies to conduct / monitor it. So there came up so many franchise centres in most major cities and towns. They all engaged into aggressive marketing and targeted mostly the beginners, fresher and undergrads in the process overstating the importance of the certification. The pious purpose of building a competent work force with a relevant proof (vendor's certificate) for the industry was thus somewhere observed to be lost.

What do certification stands for? -
It is subject to one's perspective. A right time to Santa & Banta story to make the point stand out in a funny and interesting way. Once these two scientists decide to do some research on cockroaches. They wanted to know the effect of pulling off the legs of the cockroach on its behaviour. So they pulled off first of 6 legs of the cockroach who volunteered for their experiment and as they put him on floor, now got into senses of the pair's dreadful experiment, the cockroach struggeled to get away as much fast as it could but limited by loss of one leg. However, our scientists were not to leave him without their experiment ending into a "logical" conclusion. So they picked the creature up and it had to lose another of its leg, and the poor creature again tried in vain to totter away, but the pair of scientist were bent to continue till the creature should lose all of its legs and make observation for each loss of his leg. At last with no legs on when they put the cockroach down on the floor and cheered it to move, the poor creature won't, when Santa made an observation that probably the creature has become deaf and now can't take the orders hence not moving, while Banta totally had a different observation that the cockroach has become blind and so can't see and hence not moving.

The fun apart, the point here to make across is that the certifications too are subject to interpretations. What they mean to one employer may not be same to another. However in a general survey conducted by Robert Half Technology, that they put on net the link to which was available for some time on http://www.dice.com/ concluded that only 15% CEOs of the IT world cited certification in the relevant technology as a valuable qualification for an IT job applicant to posses. However, even they were still short of accepting that it should be the sole criteria for recruiting a candidate. In their opinion, while certification may indicate knowledge in the given area, it does not demonstrate in majority cases the ability to apply that knowledge at the workplace. Compared an academic degree with a certification without ample hands-on is just an additional piece of formal designation with no distinction. 100% employers showed their interest in job seekers who can contribute really to their companies rather than their decorations.


However to quote Socrates, "an unexamined life is not worth living", certification demonstrates an ongoing commitment to learning and keeping abreast with the technological advances for a "working" candidate. It shows you are ambitious and motivated enough to achieve a professional goal. Certification may reinforce your experience, reassure your employer about your skills and to that extent make your resume stand out from stack. However, certification does not become a substitute for rigorous hands-on training or experience.


Is Certification a hype or necessity? -
This question is very relevant since almost every certification requires substantial time, efforts and is highly expensive. Certifications have a very short life in the sense that they are valid only until a new version of the technology arrives in the market, and then you have to go for an upgrade. The preceding discussion and survey statistics mentioned makes one point clear, that the certifications are not nearly as important to most of the employers as your ability to apply knowledge and skills and contribute to the organization, which of course comes through exposure to technology than targeting an examination.


Notwithstanding everything foregoing, well-chosen certifications that reflect your skills and interests and reinforce your experience are definitely worth considering. With an overwhelming number of certifications, the current trend of pursuing certifications indiscriminately, just with intention to keep up with stream of new designations, is certainly a hype. Certifications are hot, mandatory, and lead to better job or pay package is nothing but a myth.


Exploding myth -
Certification is necessary, they attract employers and fetch better pay packages - False. Sound understanding, hands-on and exposure to the technology is more important. Certification in relevant technology in addition to these is certainly a bright spot.

Certification substitutes for non-IT related academic qualification - False. Most fields in IT sector are concept oriented and not related to any academic qualification. Certification does not prove employability either. Any intellect irrespective of his/her academic major can work in IT if he/she gets proper exposure through study and practice.

Certification adds value to your resume - True. Certification relevant to your experience exhibits your commitment to achieve professional goals and indicates an ongoing effort to excel. However, myriad of certifications with a false promise on performance has an adverse effect.

Certifications enhance employability of fresher - False. Without an exposure, a merely certified candidate is at par with academic degree. In most cases certifications are just gained by studying through FAQs without enough hands-on and coaching is provided by "certified" trainers rather than experienced faculties. So fresher must consider these factors before opting for a certification.

Conclusion -
Use certification as an opportunity to study further and enhance existing ability, which was exactly the purpose of certification when they were introduced. Doing certification neither is about keeping pace on a treadmill and outsmart others by fancy designations you earn, nor using them as license for getting a job, which they are actually not. 

Sunday 18 March 2012

Relational Database Model - Codd's Rules - Part 2

This is in continuation to the last post "Relational Database Model - Codd's Rules - Part 1"

The following is explanation of the remaining Codd's rules 7 - 12 -

Codd's Rule #7 (High-Level Insert, Update and Delete Rule) -
Supports "Set Based" operations or "Relational Algebra". A relational database must support basic relational algebra operations (projection, selection, join, product, union, intersection, division and minus). Relational databases must allow data retrieval in sets constructed of data from multiple rows and/or multiple tables (join / product operation...). This means that data manipulations must also be supported to happen on a set of rows retrieved on such basis rather than just for a single row in single table. For Example - If we want to delete certain rows, then for a "delete" statement fired by the user those rows which satisfy the specified criteria should be deleted as a set.

Codd's Rule #8 (Physical data independence) -
Programs or applications that manipulate the data in the relational database must be unaffected by changes in the way the data is physically stored. For example, in the file based system (non-RDBMS) of the database, the data is stored in the form of records in SDF (System / standard Data Format) or Delimited format. The programs accessing the data in such case was required to be aware of the position of the data, which when changed, required the set of programs to change that may be used to access / manipulate the data. One of the problems, for example that was faced in the recent years was "Y2K (year 2000) problem", also in the databases which required the century figures 19 or 20 to be introduce before the two figured years; like an insurance start date 051275 (ddmmyy) was required to be converted to 05121975 (ddmmyyyy) which increased the field length by 2 and so the change in the programs was required to cope up with this change in the structure and task was not just colossal but was also limited by time to be finished before the actual year 2000 dawned.


Codd's Rule #9 (Logical data independence) -
Relationships among tables, structure of tables, rows or columns should be able to be modified without impairing the function of applications and ad hoc queries. Logical data independence is more difficult to achieve than the physical data independence. Not only this change in database schema or structure of tables and relationships should not affect the application but further it should not require to recreate the database too.


Codd's Rule #10 (Data integrity independence) -
Data integrity is the function of DBMS. Consistency and accuracy of the data is very important. "Integrity Constraint" is the protocol (set of rules) to implement this. Integrity in the database takes 3 forms - Entity Integrity, Referential Integrity and Domain Integrity. [expect their explanation and implementation in some future post]. RDBMS allows to implement these integrity rules at the database level in the form of "database constraints" definable as objects (may be as part of definition of the tables) or in the form of programs (called triggers) written within the database (and there existence be part of metadata in "data dictionary" (also called Catalog). Also it must be possible to change such constraints as and when appropriate without affecting existing applications.


Codd's Rule #11 (Distribution independence rule) -
Supports distributed operations. Users can join the data from tables residing physically on different servers (and/or different databases). They should be allowed to seamlessly manipulate the data in those tables withing one transaction without having to know where the data actually resides (i.e. in which database and on which server). Also the integrity must be maintained across the whole operation. Moreover the existing application should continue to operate successfully (and without requiring any change) when existing distributed data are redistributed around the system.


Codd's Rule #12 (Non-subversion rule) -
Data integrity and security can not be subverted. There should not be any other path to subvert the data integrity. This means that the users should not be allowed to circumvent the data integrity (and security too) by following a different path and manipulating the data. If a relational system provides low level single-record-at-time interface then such interface can not be used to circumvent the integrity and security constraints defined in the higher level language (dealing with sets of records at a time).


Hope you had pleasure reading this pair of posts on Codd's Rules. Please visit again for some more interesting stuff. Please don't forget to leave your comments / technical addition to the posts.

Friday 16 March 2012

Relational Database Model - Codd's Rules - Part 1

The Background -
Dr. Edgar Frank Codd (1923-2003) introduced the "Relational Model" for database management systems in 1970 in a research paper entitled "A Relational Data Model of Data for Large Shared Data Banks" while working at IBM Research Laboratory, San Jose, California. This model uses the concept of a "Mathematical Relation" which is nothing but a table of values with certain specific constraints (Refer posts - Database Design - Normalization ... Part I, II, III) as its building blocks. The concept has its theoretical basis in set theory and first-order predicate logic. However, those "Rules" sometimes referred to as "Codd's 12 Commandments" were proposed by him in 1985 to articulately define his vision of the relational database, which he feared was being diluted by many vendors in early 1980s to repackage their existing products with a "relational" veneer.

There are actually 13 rules numbered 0 - 12. However, in practice, rule 0 is ignored (from the count) as it only insists on exclusive use of "relational facility" to manage the database. It is considered as fundamental to the database system to qualify as being called as "Relational".

It is said that NONE of the popular commercial database systems today available in the market are ideally "Relational" going by the rules of Codd and more formal definitions derived subsequently by other authorities in the subject. The reasons for this being are some controversial rules (like Rule #3) and some debatable issues like Three Valued Logic. Also some rules are difficult to implement if not impossible.

The simplified rules and their explanation in brief follows -

Codd's Rule #1 (The Information Rule) -
Data is "presented" in Tables. A set of related tables forms the database and all the data is represented as tables. There is no other way than the tables, in which data can be placed or viewed.


Codd's Rule #2 (Guaranteed Access Rule) -
Data is "logically" accessible. A relational database does not refer to the data by position or physical location. For example, you can not say, in a relational database like 5th record and at character position 24-29 is the designation of an employee XYZ. Each of data must be logically accessible by referencing a "table", a column (or some smallest combination of columns) with unique value designated as "primary key", and column(s) (of which data is to be known). For example you may know the job of an employee Peter with empid 1234 from the table named emp. 

Codd's Rule #3 (Systematic Treatment of "NULL" values) -
NULL s are treated uniformly as unknown values. "NULL" means the value that is simply not present or not available or may not be applicable. It is not allowed to be represented as "0" (zero) or '' (an empty string) for numeric or string values respectively, because this substitution does not represent the fact that the value is not present. Imagine, does it not look strange substituting 0 for the age of an employee whose information of age is currently not available? The NULL is independent of datatype. However NULL may cause problem of comparison (NULL can not be compared) and it propagates through arithmetic expression. For example comparison "if x = NULL then" is illegal and x + y will result in NULL if x is NULL and y holds 10. Actually in comparison like statements for NULL we write "if x is NULL then" or "if x is not NULL then". For dealing with the NULL values in expressions, we need to substitute an appropriate value in place of NULL (for example 0 in addition and 1 in multiplication) by using some function. (for example nvl(V,R) where V is the value; if NULL is replaced with R).


Codd's Rule #4 (Dynamic on-line catalog based on relational model) -
Database is self describing. This pertains to how should the database keep the data about itself - the Metadata. Metadata is the information about the structure of the tables, their relationships, ownership, allocation of privileges etc. Dr. Codd insists to store this information into tables (also called as catalog or data dictionary). This data must also be accessible to the appropriately authorized users using the same query language as the users use for accessing their owned tables.


Codd's Rule #5 (Comprehensive data sub-language rule) -
Use of single language to communicate with the database. Dr. Codd insisted on use of a "Non Procedural" or "Declarative" language for accessing the database; such language in which the users will only provide (declare) what they want and not how to get it. Apart from the basic query operations the language must also support Data Definition Operations (DDL), Data Manipulation Operations (DML), security and integrity constraints (DCL), Transaction Management Operations (commit or rollback), etc.


Codd's Rule #6 (The view updating rule) -
Provide alternative way for viewing the data. All the data is stored in tables. However, a relational database must not be limited to source tables when presenting the data to users. So we may be able to create a "view" on the data (technically it is a query statement stored in the database with a name and can be accessed in the same way as the table but in the background the data presented by the view is actually has been fetched from the table(s)). So views are termed as "virtual tables" or abstractions of the source tables. For to be able to show the current state of the data, the rule says - All views that are theoretically updateable must be updateable by the system.


With this we have covered the first 6 of the Codd's Rules in this part. Click Here for the definitions and explanation on codd's rules 7 through 12.

Wednesday 14 March 2012

Database Design - Normalization - Normal Form - Part III

You are requested to visit "Database Design .... Part II" for continuity with this post.
In the last two posts with the same heading we did all the ground work required to understand the concept and technique of Normalization and Normal Forms. This post may contain some bookish / hi-tech definitions - but no worries. The readers with heuristic approach may skip the hi-tech stuff and they still can understand normalization and normal forms from the examples.
Relational Database Design - The goal of a relational database design is to generate a set of relation schema that allows us to store information without redundancy and perform the various operations on the data without anomalies. This is achieved by designing the schema in appropriate Normal Form.  

Decomposition - It is a process to divide appropriately a "universal relation schema" with all database attributes into several relations each with fewer attributes to achieve a targeted Normal Form. A "BAD" decomposition procedure is one which may give rise to Lossy Decomposition or Lossy-join Decomposition. Ideally the decomposition should have following important properties -
  • Lossless-join decomposition
  • Dependency Preservation
  • No Repetition of Information
Functional Dependency Concept -
Functional dependency concept is at the center of the definition of "Normal Forms" or process of "Normalization". Functional dependency is a constraint on set of legal relation.
Definition – A Functional Dependency, denoted by X → Y, between two sets of attributes X  and Y that are subsets of R specifies a constraint on the possible tuples (read rows) that can form a relation state r of R. The constraint is that, for any two tuples t1 and t2 in r that have t1[X] = t2[X], they must also have t1[Y] = t2[Y].
This means that the values of the Y component or a tuple in r depend on, or are determined by, the value of the component X; alternatively, the values of X component of a tuple uniquely (or functionally) determine the values of the Y component.
(This was only a definition in mathematical format of the concept of dependency we discussed in "what is RDBMS - Part II" with an example of "account number" and "balance". This and some such stuff is for readers with scientific approach and academic interest)
Closure of a set of Functional Dependencies - There may be several functional dependencies that may be observed in a relation. For example a relation of students S = {Stid, Sub, Fees, Phone, Attendance}. Here Stid →Phone Attendance Sub and Sub →Fees are the dependencies which are semantically obvious dependencies. But also there is dependency Stid →Fees which is inferred (since Stid → Sub and Sub → Fees, by property of transitivity Stid → Fees). Let F be a set of functional dependencies. The Closure of F (indicated by F+) is the set of all functional dependencies logically implied by F.  

Closure of Attribute Sets - Given a set α of attributes of R and a set of functional dependencies F, we need a way to find out all the number of attributes of R that are functionally determined by α. This set of attributes is called as closure of attributes α under F. It is denoted by α+. Finding α+ is useful because – 
  • If α+ = R then α is superkey for R. 
  • If we find α+ for all α R then we have computed F+ 
Normalization of Relations -  Normalization of data can be considered as a process of analyzing the given "universal relation schema" based on their FDs (Functional Dependencies) and primary keys to achieve the desirable properties of –
  • Eliminating redundancy.  
  • Eliminating the insertion, deletion and update anomalies.
First Normal Form (1NF) –  A relation is in the First Normal Form (1NF) if the value of any attribute in the tuple (read row) must be single value (atomic) from the domain of that attribute. (in the following example however the "skills" column contains multiple skills.)

Empid Ename Qualification Skills
101 Peter BS Java,VB,Oracle
....
Following is the same relation in 1 NF (First Normal Form) with "redundancy". [Incorrect]
Empid Ename Qualification Skills
101 Peter BS Java
101 Peter BS VB
101 Peter BS Oracle
....
Following is the same relation in 1 NF (First Normal Form) with "repeating fields". [Incorrect]

Empid Ename Qualification Skill1 Skill2 Skill3 Skill4
101 Peter BS Java VB Oracle
....
Following is the normalized relation in 1 NF (First Normal Form) by decomposing into relations "Employee" and "Skills". [correct]

Employee
Empid Ename Qualification
101 Peter BS
....

Skills
Empid Skill
101 Java
101 VB
101 Oracle
102 PHP
102 ....
....
Second Normal Form (2NF) –  A relation is said to be in the Second Normal Form (2NF) if it is in the "first normal form" and then it does not show any "partial dependency" and hence the chances of a relation violating "2NF" is only when there is "composite primary key" (primary key in a relation is combination of 2 or more columns).
In the relation that follows :
  • Primary key is composite (stid + subject)
  • Partial dependency is observed - "Fees" depends on "Subject" and "Phone" depends on "stid".
  • Attendance has functional dependency - on composite primary key (stid + subject).
stid subject fees phone attendance
101 C 1000 12345 20
102 VB 1200 76589 25
101 Oracle 2000 12345 30
....

This relation has been decomposed into three relations to achieve the "2NF". Observe here that there is at least one relation that remains with the original composite Primary Key (stid + subject). In this case this relation is "Attendance".

Student
stid phone
101 12345
102 76589
103 .....
....

Subject
subject fees
C 1000
VB 1200
Oracle 2000
PHP ....
....

Attendance
stid subject Attendance
101 C 20
101 Oracle 30
102 VB 25
103 .... ....
....

Third Normal Form (3NF) – A relation is said to be in Third Normal Form (3NF) if it is already in the "1NF" and "2NF" and further does not have a non-key attribute functionally dependent on another non-key attribute, that is, there should be no "transitive dependency" of a non-key attribute on primary key.

In the following relation observe that the non-key attribute "location" is decided by (dependent upon) "deptid" which is a non-key attribute. The primary key is "empid". So here is the case of "transitive dependnecy". There is redundancy and also all the transaction anomalies - 

Empid Ename job salary deptid dname location
101 Peter Manager 4000 10 Accounting New York
102 Sarah Analyst 3000 20 Research Boston
103 Albert Clerk 2000 10 Accounting New York
....

And here below the same relation has been decomposed into two relations "Employee" and "Department" where "location" and "dname" has been moved to relation "Deparment" (and thus eliminating the "transitive dependency" - 
Employee
empid ename job salary deptid
101 Peter Manager 4000 10
102 Sarah Analyst 3000 20
103 Albert Clerk 2000 10
....

Department
empid ename job
10 Accounting New York
20 Research Boston
30 Sales Dallas
....

Boyce-Codd Normal Form (BCNF) – A relation is said to be in Boyce-Codd Normal Form (BCNF) if it is already in the "3NF" and further does not have overlapping composite key. A relation in "BCNF" always satisfy "3NF" but NOT every "3NF" is also "BCNF". For Example the following relation is in "3NF" (does not show any transitive or partial dependency).

In the following example we assume that a teacher may teach only one subject but one subject may be taught by 2 or more teachers and only a particular teacher teaches that subject to a particular student. Then combination (stid + subject) will decide the teacher and teacher decides the subject. The combination (stid + subject) is primary key, Teacher is (tends to be) candidate key, and potentially (stid + teacher) also tends to become the primary key. [however we don't accept the combination (stid + teacher) as primary key as it will give rise to partial dependency - subject depends on teacher and hence it is rejected]

stid subject teacher
101 RDBMS Peter
102 OS Albert
103 RDBMS Sarah
101 Micro Processor George
104 RDBMS Peter
....

The solution will be, to split the relation into two – {studentid, teacher} and {teacher,subject. In this example we have given more importance to "losslessness" and "non-additive decomposition" while ignoring the property of "preserving functional dependency" in the decomposed relations. (The discussion on the decomposition properties coming up shortly in next posts)

Multivalued Dependency & Fourth Normal Form (4NF)-
Multivalued dependencies (MVD) are a consequence of when we have two non-key multivalued attributes. For example consider the following relation -

empid skills langspeak spousename
101 VB,Oracle French,English Sarah
....

Now for this relation to be in "1NF" -
empid skills langspeak spousename
101 VB French Sarah
101 VB English Sarah
101 Oracle French Sarah
101 Oracle English Sarah
....

Now this relation decomposed to "4NF" -

EmpSkills -
empid skills
101 VB
101 Oracle
....

EmpLang -
empid Langspeak
101 French
101 English
....

EmpSpouse -
empid SpouseName
101 Sarah
....

In here we have learned the technique of Normalization. There are however some properties of a "good" decomposition remain to be covered. Let us meet again in the next blog shortly.