Databases

http://www.atlasindia.com/sql.htm

http://www.bluerwhite.org/btree/

Normalization

Normalization of a database helps in modifying the design at later times and helps in being prepared if a change is required in the database design.

http://www.atlasindia.com/sql.htm

1nd Normal Form or 1NF:

Each Column Type is Unique.

2nd Normal Form or 2NF:

1NF +  all attributes within the entity should depend solely on the entity’s unique identifier.

3rd Normal Form or 3NF:

2NF +  no column entry should be dependent on any other entry (value) other than the key for the table.  If such an entity exists, move it outside into a new table.

B-Trees

B-Trees are used to store the data on external storage like disks. Unlike main memory, disk access are expensive. So B-Trees tries to minimize the access

http://www.bluerwhite.org/btree/
http://jorendorff.github.io/hackday/2012/library/

These links explains it well and I will try to summarize it here. Consider the problem of arranging books in library for fast search Libraries use multiple hierarchies/catalog to organize the books. Why don’t we just arrange all the books in (alphabetic) sorted order and binary search. After all, binary search is the best method to find an object in computer memory.

There is a problem with extending it to our library. Binary search assumes accesses time of any location is same. It ignores the fact that in a physical library we have to walk down to access the books (and the walking time is significantly costly compared to cost of checking if a book is the search candidate) .

In our library analogy, the book we are searching represents the key we are looking for, the library’s hierarchical catalog is the B-Tree. The walking time is the seek time when the data is stored on disk. If the walking time is negligible (say you have robotic eyes and can view all the book’s titles without having to walk), then binary search is in-fact better. The robotic eyes means random access to any location is constant time.

If data is in main-memory, it means we have robotic eyes without the need for walking and use binary search. If the data is in disk, it means we have to walk (seek the location on disk) and use better hierarchical organization to avoid walking (seeking)

2 Responses to Databases

  1. Hyperbook says:

    B-trees http://cs.kangwon.ac.kr/~leeck/file_processing/B-tree.pdf
    Micheal Folk is the best book on this subject..if you cannot get the book there are few online resoures https://drive.google.com/…/fol…/0B3mkI-9m0-QfT3FQQ3JTYmhMT1k

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s