BCS304

Database Management System

chintan Patel

chintan.patel@rru.ac.in

Relational Model, Relational Algebra, SQL

• Relational Model
• Database schema and Keys
• Relational Query Language
• Relational Algebra
• SQL

​

In this Unit

Example of a Instructor  Relation

Tuples (or rows)

Attributes (or columns)

Domain of the attribute : Set of Allowed Values

• Example
• Name (Attribute) : Character (Domain)
• ID : Numeric
• Salary : Numeric

​

NULL Attribute: value is “unknown”

• “null” value is an actual value, not as a zero value, a blank, or an empty string.
• Some attributes should be allowed to contain null values, other attributes should not contain null values.
• Example : For the EMPLOYEE entity, you might not want to allow the attribute EMPLOYEE_LAST_NAME to contain a null value.

• Attribute values : Required to be atomic; that is, indivisible
• Example :
• Full name (Non atomic)
• First Name: Atomic

• Order of tuples is irrelevant (tuples may be stored in an arbitrary order)

Database Schema

​

• Database schema : Logical structure of the database.
• Database instance : Snapshot of the data in the database at a given instant in time. 

​

• Example:
• schema:   instructor (ID, name, dept_name, salary)
• Instance:

Keys in Relational Model

1. Candidate Keys
2. Super Key
3. Primary Key
4. Alternate Keys
5. Foreign Keys

Discussion

• Let K ⊆ R
• K is a super key of R if values for K are sufficient to identify a unique tuple of each possible relation r(R) 
• Example:  {ID} and {ID,name} are both super keys of instructor.

• Super key K is a candidate key if K is minimal. Example:  {ID} is a candidate key for Instructor

• One of the candidate keys is selected to be the primary key.

Candidate Key: Minimal set of attributes that can uniquely identify a tuple

​

For Example, ID in INSTRUCTOR relation. 

• Minimal super key.
• Super key with no repeated data.
• Must contain unique values.
• Must NOT contain NULL values.
• Table must have at least a single candidate key.
• Relation : Multiple candidate keys possible, but only one primary key (the primary key cannot have a NULL value, so the candidate key with NULL value can’t be the primary key).
• Example: ID, Phone No, and University_Email are candidate keys.
• Adding zero or more attributes to the candidate key generates the super key.
• The candidate key can be simple (having only one attribute) or composite as well. For Example, {STUD_NO, COURSE_NO} is a composite candidate key for relation STUDENT_COURSE.

​

Primary Key : ONLY ONE KEY CHOOSEN FROM SET OF CANDIDATE KEYS.

Alternate Keys : NOT CHOOSEN SET OF CANDIDATE KEYS:

Example: ID, Phone No, and University_Email are candidate keys but ID can be chosen as the primary key

ANY RELATION CAN/MUST HAVE ONLY ONE PRIMARY KEY

Primary keys are not necessarily to be a single column; more than one  the column can also be a primary key for a table.

Foreign Key : Column that creates a relationship between two tables.

• Maintain data integrity and allow navigation between two different instances of an entity.
• The relation which is being referenced is called referenced relation and the corresponding attribute is called referenced attribute.
• The relation which refers to the referenced relation is called referencing relation and the corresponding attribute is called referencing attribute.
• The referenced attribute of the referenced relation should be the primary key to it.
• For Example, STUD_NO in STUDENT_COURSE is a foreign key to STUD_NO in STUDENT relation. 
• Foreign Key can be NULL as well as may contain duplicate tuples i.e. it need not follow uniqueness constraint.
• A Relation can have more than one foreign keys
• Example : STUD_NO in STUDENT_COURSE relation not necessary be unique. However, the STUD_NO in STUDENT relation is a primary key and it needs to be always unique, and it cannot be null. 

Example: Primary key and Foreign Keys

Quiz: Decide Primary key and Foreign Keys

University Database

Quiz: Decide Primary key and Foreign Keys

Quiz : Keys

Example-1 : Let a Relation R have attributes {a1,a2,a3} and a1 is the candidate key. Then how many super keys are possible? 

Here, any superset of a1 is the super key. �Super keys are = {a1, a1 a2, a1 a3, a1 a2 a3} �Thus we see that 4 Super keys are possible in this case. 

In general, if we have ‘N’ attributes with one candidate key then the number of possible superkeys is 2^{(N – 1)}. 

Example-2 : Let a Relation R have attributes {a1, a2, a3,…,an}. Find Maximum Super key of R. 

Maximum Super keys = 2ⁿ – 1. �If each attribute of relation is candidate key. 

Example-3: Let a Relation R have attributes {a1, a2, a3,…, an} and the candidate key is “a1 a2 a3” then the possible number of super keys? 

Following the above formula, we have 3 attributes instead of one. So, here the number of possible super keys is 2^(N-3).

• Procedural Language:
• Program code is written as a sequence of instructions.
• User has to specify “what to do” and “how to do” (step by step procedure).
• Instructions are executed in the sequential order to solve specific problems.

Examples of Procedural languages: FORTRAN, COBOL, ALGOL, BASIC, C and Pascal.

• Non-Procedural Language (a.k.a. applicative or functional language):
• User has to specify only “what to do” and NOT “how to do”.

Examples of Non-Procedural languages: SQL, PROLOG, LISP.

Relational Query Languages

Relational algebra

(Procedural Language)

Tuple relational calculus

Domain relational calculus

Relational Algebra

• A  procedural language consisting  of a set of operations that take one or two relations as input and produce a new relation as their result. 
• Six basic operators
• select: σ
• project: ∏
• union: ∪
• set difference: – 
• Cartesian product: x
• rename: ρ

​

• The  select operation selects tuples that satisfy a given predicate.
• Notation:  σ _p(r)
• p is called the selection predicate
• Example: select those tuples of the instructor relation where the instructor is in the “Physics” department.
• Query�     �Result

Select Operation

σ _{dept_name=“Physics”} (instructor)

Select Operation (Cont.)

• Allows comparisons using 

                     =, ≠, >, ≥. <. ≤

​

• Combine multiple predicate into a larger predicate by using the connectives:

                   ∧ (and), ∨ (or), ¬ (not)

​

• Example: Find the instructors in Physics with a salary greater $90,000, we write:

�          σ _{dept_name=“Physics”} ∧ _salary > 90,000 (instructor)

​

• Also includes comparisons between two attributes. 
• Example, find all departments whose name is the same as their building name:

σ _{dept_name=building}  (department)

• A unary operation that returns its argument relation, with certain attributes left out.  
• Notation:

                  ∏ _{A1,A2,A3 ….Ak}  (r)   

    where A₁, A₂ are attribute names and r is a relation name.

• The result is defined as the relation of k columns obtained by erasing the columns that are not listed
• Duplicate rows removed from result, since relations are sets

Project Operation

• Example: Eliminate the dept_name attribute of instructor
• Query:�            ∏_{ID, name, salary} (instructor) 

• Find the names of all instructors in the Physics department.

�             ∏_name(σ _{dept_name =“Physics”}  (instructor))

​

Cartesian-Product Operation

• Denoted by X  allows us to combine information from any two relations.  
• Example: the Cartesian product of the relations instructor and teaches is written  as:

                instructor  X  teaches

​

• Since the instructor ID appears in both relations we distinguish between these attribute by attaching to the attribute the name of the relation from which the attribute originally came.
• instructor.ID
• teaches.ID

��

X

=

Most of the resulting rows have information about instructors who did NOT teach a particular course. 

• To get only those tuples of  “instructor  X  teaches “ that pertain to instructors and the courses that they taught,

​

And Write relational algebra query

σ _{instructor.id =  teaches.id}  (instructor  x teaches ))

Select

operation

Cartesian Product

operation

Select

operation

Cartesian Product

operation

Theta Join

operation

=

=

Union Operation

• The union operation allows us to combine two relations 
• Notation:  r  ∪ s
• For r ∪ s to be valid.

    1.  r, s must have the same arity (same number of attributes)

    2.  The attribute domains must be compatible (example: 2^nd column �        of r deals with the same type of values as does the 2^nd �    column of s)

• Example: to find all courses taught in the Fall 2017 semester, or in the Spring 2018 semester, or in both�  ∏_{course_id} (σ _{semester=“Fall”  Λ year=2017} (section))  ∪  �  ∏_{course_id} (σ _{semester=“Spring”  Λ year=2018} (section))

Set Intersection Operation

• The  set-intersection  operation  allows us to find tuples that are in both the input relations.
• Notation: r ∩ s
• Assume: 
• r, s have the same arity 
• attributes of r and s are compatible
• Example: Find the set of all courses taught in both the Fall 2017 and the Spring 2018 semesters.

           ∏_{course_id} (σ _{semester=“Fall”  Λ year=2017} (section)) ∩ �  ∏_{course_id} (σ _{semester=“Spring”  Λ year=2018} (section))

• �Result

�

Set Difference Operation

• The set-difference operation allows us to find tuples that are in one relation but are not in another. 
• Notation r – s
• Set differences must be taken between compatible relations.
• r and s must have the same arity
• attribute domains of r and s must be compatible
• Example: to find all courses taught in the Fall 2017 semester, but not in the Spring 2018 semester�  ∏_{course_id} (σ _{semester=“Fall”  Λ year=2017} (section))  −  �  ∏_{course_id} (σ _{semester=“Spring”  Λ year=2018} (section))

����

Assignment Operation

• It is convenient at times to write a relational-algebra expression by assigning parts of it to temporary relation variables.  
• The assignment  operation is  denoted by ← and works like assignment in a programming language.
• Example: Find all instructor in the “Physics” and Music department.��         Physics ← σ _{dept_name=“Physics”} (instructor)

       Music ← σ _{dept_name=“Music”} (instructor)

       Physics ∪ Music

�

Rename Operation

• The results of relational-algebra expressions do not have a name that we can use to refer to them.  The  rename operator,  ρ ,  is provided  for that purpose
• The expression:

                  ρ_x (E)

      returns the result of expression E under the name x

• Another form of the rename operation:

                 ρ_{x(A1,A2, .. An)} (E)

�

Equivalent Queries

​

• There is more than one way to write a query in relational algebra. 
• Example:  Find information about courses taught by instructors in the Physics department with salary greater than 90,000
• Query 1

     σ _{dept_name=“Physics”} ∧ _{salary > 90,000} (instructor)

​

• Query 2

     σ _{dept_name=“Physics”} (σ _{salary > 90.000} (instructor))

​

• The two queries are not identical; they are, however, equivalent -- they give the same result on any database.

��

Practice : Assignment 1 [20 Marks]

�Schema :

• College(CNAME, state, enrollment_no)
• Student(SID, SNAME, GPA, SizeHS)
• Apply (SID, CNAME, major, decision)

​

​

• Find students details whose GPA is more than 3.7 [2 Marks]
• Find student details whose GPA is more than 3.4 and HS Size is less than 1000. [2 Marks]
• Find applications details came for “stanford” college name and “cs” as a major subject. [2 Marks]
• Find only names and ID of the students who are having GPA more than 3.5. [2 Marks]
• Find Names and GPA of students with HS size more than 1000 and who applied to CS and were get rejected. [2 Marks]
• Names and GPA of the students with HS Size more than 1000 who applied to CS at colllege with enrolment more than 20000 and were rejected. [2 Marks]
• Find IDs of student who did not applied anywhere. [2 Marks]
• IDs and Names of students who didn’t applied anywhere. [2 Marks]
• Assume you have only one column (no) in table (r) with numbers. Write a regular expression to find maximum among this numbers. [4 Marks]

Gracing Assignment - 1

�1. Scheme:

​

​

​

​

​

​

​

​

​

​

​

• Find the name of each employees who live in city “Miami”
• Find the name of employees whose salary is greater than $10000.
• Find the name of each employees who lives in city “Miami” and whose salary is greater than $10000.
• Find the ID and name of each employees who does not work for “Bigbank”
• Find the ID and name of each employee who earns at least as much as every employee in the database. 

[GATE 2000]

​

​

​

�1. Given the relations employee (name, salary, deptno), and�    department (deptno, deptname, address)

• Which of the following queries cannot be expressed using the basic relational algebra operations (σ,π,×,⋈,∪,∩,−)(σ,π,×,⋈,∪,∩,−)? 
• Department address of every employees.
• Employees whose name is the same as department name
• The sum of all employee’s salary
• All employees of given department.

��

[GATE 2003]

�2. Consider the following SQL query select distinct al, a2,........., an    

     from r1, r2,........, rm where P 

       For an arbitrary predicate P, this query is equivalent to which of the following       

     relational algebra expressions ?

�������Answer : A

Option B is doing natural join meaning only those tuples having same value for common attribute(s) in both the relations are selected for output.

�

[GATE CSE 2006]

​

​

• Consider the relations r₁(P, Q, R) and r₂(R, S, T) with primary keys P and R respectively. The relation r₁ contains 2000 tuples and r₂ contains 2500 tuples. The maximum size of the join r1⋈r2 is
• 2000
• 2500
• 4000
• 5000

​

​

�Answer = 2000

[GATE CSE 2006]

​

​

• Which of the following relational query languages have the same expressive power?
1. Relational algebra
2. Tuple relational calculus restricted to safe expressions
3. Domain relational calculus restricted to safe expressions

�(A) II and III only�(B) I and II only�(C) I and III only�(D) I, II and III

​

�Answer : D

Also Refer :

https://www.cs.purdue.edu/homes/bb/cs448_Fall2017/lpdf/Chapter08.pdf