DataBase Management Systems(Module 2)

Download

MODULE 2

2.1 Basic Structure of relational model - The relational model for database management is a data model based on predicate logic and set theory. It was invented by Edgar Codd. The fundamental assumption of the relational model is that all data are represented as mathematical n-ary relations, an n-ary relation being a subset of the Cartesian product of n sets.

 1) Relation The fundamental organizational structure for data in the relational model is the relation. A relation is a two-dimensional table made up of rows and columns. Each relation also called a table, stores data about entities.

 2) Tuples - The rows in a relation are called tuples. They represent specific occurrences (or records) of an entity. Each row consists of a sequence of values, one for each column in the table. In addition, each row (or record) in a table must be unique. A tuple variable is a variable that stand for a tuple.

3) Attributes – The column in a relation is called attribute. The attributes represent characteristics of an entity.

4) Domain – For each attribute there is a set of permitted values called domain of that attribute. For all relations ‘r’, the domain of all attributes of ‘r’ should be atomic. A domain is said to be atomic if elements of the domain are considered to be indivisible units.

2.2 Database Schema – Logical design of the database is termed as database schema.    

1)      Database instance – Database instance is a snapshot of the data in a database at a given instant of time.

2)      Relation schema – The concept of relation schema corresponds to the programming notion of type definition. It can be considered as the definition of a domain of values. The database schema is the collection of relation schemas that define a database.

3)      Relation instance – The concept of a relation instance corresponds to the programming language notion of a value of a variable. For relation instance, we actually mean the “relation” itself.

2.3 Keys – A key is the relational means of specifying uniqueness. The keys applicable in relational model are primary key, candidate key and super key.

1.) Primary key - A primary key is a value that can be used to identify a unique          row in a table. Attributes are associated with it.

2.) Candidate key - A candidate key of a relation variable is a set of attributes of that relation variable such that (1) at all times it holds in the relation assigned to that variable that there are no two distinct tuples with the same values for these attributes and (2) there is not a proper subset for which (1) holds.

3.) Super key - A superkey is defined in the relational model as a set of attributes of a relation variable for which it holds that in all relations assigned to that variable there are no two distinct tuples that have the same values for the attributes in this set.

4.) Foreign key - A foreign key is a field or group of fields in a database record that point to a key field or group of fields forming a key of another database record in some (usually different) table. A relation schema, r1, derived from an E-R schema may include among its attributes the primary key of another relation schema, r2. This attribute is the foreign key from r1, referencing r2. The relation r1 is called the referencing relation of the foreign key dependency and r2 is called the referenced relation of r2.

2.4 Schema diagram – A database schema, along with primary key and foreign key dependencies, can be depicted pictorially by schema diagrams. Each relation in the database schema is represented as a box, with the attributes listed inside it and the relation name above it. If there are primary key attributes, a horizontal line crosses the box, with the primary key attributes listed above the line. Foreign key dependencies appear as arrows from the foreign key attributes of the referencing relation to the foreign key attributes of the referenced relation.

2.5 Relational algebra – The relational algebra is a procedural query language. (A query language is a language in which a user requests information from the database.) It consists of a set of operations that take one or two relations as input and produce a new relation as the result. The fundamental operations in relational algebra are select, project, union, set difference, Cartesian product and rename. There are several other operations namely, set intersection, natural join, division and assignment.

Fundamental operations

1.      Select operation - The select operation selects tuples that satisfy a given predicate. The Greek symbol ‘σ’ is used to denote selection. The predicate appears as a subscript to σ .  It is a unary operation.

          E.g. Consider the borrow relation and branch relation in the banking example:

Branch name	Loan#	Customer name	Amount
Downtown Round Hill Redwood	17 23 13	Jones Smith Hayes	1000 2000 1300

                                       Borrow relation

  

                                     Table 2.1

                                                Branch relation

Branch name	Branch city	Assets
Downtown Round Hill Redwood	Brooklyn Horseneck Palo Alto	9000000 21000000 17000000

                                    

                                                          

         

                                    Table 2.2

To select tuples (rows) of the borrow relation where the branch is “Redwood”, we would     write

                        s_{bname =”Redwood”} (borrow)

                          The new relation created as the result of this operation consists of  one tuple: (Redwood, 13, Hayes,1300). We allow comparisons using =, , <, , > and  in the selection predicate. We also allow the logical connectives (or) and (and). For example:

                        s_{bname = “Downtown” L amount > 800} (borrow)

            

2.      Project operation - The project operation is used to retrieve specific attributes/columns from a relation. It is denoted using Greek letter pi (∏). It is a unary operation.

For example, to obtain a relation showing customers and branches, but ignoring amount and loan#, we write

             ∏_{branchname,customername}(borrow)

 3) Union operation – The union operation is a binary operation since it involves 2 relations. It is used to retrieve tuples appearing in either or both the relations participating in the UNION. It is denoted as U. For a union operation RUS to be legal, we require that

• R and S must have the same number of attributes.
• The domains of the corresponding attributes must be the same.

4) Set difference – The set difference operation is a binary operation. Set difference is denoted by the minus sign (). It finds tuples that are in one relation, but not in another. Thus R-S results in a relation containing tuples that are in R but not in S.

5) Cartesian product – This is a binary operation involving 2 relations. It is used to obtain all possible combination of tuples from two relations. The cartesian product of two relations is denoted by a cross (), written R1 x R2 for relations R1 and R2. The result of R1 x R2 is a new relation with a tuple for each possible pairing of tuples from R1 and R2. In order to avoid ambiguity, the attribute names have attached to them the name of the relation from which they came. If no ambiguity will result, we drop the relation name. If R1 has n tuples, and R2 has m tuples, then R=R1 x R2 will have mxn tuples.

 6) Rename – The rename operation solves the problems that occur with naming when performing the cartesian product of a relation with itself.

Suppose we want to find the names of all the customers who live on the same street and in the same city as Smith.

Customer name	Customer street	Customer city
Jones Smith Hayes	Main North Main	Harrison Rye Harrison

                                      Table 2.3 Customer relation

We can get the street and city of Smith by writing

To find other customers with the same information, we need to reference the customer relation again:

where p is a selection predicate requiring street and ccity values to be equal.

So we have to distinguish between the two street values appearing in the Cartesian product, as both come from a single customer relation. For that, we use the rename operator, denoted by the Greek letter rho ().

We write

to get the relation r under the name of x.

If we use this to rename one of the two customer relations we are using, the ambiguities will disappear.

Additional operations

1. Set Intersection - Set intersection is denoted by , and returns a relation that contains tuples  that are in both of its argument relations. It does not add any power as

Eg: Consider the depositor and borrower relations. If we want to find all customers who have both a loan and an account, we have to take the intersection of two relations. It can be written as ∏ _{customer name}(borrower) ∩ ∏ _{customer name}(depositor).

2.      Natural join - Natural join is a dyadic operator that is written as RS where R and S are relations. The result of the natural join is the set of all combinations of tuples in R and S that are equal on their common attribute names.

Consider R and S to be sets of attributes. We denote attributes appearing in both relations by R ∩ S. We denote attributes in either or both relations by RUS. Consider two relations r(R) and s(S). The natural join of r and s, denoted by r  s is a relation on scheme R ∩ S. It is a projection onto R U S of a selection on r x s where the predicate requires r.a =s.a for each attribute a in R ∩ S.  Formally, r   s = Π _{R U S} (σ _{r.A1=s.A1 Λ r.A2=s.A2 Λ….r.An=s.An} (r x s)) where  R ∩ S = {Λ₁, Λ₂,…., Λ_n }

For an example consider the tables Employee and Dept and their natural join:

Employee
Name	EmpId	DeptName
Harry	3415	Finance
Sally	2241	Sales
Harriet	2202	Sales

      

Dept
DeptName	Manager
Sales	Harriet
Production	Charles
Finance	George

Table 2.4                                                           Table 2.5

EmployeeDept
Name	EmpId	DeptName	Manager
Harry	3415	Finance	George
Sally	2241	Sales	Harriet
George	3401	Finance	George
Harriet	2202	Sales	Harriet

                   Table 2.6

3. Equi-join - If we want to combine tuples from two relations where the combination condition is not simply the equality of shared attributes then it is convenient to have a more general form of join operator, which is the θ-join (or theta-join). The θ-join is a

dyadic operator that is written as or where a and b are attribute names, θ is a binary relation in the set {<, ≤, =, >, ≥}, v is a value constant, and R and S are relations. The result of this operation consists of all combinations of tuples in R and S that satisfy the relation θ. The result of the θ-join is defined only if the headers of S and R are disjoint, that is, do not contain a common attribute.

 4. Outer-join - Whereas the result of a join (or inner join) consists of tuples formed by combining matching tuples in the two operands, an outer join contains those tuples and additionally some tuples formed by extending an unmatched tuple in one of the operands by "fill" values for each of the attributes of the other operand. Three outer join operators are defined: left outer join, right outer join, and full outer join.

Left Outer join - The left outer join is written as R =X S where R and S are relations. The result of the left outer join is the set of all combinations of tuples in R and S that are equal on their common attribute names, in addition to tuples in R that have no matching tuples in S. For an example consider the tables Employee and Dept and their left outer join:

Dept
DeptName	Manager
Sales	Harriet
Production	Charles

Employee
Name	EmpId	DeptName
Harry	3415	Finance
Sally	2241	Sales
George	3401	Finance
Harriet	2202	Sales
Tim	1123	Executive

 In the resulting relation, tuples in S which have no common values in common attribute names with tuples in R take a null value, ω. Since there are no tuples in Dept with a DeptName of Finance or Executive, ωs occur in the resulting relation where tuples in DeptName have tuples of Finance or Executive.            

Table2.8

Table 2.9

The left outer join can be simulated using the natural join and set union as follows:

R =X S  =  R ∪ (RS)

Employee =X  Dept
Name	EmpId	DeptName	Manager
Harry	3415	Finance	ω
George	3401	Finance	ω
Tim	1123	Executive	ω
Sally	2241	Sales	Harriet
Harriet	2202	Sales	Harriet

Table 2.10

Right outer join - The right outer join behaves almost identically to the left outer join, with the exception that all the values from the "other" relation appear in the resulting relation. The right outer join is written as R X= S where R and S are relations. The result of the right outer join is the set of all combinations of tuples in R and S that are equal on their common attribute names, in addition to tuples in S that have no matching tuples in R. For an eg. consider the tables Employee and Dept and their right outer join:

In the resulting relation, tuples in R which have no common values in common attribute names with tuples in S take a null value, ω. Since there are no tuples in Employee with a DeptName of Production, ωs occur in the Name attribute of the resulting relation where tuples in DeptName had tuples of Production.

Employee
Name	EmpId	DeptName
Harry	3415	Finance
Sally	2241	Sales
George	3401	Finance
Harriet	2202	Sales
Tim	1123	Executive

Dept
DeptName	Manager
Sales	Harriet
Production	Charles

Table 2.11

                 Table2.12

Employee X=  Dept
Name	EmpId	DeptName	Manager
Sally	2241	Sales	Harriet
Harriet	2202	Sales	Harriet
ω	ω	Production	Charles

Table2.13

Full outer join - The outer join or full outer join in effect combines the results of the left and right outer joins. The full outer join is written as R =X= S where R and S are relations. The result of the full outer join is the set of all combinations of tuples in R and S that are equal on their common attribute names, in addition to tuples in S that have no matching tuples in R and tuples in R that have no matching tuples in S in their common attribute names.

For an example consider the tables Employee and Dept and their full outer join:

In the resulting relation, tuples in R which have no common values in common attribute names with tuples in S take a null value, ω. Tuples in S which have no common values in common attribute names with tuples in R, also take a null value, ω

Employee
Name	EmpId	DeptName
Harry	3415	Finance
Sally	2241	Sales
George	3401	Finance
Harriet	2202	Sales
Tim	1123	Executive

 

           

Dept
DeptName	Manager
Sales	Harriet
Production	Charles

Table 2.14                                       Table 2.15

          Table 2.16                                                                        Table2.17

Employee =X=  Dept
Name	EmpId	DeptName	Manager
Harry	3415	Finance	ω
Sally	2241	Sales	Harriet
George	3401	Finance	ω
Harriet	2202	Sales	Harriet
Tim	1123	Executive	ω
ω	ω	Production	Charles

Completed
Student	Task
Fred Fred Fred Eugene Eugene Sara Sara	Database1 Database2 Compiler1 Database1 Compiler1 Database1 Database2

DBProject

Task

Database1 Database2

5. Division operation - The division is a binary operation that is written as R ÷ S. The result consists of the restrictions of tuples in R to the attribute names unique to R, i.e., in the header of R but not in the header of S, for which it holds that all their combinations with tuples in S are present in R. For an example see the tables Completed, DBProject and their division:  Table 2.19                

Completed ÷ DBProject

Student

Fred Sara

         

                                    

  Table 2.18

                                

Let  r(R) and s(S) be relations. Let . The relation   r ÷ s is a relation on scheme R – S. A tuple t is in r ÷ s if for every tuple t_s in  s there is a tuple t_r in r satisfying both of the following:

These conditions say that the  portion of a tuple  is in  if and only if there are tuples with the  portion and the  portion in  for every value of the  portion in relation .

6. Assignment operation - Sometimes it is useful to be able to write a relational algebra expression  in     parts using a temporary relation variable. The assignment operation, denoted , works like assignment in a programming language.

     We could rewrite our division definition as

No extra relation is added to the database, but the relation variable created can be used in subsequent expressions. Assignment to a permanent relation would constitute a modification to the database.

2.6 Tuple Relational Calculus - The tuple calculus is a calculus that was introduced by Edgar F. Codd as part of the relational model in order to give a declarative database query language for this data model. The tuple relational calculus is a nonprocedural language. (The relational algebra was procedural.) We must provide a formal description of the information desired.

A query in the tuple relational calculus is expressed as { t / P(t) } i.e. the set of tuples t for  which predicate P is true. We also use the notation

• t[a] to indicate the value of tuple  on attribute.
• t є r to show that tuple t is in relation r.

Example Queries

For example, to find the branch-name, loan number, customer name and amount for loans over $1200:

This gives us all attributes, but suppose we only want the customer names. (We would use project in the algebra.) We need to write an expression for a relation on scheme (cname).

In English, we may read this equation as “the set of all tuples t such that there exists a tuple s in the relation borrow for which the values of  t and s for the cname attribute are equal, and the value of  s for the amount attribute is greater than 1200.”

The notation  means that “there exists a tuple t  in relation r such that predicate Q(t)  is true''. Consider another example: Find all customers having a loan from the SFU branch, and the cities in which they live:

In English, we might read this as “the set of all (cname,ccity) tuples for which cname is a borrower at the SFU branch, and ccity is the city of cname”. Tuple variable s ensures that the customer is a borrower at the SFU branch. Tuple variable u is restricted to pertain to the same customer as , and also ensures that ccity is the city of the customer.

The logical connectives (AND) and (OR) are allowed, as well as (negation). We also use the existential quantifier and the universal quantifier .

Formal Definition

A tuple relational calculus expression is of the form { t | P(t) } where P is a formula. Several tuple variables may appear in a formula.

Tuple variable : A tuple variable is said to be a free variable unless it is quantified by a or a . If it is quantified by a  or a , it is said to be bound variable.

Formula : A formula is built of atoms. An atom is one of the following forms:

o    s є r , where s is a tuple variable, and r is a relation ( is not allowed).

o    s[x] θ u[y] where s and u are tuple variables, and x and y are attributes, and θ is a comparison operator ().

o    s[x] θ c, where c is a constant in the domain of attribute x.

Formulae are built up from atoms using the following rules:

o    An atom is a formula.

o    If P is a formula, then so are and (P).

o    If P₁and P₂ are formulae, then so are P₁  P_2,  ,  and .

o    If  P(s) is a formula containing a free tuple variable s, then

are also formulae.

Important equivalences:

o   

o   

o   

Safety of Expressions

A tuple relational calculus expression may generate an infinite expression, e.g.

There are infinite number of tuples that are not in borrow. Most of these tuples contain values that do not appear in the database. So we have to restrict the relational calculus.

Safe Tuple Expressions

The domain of a formula , denoted dom(), is the set of all values referenced in P. We may say an expression { t / P(t) }is safe if all values that appear in the result are values from dom(). A safe expression yields a finite number of tuples as its result. Otherwise, it is called unsafe. The tuple relational calculus restricted to safe expressions is equivalent in expressive power to the relational algebra.

2.7 Domain Relational Calculus - The domain relational calculus (DRC) is a calculus that was introduced by Edgar F. Codd as a declarative database query language for the relational data model. This language uses the same operators as tuple calculus; Logical operators Λ(and), V(or) and ¬ (not). The existential quantifier (∃) and the universal quantifier (∀) can be used to bind the variables.

Formal Definition

An expression is of the form

where the  represent domain variables, and  is a formula.

An atom in the domain relational calculus is of the following forms :

• 1

, x₂, …., x_n> є r  where r is a relation on n attributes, and x_i, 1 ≤ i ≤ n, are domain variables or constants.

x θ y , where x and y are domain variables, and θ is a comparison operator.

x θ c , where c is a constant.

Formulae are built up from atoms using the following rules:

• An atom is a formula.
• If  P is a formula, then so are and (P).
• If P₁and P₂ are formulae, then so are P₁  P_2,  ,  and .
• If  P(s) is a formula containing a free tuple variable s, then

are also formulae.

Example Queries

Find branch name, loan number, customer name and amount for loans of over $1200.

Find all customers who have a loan for an amount > than $1200.

Find all customers having a loan from the SFU branch, and the city in which they live.

Find all customers having a loan, an account or both at the SFU branch.

Find all customers who have an account at all branches located in Brooklyn.

Safety of Expressions

We say that an expression

{ < x1, x2,…..,xn > | P (x1, x2,….xn)} is safe if all of the following hold:

1. All values that appear in tuples of the expression are values from dom(P).

2. For every  “there exists” sub formula of the form  Эx (P1(x)), the subformula is true if and only if there is a value x in dom(P1) such that P1(x) is true.

3. For every “ for all” subformula of the form Vx (P1(x)), the subformula is true if and only if P1(x) is true for all values of x.

                    An expression such as { | ¬( є loan)} is unsafe because it allows values in the result that are not in the domain of the expression.

All three of the following are equivalent:

• The relational algebra.
• The tuple relational calculus restricted to safe expressions.
• The domain relational calculus restricted to safe expressions.

2.8 SQL – Sql has become the standard relational database language. It has several parts:

o   Data definition language (DDL) - provides commands to

§  Define relation schemes.

§  Delete relations.

§  Create indices.

§  Modify schemes.

o   Interactive data manipulation language (DML) - a query language based on both relational algebra and tuple relational calculus, plus commands to insert, delete and modify tuples.

o   Embedded data manipulation language - for use within programming languages like C, PL/1, Cobol, Pascal, etc.

o   View Definition - commands for defining views

o   Authorization - specifying access rights to relations and views.

o   Integrity - a limited form of integrity checking.

o   Transaction control - specifying beginning and end of transactions.

Basic Structure

Basic structure of an SQL expression consists of select, from and where clauses.

A typical SQL query has the form :

                                             select A₁, A₂,…….,A_n

                                             from r₁, r₂,….,r_n

                                             where P

Each A_i  represents an attribute, and each r_i a relation. P is a predicate. This query is equivalent to the algebra expression.

                                      Π _{A1, A2,….,An}(σ _p (r1 x r2 x ………x rm))

If the where clause is omitted, the predicate P is true. The list of attributes can be replaced with a * to select all. The result of an SQL query is a relation.

The select clause - corresponds to the projection operation of the relational algebra. It is used to list the attributes desired in the result of a query. If we want to remove duplicates in a selection procedure, we use the keyword distinct after select. The keyword all is used to specify explicitly that duplicates are not removed. select * means select all the attributes. Select clause can also contain arithmetic expressions involving operators (+, -, *, / ) and operating on constants or attributes of  tuples.

Eg: 1.  select branch-name

            from loan

1.  select branch-name, loan-number, amount*100

from loan

The where clause - corresponds to selection predicate in relational algebra. It consists of a predicate involving attributes of the relations that appear in the from clause. SQL uses the logical connectives and, or and not - rather than mathematical symbols Λ, V and ¬ in the where clause. The operands of the logical connectives can be expressions involving the comparison operators <, >, ≤, ≥, = and <>. SQL includes a between comparison operator to simplify where clauses that specify that a value be less than or equal to some value or greater than or equal to some other value.

Eg: 1. select loan-number

          from loan

          where amount between 90000 and 100000

The from clause - corresponds to Cartesian product of the relational algebra. It lists the relations to be scanned in the evaluation of the expression.

The rename operation – SQL provides a mechanism for renaming both relations and attributes. It uses the as clause, taking the form: old-name as new-name.

String operations - The most commonly used operation on strings is pattern matching using the operator like. We describe patterns using two special characters:

·         Percent (%) – The % character matches any substring.

·         Underscore ( _ ) – The _ character matches any character.

Patterns are case-sensitive. The keyword escape is used to define the escape character. We can use not like for string mismatching.

Ordering the display of tuples - SQL allows the user to control the order in which tuples are displayed.

• order by makes tuples appear in sorted order (ascending order by default).
• desc specifies descending order.
• asc specifies ascending order.

Set operations - SQL has the set operations union, intersect and except. union eliminates duplicates, being a set operation. If we want to retain duplicates, we may use union all, similarly for intersect and except.

Not all implementations of SQL have these set operations. except in SQL-92 is called minus in SQL-86.

Aggregate functions - In SQL we can compute functions on groups of tuples using the group by clause. Attributes given are used to form groups with the same values. SQL can then compute

• average value -- avg
• minimum value -- min
• maximum value -- max
• total sum of values -- sum
• number in group -- count

These are called aggregate functions. They return a single value. having-clause is used to state conditions that applies to groups rather than to tuples. Predicates in the having clause are applied after the formation of groups. If a where clause and a having clause appear in the same query, the where clause predicate is applied first. Tuples satisfying where clause are placed into groups by the group by clause. The having clause is applied to each group. Groups satisfying the having clause are used by the select clause to generate the result tuples. If no having clause is present, the tuples satisfying the where clause are treated as a single group.

Null values – The keyword null is used to test for a null value(absence of information about the value of an attribute).

2.9Views in SQL - A view in SQL is defined using the create view command:

                                              create view v as

where is any legal query expression. The view created is given the  name v. To create a view all-customer of all branches and their customers:

create view all-customer as

(select bname, cname

from depositor, account

where depositor.account# = account.account#)

         union

    (select bname, cname

    from borrower, loan

    where borrower.loan# = loan.loan#)

Having defined a view, we can now use it to refer to the virtual relation it creates. View names can appear anywhere a relation name can.

2.10 Data manipulations

Insert – It is used to insert a single tuple to a relation. To insert data into a relation, we either specify a tuple, or write a query whose result is the set of tuples to be inserted. Attribute values for inserted tuples must be members of the attribute's domain.

Eg: To insert a tuple for Smith who has $1200 in account A-9372 at the SFU branch.

insert into account  values (“SFU”, “A-9372”', 1200)

It is important that we evaluate the select statement fully before carrying out any insertion. If some insertions were carried out even as the select statement were being evaluated, the insertion might insert an infinite number of tuples. Evaluating the select statement completely before performing insertions avoids such problems. It is possible for inserted tuples to be given values on only some attributes of the schema. The remaining attributes are assigned a null value denoted by null. We can prohibit the insertion of null values using the SQL DDL.

Delete – The delete command removes tuples from a relation. Deletion is expressed in much the same way as a query. Instead of displaying, the selected tuples are removed from the database. We can only delete whole tuples. A deletion in SQL is of the form  delete from r  where P. Tuples in r for which P is true are deleted. If the where clause is omitted, all tuples are deleted. We may only delete tuples from one relation at a time, but we may reference any number of relations in a select-from-where clause embedded in the where clause of a delete. However, if the delete request contains an embedded select that references the relation from which tuples are to be deleted, ambiguities may result.

Update - Updating allows us to change some values in a tuple without necessarily changing all. where clause of update statement may contain any construct legal in a where clause of a select statement (including nesting). A nested select within an update may reference the relation that is being updated. As before, all tuples in the relation are first tested to see whether they should be updated, and the updates are carried out afterwards.

Update of a view - The view update exists also in SQL. An example will illustrate: Consider a clerk who needs to see all information in the loan relation except amount. Let the view branch-loan be given to the clerk:

 create view branch-loan as select bname, loan# from loan

Since SQL allows a view name to appear anywhere a relation name may appear, the clerk can write: insert into branch-loan values (“SFU”, “L-307”). This insertion is represented by an insertion into the actual relation loan, from which the view is constructed. However, we have no value for amount. This insertion results in (“SFU'', “L-307”, null) being inserted into the loan relation.

Download