Saturday, January 31, 2015

Dependency Preservation


Define dependency preservation / What is dependency preservation? / Why do we need dependency preserving decomposition? / The need for dependency preserving decomposition / dependency preserving decomposition example / What is dependency Preservation property for decomposition? / Why dependency preservation is important? / Dependency preservation property of normalization process


Dependency Preservation


A decomposition of a relation R into R1, R2, R3, …, Rn is dependency preserving decomposition with respect to the set of Functional Dependencies F that hold on R only if the following is hold;

(F1 U F2 U F3 U … U Fn)+= F+
where,
F1, F2, F3, …, FnSets of Functional dependencies of relations R1, R2, R3, …, Rn.

(F1U F2 U F3 U … U Fn)+ - Closure of Union of all sets of functional dependencies.

F+ - Closure of set of functional dependency F of R.

If the closure of set of functional dependencies of individual relations R1, R2, R3, …, Rn are equal to the set of functional dependencies of the main relation R (before decomposition), then we would say the decomposition D is lossless dependency preserving decomposition.

Discussion with Example of Non-dependency preserving decomposition:


Dependency preservation is a concept that is very much related to Normalization process. Remember that the solution for converting a relation into a higher normal form is to decompose the relation into two or more relations. This is done using the set of functional dependencies identified in the lower normal form state. 

For example, let us assume a relation R (A, B, C, D) with set of functional dependencies F = {AB, BC, CD}. There is no partial dependency in the given set F. Hence, this relation is in 2NF. 

Is R (A, B, C, D) in 3NF? No. The reason is Transitive Functional Dependency. How do we convert R into 3NF? The solution is decomposition. 

Assume that we decompose R(A, B, C, D) into R1(A, C, D) and R2(B, C).
In R1(A, C, D), the FD CD holds. In R2(B, C), the FD BC holds. But, there is no trace of the FD AB. Hence, this decomposition does not preserve dependency.

What wrong would the above decomposition cause?

In R, the following were held;

  • value of B depends on value of A,
  • value of C depends on value of B,
  • value of D depends on value of C.
after decomposition, the relations R1 and R2 are holding the following;

  • value of C depends on value of B,
  • value of D depends on value of C.

The dependency AB is missing. This causes acceptance of any values for B in R2. It causes duplicate values to be entered into R2 for B which may not depend on A. If we would like to avoid this type of duplication, then we need to perform a join operation between R1 and R2 to accept a new value for B which is costlier operation. Hence, we demand the decomposition to be a dependency preserving decomposition.

Few key points;

  • We would like to check easily that updates to the database do not result in illegal relations being created.
  • It would be nice if our design allowed us to check updates without having to compute natural joins.
  • We can permit a non-dependency preserving decomposition if the database is static. That is, if there is no new insertion or update in the future.
Example:

Assume R(A, B, C, D) with FDs AB, BC, CD.
Let us decompose R into R1 and R2 as follows;
R1(A, B, C)
R2(C, D)
The FDs AB, and BC are hold in R1.
The FD CD holds in R2.
 All the functional dependencies hold here. Hence, this decomposition is dependency preserving. 


Friday, January 30, 2015

Partial Functional Dependency - Definition


Partial Functional Dependency - Definition / What is Partial dependency? / Example for partial key dependency / Partial key functional dependency - an overview

Partial Dependency


Partial Dependency is a form of Functional dependency that holds on a set of attributes. It is about the complete dependency of a right hand side attribute on one of the left hand side attributes. In a functional dependency XY Z, if Z (RHS attribute) can be uniquely identified by one of the LHS attributes, then the functional dependency is partial dependency.

Example:
Let us assume a relation R with attributes A, B, C, and D. Also, assume that the set of functional dependencies F that hold on R as follows;
F = {A B, D C}.
From set of attributes F, we can derive the primary key. For R, the key can be (A,D), a composite primary key. That means, AD BC, AD can uniquely identify B and C. But, for this case A and D is not required to identify B or C uniquely. To identify B, attribute A is enough. Likewise, to identify C, attribute D is enough. The functional dependencies AD B or AD C are called as Partial functional dependencies.

Operating Systems Concepts, Questions with Answers


All Operating Systems Questions with Clear Answers / Operating Systems Exercises Solved / Solutions for Exercises in Operating Systems / Operating Systems selected Questions with Answers / Operating Systems Notes / Index for various online materials on Operating Systems



1. Processes and Threads

2. Inter-process Communication

3. Inter-process Communication in Linux

4. Process Scheduling

5. Process Scheduling in Linux

6. Process Synchronization

7. Deadlocks

8. Memory Management

9. Memory Management in Linux

10. File System Concepts

11. File System Implementation

12. File System in Linux

13. File System in Windows

Advanced Concepts in Operating System

1. Distributed OS

2. Distributed Deadlock Handling

3. Distributed Shared Memory

4. Multiprocessor OS


1. Peterson’s algorithm


2. Inter Process Communication (IPC) through Shared Memory, Race Conditions, Mutual Exclusion, Peterson's Algorithms etc.


3. Scheduling Algorithms


4. Paging and TLB


5. Deadlock




8. Memory Management


9. Distributed Operating Systems
With the advent of computer networks, in which many computers are linked together and are able to communicate with one another, distributed computing became feasible. A distributed computation is one that is carried out on more than one machine in a cooperative manner. A group of linked computers working cooperatively on tasks, referred to as a distributed system, often requires a distributed operating system to manage the distributed resources. Distributed operating systems must handle all the usual problems of operating systems, such as deadlock. Distributed deadlock is very difficult to prevent; it is not feasible to number all the resources in a distributed system. Hence, deadlock must be detected by some scheme that incorporates substantial communication among network sites and careful synchronization, lest network delays cause deadlocks to be falsely detected and processes aborted unnecessarily. Interprocess communication must be extended to processes residing on different network hosts, since the loosely coupled architecture of computer networks requires that all communication be done by message passing. Important systems concerns unique to the distributed case are workload sharing, which attempts to take advantage of access to multiple computers to complete jobs faster; task migration, which supports workload sharing by efficiently moving jobs among machines; and automatic task replication at different sites for greater reliability. 




Wednesday, January 28, 2015

Functions of Database Administrators


Functions of Database Administrator / List the major functions of a DBA / What are the functions of a database administrator? / Functions of DBA with simple examples


Functions of Database Administrator (DBA)

Database Administrator is one of the stakeholders of DBMS. He is role is to control the database system as a whole. The major functions of a DBA are the following;

  • Selection of hardware and software:for example, he has to anticipate the size of the database in the near future and go for necessary hardware.
  • Schema definition / Database structure definition: DBA is the person who defines the structure of a database and creates databases using set of DDL statements. For example, DBA can create a table using SQL as follows;
CREATE TABLE stu(Regno CHAR(5) PRIMARY KYE, SName VARCHAR(30) NOT NULL, Phone NUMBER(10) NOT NULL);

  • Storage structure and access-method definition: DBA defines the way to store data and the ways to access the stored data. Some of the access methods include, how to use indexes?, when to use indexes? how to store tables? etc.
  • Schema and physical organization modification: DBA changes the structure of the tables or other database components, modifies the physical organization of data files etc. This alteration is mainly performed to improve the system efficiency. For example, the structure of the table stu created above can be modified as follows to add another attribute Gender;
ALTER TABLE stu ADD Gender CHAR(1) NOT NULL CHECK (Gender in (‘M’, ‘F’));

  • Granting of authorization for data access: DBA decides and permits various users to access database. Normally, one cannot permit all the users to access all the content of a database. In reality, except DBA all the other users are considered as restricted users. DBA can restrict users to access only a portion of a table, only to view records, only to insert records, only to insert and modify records and so on. For example, the following statement permits the user Ram to view the records from the table stu;
GRANT SELECT ON stu TO Ram;

  • Routine maintenance: Schema definition, alteration, and physical organization modification are usually done only very few times by the DBA. The major work is to maintain the database and its users. The following list shows some of the routine maintenance work of a DBA;

Authorizing users
Backing up of database
Recovery of database in case of failures
Checking the availability of disk space
Checking the performance of the DBMS
Monitoring for unauthorized access etc.
 

All the functions listed above are well defined and includes various sub-functions according to the business application.