Complete Computer Science guide: DBMS

Relational algebra is a notation for representing the types of operations which can be performed on relational databases. It is used in a RDBMS as the intermediate language for query optimization.

A relation is a set of k-tuples, for some k called the arity of the relation. In general, names are given to the components of the tuple (a tuple corresponds to a record - Pascal or structure - C with fields corresponding to the names of the components). Note: this definition implies that each tuple is unique. Each relation is described by a schema which consists of a relation name and a list of attribute names - relation-name(attribute-list). R(A1, ..., An), R.Ai.

A relational algebra is an algebraic language based on a small number of operators which operate on relations (tables). It is the intermediate language used by a RDBMS. Queries are expressed by applying special operators to relations.

Figure 1: Relational Algebra
expression	::=	relation \| monadic-expression \| dyadic-expression
monadic-expression	::=	selection \| projection \| renaming
dyadic-expression	::=	expression diadic-operation expression
selection	::=	σ_{selection-condition} (relation-name)
projection	::=	π attribute - list ( relation - name )
renaming	::=	ρ_{attribute-list}(relation-name)
dyadic-operation	::=	U\| − \| × \| ∩ \| ÷ \| \|〉〈\|_{join-condition}
selection-condition	::=	logical-condition \| comparison

Eight operations were originally defined for relations. Each of these creates a new relation from an existing relation or set of relations.

• Basic Operators

1. Selection: Selects a subset of tuples from a particular relation, based upon a specified selection condition. The selection condition is a boolean expression formed from the names of the attributes of the relation and constants.

2. Projection: Drops columns from a relation retaining only those in the attribute list.

3. Set union: Combines tuples of two relations with like attributes.

Both relations must have the same number of columns.
The names of the attributes are the same in both relations.
Attributes with the same name in both relations have the same domain.

4. Set difference: Finds tuples in two relations with like attributes which are in the first relation but not the second.

5. Cartesian product: Creates a new relation from all concatenations of two relations. NOTE: this is the most computationally expensive operator in the relational algebra.

Renaming: The attribute names in the attribute list replace the attribute names of the relation. ρS(A1,...,An)(R) is the same relation as R but its name is S with the attributes named. A1,...,An.

• Derived operators

1. Set intersection: Finds the common tuples in two relations with like attributes.

2. Divide: Takes two relations, with attributes {X1...XN,Y1...YM} and {Y1...YM} respectively, and returns a relation with attributes {X1...XN} representing all the tuples in the first with matched every tuple in the second relation.

3. Join: Creates new relation from all combinations of tuples in two relations with some matching attributes - R|〉〈|join-conditionS = σjoin-condition (R × S). While this relation has the potential to be computationally expensive (due to the cartesian product) the join-condition typically allows the operation to be relatively inexpensive.

The join defined above is called a theta-join.
Equijoins are joins where the join-condition only involves equalities.

Back to main directory:

DBMS

1. Client-Server Database Systems
A client is defined as a requester of services and a server is defined as the provider of services.
Today centralized systems act as server systems that satisfy requests generated by client systems.
Functionally database systems can be broadly divided into two parts:
• Front end: front end of a database system consists of tools such as SQL user interface, forms interfaces, reports generation tools, and analysis tools.
• Back end: The back end of a database system manages query evaluation and optimization, access structures, concurrency control and recovery management.

2. Parallel Systems
In parallel processing, many operations are performed simultaneously and the computational steps are performed sequentially. It can process thousands of transactions per second.
There are four types of Architectural Models for Parallel Processing:
• Shared Memory (tightly coupled) architecture: Multiple processors share secondary (disk) storage and also share primary memory.
• Shared Disk (loosely coupled) architecture: Multiple processors share secondary (disk) storage but each has their own primary memory.
• Shared Nothing: The processors share neither a common memory nor common disk.
• Hierarchical: this model is the combination of preceding three architectures.

3. Distributed Systems
Distributed database is a collection of multiple logically interrelated databases distributed over a computer network and a distributed database management system is a software system that manages a distributed database while making the distribution transparent to the user. Transparency means hiding the details of where the data is physically stored within the system.
Reasons for building a distributed database are sharing of data, autonomy, and availability.
Functions of distributed databases:
• Keeping track of data.
• Query Processing by a communication network.
• Security Management.
• Distributed Transaction Management
• Database Recovery.

Back to main directory:

DBMS

The goal of Three-Schema architecture is to separate the user applications and physical database. In this architecture, schemas can be defined at the following three levels:

The internal level:- The internal level has an internal schema which describes the physical storage structure of the database.

The conceptual level:-The conceptual level has a conceptual schema, it describes the entities, data types, relationships, user operations and constraints.

The external level or view level:- The external or view level includes a number of external schemas or user views. It describes the part of the database that a particular user group is interested in and hides the rest of the database from that user group.

Back to main directory:

DBMS

Data model is defined as the collection of conceptual tools for describing data, data relationships, data semantics and consistency constraints. There are following four Data Model exists.

THE HIERARCHICAL DATA MODEL
A hierarchical database consists of the following:
1. It contains nodes connected by branches same as the trees in datastructers.
2. The top node is called the root.
3. If multiple nodes appear at the top level, the nodes are called root segments.
4. The parent of node nx is a node directly above nx and connected to nx by a branch.
5. Each node (with the exception of the root) has exactly one parent.
6. The child of node nx is the node directly below nx and connected to nx by a branch.
7. One parent may have many children.

THE NETWORK DATA MODEL
Like the The Hierarchical Data Model the Network Data Model also consists of nodes and branches, but a child may have multiple parents within the network structure.

THE RELATIONAL DATA MODEL
The Relational Data Model has the relation at its heart, but then a whole series of rules governing keys, relationships, joins, functional dependencies, transitive dependencies, multi-valued dependencies, and modification anomalies. A relation is subject to the following rules:
1. Relation (file, table) is a two-dimensional table.
2. Attribute (i.e. field or data item) is a column in the table.
3. Each column in the table has a unique name within that table.
4. Each column is homogeneous. Thus the entries in any column are all of the same type (e.g. age, name, employee-number, etc).
5. Each column has a domain, the set of possible values that can appear in that column.
6. A Tuple (i.e. record) is a row in the table.
7. The order of the rows and columns is not important.
8. Values of a row all relate to some thing or portion of a thing.
9. Repeating groups (collections of logically related attributes that occur multiple times within one record occurrence) are not allowed.
10. Duplicate rows are not allowed (candidate keys are designed to prevent this).
11. Cells must be single-valued (but can be variable length). Single valued means the following:
o Cannot contain multiple values such as 'A1,B2,C3'.
o Cannot contain combined values such as 'ABC-XYZ' where 'ABC' means one thing and 'XYZ' another.

Object Oriented Model
In object oriented model information is represented in the form of objects as used in object oriented programming. Object Oriented Database Management Systems is a combination of object oriented programming language capabilities and database capabilities. It contains some properties like transparently persisted data, concurrency control, data recovery, associative queries, and other capabilities. Some object oriented programming languages are Java, C++, .NET, Visual Basic, Python etc. Most object databases also offer some kind of query language, allowing objects to be found by a more declarative programming approach.

Back to main directory:

DBMS

DBMS stands for Database Management System. A DBMS consists of collection of interrelated data and a set of program to access that data. The collection of data is known as a database. A database consists of the data related to one organization. Prior to DBMS systems, the data was kept under the file system in forms of multiple files. The following are the disadvantages of the File system:-

1. Difficulty in Accessing data:- In the file system it is very difficult to find the data which is needed for some specific purpose. Like to get the average sale of the quarter needs to process all files for the quarter and then do some processing.

2. Data inconsistency and redundancy:- As the files and processing systems created by different vendors and programmers, so there is a inconsistency of data as different people prefer the different style of data handling. Also the different systems may use the different programming languages to develop the processing systems so the multiple copies of the same file kept under various places so redundancy is another problem we have with file system.

3. Security Problem:- There is a great risk of unauthroized person access the file system and get the data. So security is the major concern in the file system.

4. Integrity Problem:- The integrity issue is also a major concern as the data stored in the file can be changed easily. While creating files there is no specific rules checked while storing the data.

ADVANTAGES OF DATABASE MANAGEMENT SYSTEM:-

The following are the advantages of DBMS systems:-

1. A data can be validated before storing into the DBMS system.These rules for data validation are known as Constraints in DBMS.

2. Different users can be created with different rights for the database.So DBMS systems are more secure than the conventional file system.

3. The relationships of the data can also be stored along with the data which is not possible for the files.

4. A simple english like language SQL is introduced which helps to access data more efficiently and quickly.

5. Multiple users can access the data simultenously and DBMS system will take care the conflicts.

6. The dependent tasks can be controlled with transaction management facility of the DBMS. For example:- Transfering the cash from one account to second account consits of withdrawing the amount from one account and deposit in other. What if the application fails after the withdrawl so DBMS system will rollback the withdrawl automatically.

Back to main directory:

DBMS

Databases use tables to organize information. Each table consists of a number of rows, each of which corresponds to a single database record. Databases keep all of these records through the use of keys.

Candidate Key

A candidate key is a combination of attributes that can be uniquely used to identify a database record without any extraneous data. Each table may have one or more candidate keys. One of these candidate keys is selected as the table primary key.

Alternately, Candidate Key is a column or group of columns that uniquely describe every row in a table.

For instance, in a table that describes people (employees, customers, club members, whatever), there are many columns that describe those people. If you accept the assertion that you can't have two people with the same name, one of your CKs could be the person's name. If you accept the assertion that you can't have two people with a given phone number, one of your CKs could be the phone number. A candidate key must possess the following properties:

Unique identification - For every row the value of the key must uniquely identify that row.
Non redundancy - No attribute in the key can be discarded without destroying the property of unique identification.

Surrogate Key

A Surrogate Key (SK) is an arbitrary value that is used solely by the database (and therefore by any programs that use that database) to uniquely identify a row. This can be a GUID, an "automagically" assigned number, or just some arbitrary value that happens to be unique for every row. SKs are guaranteed to be unique (that is part of their definition), so they are always CKs. Using an SK can be extremely convenient because it allows the database to function independently of any changes to the business rules that make other CKs unique.

Primary Key

A unique key or primary key is a candidate key to uniquely identify each row in a table. A unique key or primary key comprises a single column or set of columns. No two distinct rows in a table can have the same value (or combination of values) in those columns. Depending on its design, a table may have arbitrarily many unique keys but at most one primary key.

The value this key holds should be unique for each record in the database. For example, assume we have a table called Employees that contains personnel information for every employee in our firm. We’d need to select an appropriate primary key that would uniquely identify each employee. Your first thought might be to use the employee’s name.

This wouldn’t work out very well because it’s conceivable that you’d hire two employees with the same name. A better choice might be to use a unique employee ID number that you assign to each employee when they’re hired. Most organizations have used unique identifiers (employee ID, student ID, etc.).

Once you decide upon a primary key and set it up in the database, the database management system will enforce the uniqueness of the key. If you try to insert a record into a table with a primary key that duplicates an existing record, the insert will fail.

Most databases are also capable of generating their own primary keys. Microsoft Access, for example, may be configured to use the AutoNumber data type to assign a unique ID to each record in the table. While effective, this is a bad design practice because it leaves you with a meaningless value in each record in the table.

Alternate Key

An alternate key (or secondary key) is any candidate key which is not selected to be the primary key (PK).

For example, a relational database with a table "employee" could have attributes like "employee_id", "bank_acct_no", and so on. In this case, both "employee_id" and "bank_acct_no" serve as unique identifiers for a given employee, and could thus arguably be used for a primary key. Hence, both of them are called "candidate keys". If, for example, "bank_acct_no" was chosen as the primary key, "employee_id" would become the alternate key.

Foreign Keys

These keys are used to create relationships between tables. Natural relationships exist between tables in most database structures. Returning to our Employees database, let’s imagine that we wanted to add a table containing departmental information to the database. This new table might be called Departments and would contain a large amount of information about the department as a whole. We’d also want to include information about the employees in the department, but it would be redundant to have the same information in two tables (Employees and Departments). Instead, we can create a relationship between the two tables.

Let’s assume that the Departments table uses the Department Name column as the primary key. To create a relationship between the two tables, we add a new column to the Employees table called Department. We then fill in the name of the department to which each employee belongs. We also inform the database management system that the Department column in the Employees table is a foreign key that references the Departments table. The database will then enforce referential integrity by ensuring that all of the values in the Departments column of the Employees table have corresponding entries in the Departments table.

Note that there is no uniqueness constraint for a foreign key. We may have more than one employee belonging to a single department. Similarly, there’s no requirement that an entry in the Departments table have any corresponding entry in the Employees table. It is possible that we’d have a department with no employees.

Superkey

Definition: A superkey is a combination of attributes that can be uniquely used to identify a database record. A table might have many superkeys. Candidate keys are a special subset of superkeys that do not have any extraneous (unrelated) information in them.

Examples: Imagine a table with the fields , , and . This table has many possible superkeys. Three of these are , and . Of those listed, only is a candidate key, as the others contain information not necessary to uniquely identify records.

Back to main directory:

DBMS

1. Introduction to Database
Advantages of Database Management System

2. Data Models
The Hierachical Data Model
The Network data Model
The Relational Data Model

3. Three-Schema Architecture of Database Systems

4 .Database System Architectures
Client Server Systems
Parallel Systems
Distributed Systems

5.Codd's Rules for Relational Database

6. Keys in DBMS

7.Concept of Normalisation
First Normal Form
Second Normal Form
Third Normal Form
Boyce-Codd Normal Form(BCNF)
Fourth Normal Form
Fifth Normal Form (Projection-Join Normal Form)

8. Transactions in DBMS

9. Steps to Design Database for a System

10. The Relational Algebra

Problem Statement- Query performs on a Project Management Database system.

Consider the following database:-

i)Employee(Fname,Lname,Ssn,Bdate,Address,Sex,Salary,Superssn,Dno)

ii)Department(Dname,Dnumber,Mgrssn)

iii)Project(Pname,Pnumber,Plocation,Dnumber)

iv)Workson(Empssn,Pnumber,Hours)

Given Queries:-

1.Find the name and address of the employees who work for the research department.

2.For every project located in ‘Stafford’, list the project number,the controlling department number

and the department manager’s last name and birth date.

3.Make a list of all project numbers for projects that involve an employee whose last name Smith,

either as a worker or as a manager of the department that controls the project.

4.Find all employees whose address is in Houston.

5.Show the resulting salaries if every employee working on the product x project is given a 10%

raise.

6.Retrieve a list of employees and the project they are working on, ordered by department and

within each department, ordered alphabetically by last name, first name.

7.Retrieve the names of the employees who have no departments.

8.List the names of manager who have atleast one department.

9.Retrieve the name of each employee who works on all the projects controlled by department

number 5.

10.For each project on which more than two employees work, retrieve the project number,the

project name, and the number of employees who work on the project.

11.For each department that has more than five employees, retrieve the department number and

the number of its employees who are making than $40,000.

12.Retrieve the names of all the employees who do not have supervisors.

Commands for table creations of the schemas in:-

i) SQL> create table Employee

2 ( fname varchar2(15) NOT NULL,

3 lname varchar2(15) NOT NULL,

4 ssn char(9) NOT NULL,

5 bdate date,

6 address varchar2(30),

7 sex char(1),

8 salary number(10,2),

9 superssn char(9),

10 dno number(1) NOT NULL,

11 PRIMARY KEY (ssn),

12 FOREIGN KEY (superssn) references Employee(ssn),

13 FOREIGN KEY (dno) references Department(dnumber) );

Table Created.