Lecture 1 Relational Databases Refresher

Seite 1

• Foreign-Key?

In the context of relational databases, a foreign key is a field (or collection of fields) in one table that uniquely identifies a row of another table. In simpler words, the foreign key is defined in a second table, but it refers to the primary key in the first table.

• Normal Forms? [1] [2]

Database Normalisation is a technique of organizing the data in the database. Normalization is a systematic approach of decomposing tables to eliminate data redundancy and undesirable characteristics like Insertion, Update and Deletion Anamolies. It is a multi-step process that puts data into tabular form by removing duplicated data from the relation tables.

Normalization is used for mainly two purpose,

Eliminating reduntant(useless) data.

Ensuring data dependencies make sense i.e data is logically stored

First Normal Form (1NF) As per First Normal Form, no two Rows of data must contain repeating group of information i.e each set of column must have a unique value, such that multiple columns cannot be used to fetch the same row. Each table should be organized into rows, and each row should have a primary key that distinguishes it as unique.

The Primary key is usually a single column, but sometimes more than one column can be combined to create a single primary key. For example consider a table which is not in First normal form

Student Table :

StudentAgeSubjectAdam15Biology, MathsAlex14MathsStuart17MathsIn First Normal Form, any row must not have a column in which more than one value is saved, like separated with commas. Rather than that, we must separate such data into multiple rows.

Student Table following 1NF will be :

StudentAgeSubjectAdam15BiologyAdam15MathsAlex14MathsStuart17MathsUsing the First Normal Form, data redundancy increases, as there will be many columns with same data in multiple rows but each row as a whole will be unique.

Second Normal Form (2NF) As per the Second Normal Form there must not be any partial dependency of any column on primary key. It means that for a table that has concatenated primary key, each column in the table that is not part of the primary key must depend upon the entire concatenated key for its existence. If any column depends only on one part of the concatenated key, then the table fails Second normal form.

In example of First Normal Form there are two rows for Adam, to include multiple subjects that he has opted for. While this is searchable, and follows First normal form, it is an inefficient use of space. Also in the above Table in First Normal Form, while the candidate key is {Student, Subject}, Age of Student only depends on Student column, which is incorrect as per Second Normal Form. To achieve second normal form, it would be helpful to split out the subjects into an independent table, and match them up using the student names as foreign keys.

New Student Table following 2NF will be :

StudentAgeAdam15Alex14Stuart17In Student Table the candidate key will be Student column, because all other column i.e Age is dependent on it.

New Subject Table introduced for 2NF will be :

StudentSubjectAdamBiologyAdamMathsAlexMathsStuartMathsIn Subject Table the candidate key will be {Student, Subject} column. Now, both the above tables qualifies for Second Normal Form and will never suffer from Update Anomalies. Although there are a few complex cases in which table in Second Normal Form suffers Update Anomalies, and to handle those scenarios Third Normal Form is there.

Third Normal Form (3NF) Third Normal form applies that every non-prime attribute of table must be dependent on primary key, or we can say that, there should not be the case that a non-prime attribute is determined by another non-prime attribute. So this transitive functional dependency should be removed from the table and also the table must be in Second Normal form. For example, consider a table with following fields.

Student_Detail Table :

Student_idStudent_nameDOBStreetcityStateZipIn this table Student_id is Primary key, but street, city and state depends upon Zip. The dependency between zip and other fields is called transitive dependency. Hence to apply 3NF, we need to move the street, city and state to new table, with Zip as primary key.

New Student_Detail Table :

Student_idStudent_nameDOBZipAddress Table :

ZipStreetcitystate The advantage of removing transtive dependency is,

Amount of data duplication is reduced.

Data integrity achieved.

Boyce and Codd Normal Form (BCNF) Boyce and Codd Normal Form is a higher version of the Third Normal form. This form deals with certain type of anamoly that is not handled by 3NF. A 3NF table which does not have multiple overlapping candidate keys is said to be in BCNF. For a table to be in BCNF, following conditions must be satisfied:

R must be in 3rd Normal Form

and, for each functional dependency ( X -> Y ), X should be a super Key.

• Two-Phase Commit? [3]

Unlike a transaction on a local database, a distributed transaction involves altering data on multiple databases. Consequently, distributed transaction processing is more complicated, because the database must coordinate the committing or rolling back of the changes in a transaction as a self-contained unit. In other words, the entire transaction commits, or the entire transaction rolls back.

The database ensures the integrity of data in a distributed transaction using the two-phase commit mechanism. In the prepare phase, the initiating node in the transaction asks the other participating nodes to promise to commit or roll back the transaction. During the commit phase, the initiating node asks all participating nodes to commit the transaction. If this outcome is not possible, then all nodes are asked to roll back.

All participating nodes in a distributed transaction should perform the same action: they should either all commit or all perform a rollback of the transaction. The database automatically controls and monitors the commit or rollback of a distributed transaction and maintains the integrity of the global database (the collection of databases participating in the transaction) using the two-phase commit mechanism. This mechanism is completely transparent, requiring no programming on the part of the user or application developer.

• ACID? BASE? [4]

ACID: Example: RDBMS

Atomicity: The database transaction must completely succeed or completely fail. Partial success is not allowed.

Consistency: During the database transaction, the RDBMS progresses from one valid state to another. The state is never invalid.

Isolation: The client’s database transaction must occur in isolation from other clients attempting to transact with the RDBMS.

Durability: The data operation that was part of the transaction must be reflected in nonvolatile storage(computer memory that can retrieve stored information even when not powered — like a hard disk) and persist after the transaction successfully completes.

BASE: Example: NoSQL.

By relaxing consistency, the system can horizontally scale (many nodes) and ensure availability.

BasicallyAvailable: The system is guaranteed to be available for querying by all users. (No isolation here.)

Soft State: The values stored in the system may change because of the eventual consistency model, as described in the next bullet.

Eventually Consistent: As data is added to the system, the system’s state is gradually replicated across all nodes. For example, in Hadoop, when a file is written to the HDFS, the replicas of the data blocks are created in different data nodes after the original data blocks have been written. For the short period before the blocks are replicated, the state of the file system isn’t consistent.

• CAP?[5] [6]

In theoretical computer science, the CAP theorem, also named Brewer's theorem after computer scientist Eric Brewer, states that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:[1][2][3]

Consistency (every read receives the most recent write or an error)

Availability (every request receives a response, without guarantee that it contains the most recent version of the information)

Partition tolerance (the system continues to operate despite arbitrary partitioning due to network failures)

In other words, the CAP theorem states that in the presence of a network partition, one has to choose between consistency and availability.

• Hadoop? Yarn? Spark?

Will be covered when respective chapters are covered in class

• Degree and Cardinality [7]

Simply put, in a relation (table), number of rows: degree and number of columns= cardinality

1. Degree. This is the number of entities involved in the relationship and is usually 2 (a binary relationship). Unary relationships also exist, where only 1 entity is involved - a person is married to another person, or an employee manages other employees.

(Remember - 'entity' and 'instance of an entity' are not the same thing. John Smith is a Customer. The entity is Customer, John is an instance of an entity.)

Tenary relationships exist (3 entities are involved) as do quaternary (4) or n-ary (n). There are a number of strategies for resolving these which we will look at some other time.

2. Cardinality. This specifies the number of each entity that is involved in the relationship. There are 3 types of cardinality for binary and unary relationships:

One to one (1:1). For example, 1 man is married to 1 woman.

One to many (1:m). For example, 1 manager manages many employees, each employee is managed by 1 manager.

Many to many (m:n). For example, Each students take many modules, each module is taken by many students.

How many is many? It doesn't matter! If it's 0, 10 or 100, the way you implement the relationship is the same.

References

[1]http://beginnersbook.com/2015/05/normalization-in-dbms/

[2]http://www.studytonight.com/dbms/database-normalization.php

[3] https://docs.oracle.com/cd/B28359_01/server.111/b28310/ds_txns003.htm

[4] https://neo4j.com/blog/acid-vs-base-consistency-models-explained/

[5] https://dzone.com/articles/better-explaining-cap-theorem

[6] https://en.wikipedia.org/wiki/CAP_theorem

[7] http://n12503.blogspot.ch/2005/11/relationship-degree-cardinality-and.html