Database - Discussions

San77

Chapter08_accessible.pptx

Home >Computer Science homework help >Database - Discussions

Fundamentals of Database Systems

Seventh Edition

Chapter 8

The Relational Algebra and

The Relational Calculus

(plus Q B E- Appendix C)

Slides in this presentation contain hyperlinks. JAWS users should be able to get a list of links by using INSERT+F7

If this PowerPoint presentation contains mathematical equations, you may need to check that your computer has the following installed:

1) MathType Plugin

2) Math Player (free versions available)

3) NVDA Reader (free versions available)

Chapter Outline

8.1 Relational Algebra

Unary Relational Operations

Relational Algebra Operations From Set Theory

Binary Relational Operations

Additional Relational Operations

Examples of Queries in Relational Algebra

8.2 Relational Calculus

Tuple Relational Calculus

Domain Relational Calculus

8.3 Example Database Application (COMPANY)

8.4 Overview of the Q.B E language (appendix D)

Relational Algebra Overview (1 of 4)

Relational algebra is the basic set of operations for the relational model

These operations enable a user to specify basic retrieval requests (or queries)

The result of an operation is a new relation, which may have been formed from one or more input relations

This property makes the algebra “closed” (all objects in relational algebra are relations)

Relational Algebra Overview (2 of 4)

The algebra operations thus produce new relations

These can be further manipulated using operations of the same algebra

A sequence of relational algebra operations forms a relational algebra expression

The result of a relational algebra expression is also a relation that represents the result of a database query (or retrieval request)

Brief History of Origins of Algebra

Muhammad ibn Musa al-Khwarizmi (800-847 C E) – from Morocco wrote a book titled al-jabr about arithmetic of variables

Book was translated into Latin.

Its title (al-jabr) gave Algebra its name.

Al-Khwarizmi called variables “shay”

“Shay” is Arabic for “thing”.

Spanish transliterated “shay” as “xay” (“x” was “sh” in Spain).

In time this word was abbreviated as x.

Where does the word Algorithm come from?

Algorithm originates from “al-Khwarizmi"

Reference: P B S (http://www.pbs.org/empires/islam/innoalgebra.html)

Relational Algebra Overview (3 of 4)

Relational Algebra consists of several groups of operations

Unary Relational Operations

SELECT

PROJECT

RENAME

Relational Algebra Operations From Set Theory

DIFFERENCE (or MINUS, − )

CARTESIAN PRODUCT ( x )

Binary Relational Operations

JOIN (several variations of JOIN exist)

DIVISIONs

Relational Algebra Overview (4 of 4)

Additional Relational Operations

OUTER JOINS, OUTER UNION

AGGREGATE FUNCTIONS (These compute summary of information: for example, SUM, COUNT, AVG, MIN, MAX)

Database State for COMPANY

All examples discussed below refer to the Company database shown here.

Figure 5.7 Referential integrity constraints displayed on the COMPANY relational database schema.

Unary Relational Operations: SELECT (1 of 4)

The SELECT operation (denoted by σ (sigma)) is used to select a subset of the tuples from a relation based on a selection condition.

The selection condition acts as a filter

Keeps only those tuples that satisfy the qualifying condition

Tuples satisfying the condition are selected whereas the other tuples are discarded (filtered out)

Examples:

Select the EMPLOYEE tuples whose department number is 4:

Select the employee tuples whose salary is greater than $30,000:

Unary Relational Operations: SELECT (2 of 4)

In general, the select operation is denoted by

The symbol σ (sigma) is used to denote the select operator

The selection condition is a Boolean (conditional) expression specified on the attributes of relation R

Tuples that make the condition true are selected

appear in the result of the operation

Tuples that make the condition false are filtered out

discarded from the result of the operation

Unary Relational Operations: SELECT (3 of 4)

SELECT Operation Properties

The SELECT operation

produces a

relation S that has the same schema (same attributes) as R

SELECT σ is commutative:

Because of commutativity property, a cascade (sequence) of SELECT operations may be applied in any order:

Unary Relational Operations: SELECT (4 of 4)

A cascade of SELECT operations may be replaced by a single selection with a conjunction of all the conditions:

The number of tuples in the result of a SELECT is less than (or equal to) the number of tuples in the input relation R

The Following Query Results Refer to This Database State

Figure 5.6 One possible database state for the COMPANY relational database schema.

Unary Relational Operations: Project (1 of 3)

PROJECT Operation is denoted by π (pi)

This operation keeps certain columns (attributes) from a relation and discards the other columns.

PROJECT creates a vertical partitioning

The list of specified columns (attributes) is kept in each tuple

The other attributes in each tuple are discarded

Example: To list each employee’s first and last name and salary, the following is used:

Unary Relational Operations: Project (2 of 3)

The general form of the project operation is:

π (pi) is the symbol used to represent the project operation

<attribute list> is the desired list of attributes from relation R.

The project operation removes any duplicate tuples

This is because the result of the project operation must be a set of tuples

Mathematical sets do not allow duplicate elements.

Unary Relational Operations: Project (3 of 3)

PROJECT Operation Properties

The number of tuples in the result of projection

is always less or equal to the number of

tuples in R

If the list of attributes includes a key of R, then the number of tuples in the result of PROJECT is equal to the number of tuples in R

PROJECT is not commutative

Examples of Applying Select and Project Operations

Figure 8.1 Results of SELECT and PROJECT operations.

Relational Algebra Expressions

We may want to apply several relational algebra operations one after the other

Either we can write the operations as a single relational algebra expression by nesting the operations, or

We can apply one operation at a time and create intermediate result relations.

In the latter case, we must give names to the relations that hold the intermediate results.

Single Expression Versus Sequence of Relational Operations (Example)

To retrieve the first name, last name, and salary of all employees who work in department number 5, we must apply a select and a project operation

We can write a single relational algebra expression as follows:

OR We can explicitly show the sequence of operations, giving a name to each intermediate relation:

Unary Relational Operations: RENAME (1 of 3)

The RENAME operator is denoted by

In some cases, we may want to rename the attributes of a relation or the relation name or both

Useful when a query requires multiple operations

Necessary in some cases (see JOIN operation later)

Unary Relational Operations: RENAME (2 of 3)

The general RENAME operation

can be expressed by any of the following forms:

the relation name to S, and

the column (attribute) names to

the relation name only to S

the column (attribute) names only to

Unary Relational Operations: RENAME (3 of 3)

For convenience, we also use a shorthand for renaming attributes in an intermediate relation:

If we write:

RESULT will have the same attribute names as DEP5_EMPS (same attributes as EMPLOYEE)

If we write:

RESULT (F, M, L, S, B, A, SX, SAL, SU, DNO) ←

The 10 attributes of DEP5_EMPS are renamed to F, M, L, S, B, A, SX, SAL, SU, DNO, respectively

Note: ← the symbol is an assignment operator

Example of Applying Multiple Operations and RENAME

Figure 8.2 Results of a sequence of operations.

(a)

(b) Using intermediate relations and renaming of attributes

Relational Algebra Operations from Set Theory: UNION (1 of 2)

UNION Operation

Binary operation, denoted by 

The result of

, is a relation that includes all tuples that are either in R or in S or in both R and S

Duplicate tuples are eliminated

The two operand relations R and S must be “type compatible” (or UNION compatible)

R and S must have same number of attributes

Each pair of corresponding attributes must be type compatible (have same or compatible domains)

Relational Algebra Operations from Set Theory: Union (2 of 2)

Example:

To retrieve the social security numbers of all employees who either work in department 5 (RESULT1 below) or directly supervise an employee who works in department 5 (RESULT2 below)

We can use the UNION operation as follows:

The union operation produces the tuples that are in either RESULT1 or RESULT2 or both

Figure 8.3 Result of the Union Operation RESULT ← RESULT1 union symbol RESULT2

Relational Algebra Operations from Set Theory

Type Compatibility of operands is required for the binary set operation

see next slides)

are type compatible if:

they have the same number of attributes, and

the domains of corresponding attributes are type compatible

The resulting relation for

has the same attribute names as the first operand relation R1 (by convention)

Relational Algebra Operations from Set Theory: INTERSECTION

INTERSECTION is denoted by

The result of the operation

, is a relation that includes all tuples that are in both R and S

The attribute names in the result will be the same as the attribute names in R

The two operand relations R and S must be “type compatible”

Relational Algebra Operations from Set Theory: SET DIFFERENCE

SET DIFFERENCE (also called MINUS or EXCEPT) is denoted by −

The result of R − S, is a relation that includes all tuples that are in R but not in S

The attribute names in the result will be the same as the attribute names in R

The two operand relations R and S must be “type compatible”

Example to Illustrate the Result of UNION, INTERSECT, and DIFFERENCE

Figure 8.4 The set operations UNION, INTERSECTION, and MINUS. (a) Two union-compatible relations. (b)

Some Properties of UNION, INTERSECT, and DIFFERENCE

Notice that both union and intersection are commutative operations; that is

Both union and intersection can be treated as n-ary operations applicable to any number of relations as both are associative operations; that is

The minus operation is not commutative; that is, in general

Relational Algebra Operations from Set Theory: CARTESIAN PRODUCT (1 of 3)

CARTESIAN (or CROSS) PRODUCT Operation

This operation is used to combine tuples from two relations in a combinatorial fashion.

Denoted by

Result is a relation Q with degree n + m attributes:

The resulting relation state has one tuple for each combination of tuples—one from R and one from S.

Hence, if R has nR tuples

and S has nS tuples, then R × S will have nR * nS tuples.

The two operands do NOT have to be "type compatible”

Relational Algebra Operations from Set Theory: CARTESIAN PRODUCT (2 of 3)

Generally, CROSS PRODUCT is not a meaningful operation

Can become meaningful when followed by other operations

Example (not meaningful):

EMP_DEPENDENTS will contain every combination of EMPNAMES and DEPENDENT

whether or not they are actually related

Relational Algebra Operations from Set Theory: CARTESIAN PRODUCT (3 of 3)

To keep only combinations where the DEPENDENT is related to the EMPLOYEE, we add a SELECT operation as follows

Example (meaningful):

RESULT will now contain the name of female employees and their dependents

Figure 8.5 The Cartesian Product (CROSS PRODUCT) Operation (1 of 3)

Figure 8.5 The Cartesian Product (CROSS PRODUCT) Operation (2 of 3)

Figure 8.5 The Cartesian Product (CROSS PRODUCT) Operation (3 of 3)

Binary Relational Operations: JOIN (1 of 2)

JOIN Operation

The sequence of CARTESIAN PRODECT followed by SELECT is used quite commonly to identify and select related tuples from two relations

A special operation, called JOIN combines this sequence into a single operation

This operation is very important for any relational database with more than a single relation, because it allows us combine related tuples from various relations

The general form of a join operation on two relations

where R and S can be any relations that result from general relational algebra expressions.

Binary Relational Operations: JOIN (2 of 2)

Example: Suppose that we want to retrieve the name of the manager of each department.

To get the manager’s name, we need to combine each DEPARTMENT tuple with the EMPLOYEE tuple whose SSN value matches the MGRSSN value in the department tuple.

We do this by using the join

operation.

MGRSSN=SSN is the join condition

Combines each department record with the employee who manages the department

The join condition can also be specified as DEPARTMENT.MGRSSN= EMPLOYEE.SSN

Figure 8.6 Result of the JOIN Operation D E P T dash M G R left arrow DEPARTMENT super absolute value of x sub start expression m g r dash s s n = S s n end expression EMPLOYEE

Some Properties of JOIN (1 of 2)

Consider the following JOIN operation:

Result is a relation Q with degree n + m attributes:

The resulting relation state has one tuple for each combination of tuples—r from R and s from S, but only if they satisfy the join condition

Hence, if R has nR tuples, and S has nS tuples, then the join result will generally have less than nR * nS tuples.

Only related tuples (based on the join condition) will appear in the result

Some Properties of JOIN (2 of 2)

The general case of JOIN operation is called a Theta-join:

The join condition is called theta

Theta can be any general boolean expression on the attributes of R and S; for example:

Most join conditions involve one or more equality conditions “AND”ed together; for example:

Binary Relational Operations: E Q U I JOIN

E Q U I JOIN Operation

The most common use of join involves join conditions with equality comparisons only

Such a join, where the only comparison operator used is =, is called an E Q U I JOIN.

In the result of an E Q U I JOIN we always have one or more pairs of attributes (whose names need not be identical) that have identical values in every tuple.

The JOIN seen in the previous example was an E Q U I JOIN.

Binary Relational Operations: NATURAL JOIN Operation (1 of 2)

NATURAL JOIN Operation

Another variation of JOIN called NATURAL JOIN — denoted by * — was created to get rid of the second (superfluous) attribute in an EQUIJOIN condition.

because one of each pair of attributes with identical values is superfluous

The standard definition of natural join requires that the two join attributes, or each pair of corresponding join attributes, have the same name in both relations

If this is not the case, a renaming operation is applied first.

Binary Relational Operations: NATURAL JOIN Operation (2 of 2)

Example: To apply a natural join on the D NUMBER attributes of DEPARTMENT and DEPT_LOCATIONS, it is sufficient to write:

Only attribute with the same name is D NUMBER

An implicit join condition is created based on this attribute:

DEPARTMENT.DNUMBER=DEPT_LOCATIONS.DNUMBER

Another example:

The implicit join condition includes each pair of attributes with the same name, “AND”ed together:

R.C=S.C AND R.D.S.D

Result keeps only one attribute of each such pair:

Q(A,B,C,D,E)

Example of NATURAL JOIN Operation

Figure 8.7 Results of two natural join operations.

Complete Set of Relational Operations

The set of operations including SELECT σ, PROJECT π , UNION∪, DIFFERENCE −, RENAME

, and CARTESIAN PRODUCT X is called a complete set because any other relational algebra expression can be expressed by a combination of these five operations.

For example:

Binary Relational Operations: DIVISION

DIVISION Operation

The division operation is applied to two relations

R(Z) ÷ S(X), where X subset Z. Let Y = Z − X (and hence Z = X ∪Y); that is, let Y be the set of attributes of R that are not attributes of S.

The result of DIVISION is a relation T(Y) that includes a

tuple t if tuples

and with

For a tuple t to appear in the result T of the DIVISION, the values in t must appear in R in combination with every tuple in S.

Example of DIVISION

Figure 8.8 The DIVISION operation. (a) Dividing SSN_P N O S by SMITH_P N O S. (b) T ← R ÷ S.

Table 8.1 Operations of Relational Algebra (1 of 2)

Operation	Purpose	Notation
SELECT	Selects all tuples that satisfy the selection condition from a relation R.	sigma sub start expression less than sign selection condition greater than sign left parenthesis R right parenthesis
PROJECT	Produces a new relation with only some of the attributes of R, and removes duplicate tuples.	pi sub start expression less than sign attribute list greater than sign end expression left parenthesis R right parenthesis
THETA JOIN	Produces all combinations of tuples from R1 and R2 that satisfy the join condition.	R sub 1 join start expression less than sign join condition greater than sign end expression R sub 2
EQUIJOIN	Produces all the combinations of tuples from R1 and R2 that satisfy a join condition with only equality comparisons.	R sub 1 join start expression less than sign join condition greater than sign end expression R sub 2 OR R sub 1 join sub start expression left parenthesis less than sign join attributes 1 greater than sign right parenthesis comma left parenthesis less than sign join attributes 2 greater than sign right parenthesis end expression R sub 2
NATURAL JOIN	Same as EQUIJOIN except that the join attributes of R2 are not included in the resulting relation; if the join attributes have the same names, they do not have to be specified at all.	R sub 1 asterisk start expression less than sign join condition greater than sign end expression R sub 2 comma OR R sub 1 asterisk sub start expression left parenthesis less that sign join attributes 1 greater than sign right parenthesis comma left parenthesis less than sign join attributes 2 greater than sign right parenthesis comma R sub 2 OR R sub 1 asterisk R sub 2.

Table 8.1 Operations of Relational Algebra (2 of 2)

Operation	Purpose	Notation
UNION	Produces a relation that includes all the tuples in R1 or R2 or both R1 and R2; R1 and R2 must be union compatible.	R sub 1 union R sub 2
INTERSECTION	Produces a relation that includes all the tuples in both R1 and R2; R1 and R2 must be union compatible.	R sub 1 inter section R sub 2
DIFFERENCE	Produces a relation that includes all the tuples in R1 that are not in R2; R1 and R2 must be union compatible.	R sub 1 minus R sub 2
CARTESIAN PRODUCT	Produces a relation that has the attributes of R1 and R2 and includes as tuples all possible combinations of tuples from R1 and R2.	R sub 1 times R sub 2
DIVISION	Produces a relation R(X) that includes all tuples t[X] in R1(Z) that appear in R1 in combination with every tuple from R2(Y), where Z = X ∪ Y.	R sub1 left parenthesis Z right parenthesis divided R sub2 left parenthesis Y right parenthesis

Query Tree Notation

Query Tree

An internal data structure to represent a query

Standard technique for estimating the work involved in executing the query, the generation of intermediate results, and the optimization of execution

Nodes stand for operations like selection, projection, join, renaming, division, ….

Leaf nodes represent base relations

A tree gives a good visual feel of the complexity of the query and the operations involved

Algebraic Query Optimization consists of rewriting the query or modifying the query tree into an equivalent tree.

(see Chapter 15)

Example of Query Tree

Figure 8.9 Query tree corresponding to the relational algebra expression for Q2.

Additional Relational Operations: Aggregate Functions and Grouping

A type of request that cannot be expressed in the basic relational algebra is to specify mathematical aggregate functions on collections of values from the database.

Examples of such functions include retrieving the average or total salary of all employees or the total number of employee tuples.

These functions are used in simple statistical queries that summarize information from the database tuples.

Common functions applied to collections of numeric values include

SUM, AVERAGE, MAXIMUM, and MINIMUM.

The COUNT function is used for counting tuples or values.

Aggregate Function Operation

Use of the Aggregate Functional operation Ƒ

retrieves the maximum salary value from the EMPLOYEE relation

retrieves the minimum Salary value from the EMPLOYEE relation

retrieves the sum of the Salary from the EMPLOYEE relation

computes the count (number) of employees and their average salary

Note: count just counts the number of rows, without removing duplicates

Using Grouping With Aggregation

The previous examples all summarized one or more attributes for a set of tuples

Maximum Salary or Count (number of) Ssn

Grouping can be combined with Aggregate Functions

Example: For each department, retrieve the D NO, COUNT SSN, and AVERAGE SALARY

A variation of aggregate operation Ƒ allows this:

Grouping attribute placed to left of symbol

Aggregate functions to right of symbol

Above operation groups employees by DNO (department number) and computes the count of employees and average salary per department

Figure 8.10 the Aggregate Function Operation

(a)

Dno	No_of_employees	Average_sal
5	4	33250
4	3	31000
1	1	55000

(b)

Dno	Count_ssn	Average_salary
5	4	33250
4	3	31000
1	1	55000

(c)

Count_ssn	Average_salary
8	35125

Figure 7.1a Results of GROUP by and HAVING (in S Q L). Q24

Additional Relational Operations (1 of 6)

Recursive Closure Operations

Another type of operation that, in general, cannot be specified in the basic original relational algebra is recursive closure.

This operation is applied to a recursive relationship.

An example of a recursive operation is to retrieve all SUPERVISEES of an EMPLOYEE e at all levels — that is, all EMPLOYEE e’ directly supervised by e; all employees e’’ directly supervised by each employee e’; all employees e’’’ directly supervised by each employee e’’; and so on.

Additional Relational Operations (2 of 6)

Although it is possible to retrieve employees at each level and then take their union, we cannot, in general, specify a query such as “retrieve the supervisees of ‘James Borg’ at all levels” without utilizing a looping mechanism.

The S Q L 3 standard includes syntax for recursive closure.

Figure 8.11 A Two-Level Recursive Query

Additional Relational Operations (3 of 6)

The OUTER JOIN Operation

In NATURAL JOIN and EQUIJOIN, tuples without a matching (or related) tuple are eliminated from the join result

Tuples with null in the join attributes are also eliminated

This amounts to loss of information.

A set of operations, called OUTER joins, can be used when we want to keep all the tuples in R, or all those in S, or all those in both relations in the result of the join, regardless of whether or not they have matching tuples in the other relation.

Additional Relational Operations (4 of 6)

The left outer join operation keeps every tuple in the first or left relation R in

; if no matching tuple is found in S, then the attributes of S in the join result are filled or “padded” with null values.

A similar operation, right outer join, keeps every tuple in the second or right relation S in the result of

A third operation, full outer join, denoted by

keeps all tuples in both the left and the right relations when no matching tuples are found, padding them with null values as needed.

Figure 8.12 The Result of a LEFT OUTER JOIN Operation

Result

F name	M init	L name	D name
John	B	Smith	NULL
Franklin	T	Wong	Research
Alicia	J	Zelaya	NULL
Jennifer	S	Wallace	Administration
Ramesh	K	Narayan	NULL
Joyce	A	English	NULL
Ahmad	V	Jabbar	NULL
James	E	Borg	Headquarters

Additional Relational Operations (5 of 6)

OUTER UNION Operations

The outer union operation was developed to take the union of tuples from two relations if the relations are not type compatible.

This operation will take the union of tuples in two relations R(X, Y) and S(X, Z) that are partially compatible, meaning that only some of their attributes, say X, are type compatible.

The attributes that are type compatible are represented only once in the result, and those attributes that are not type compatible from either relation are also kept in the result relation T(X, Y, Z).

Additional Relational Operations (6 of 6)

Example: An outer union can be applied to two relations whose schemas are STUDENT(Name, SSN, Department, Advisor) and INSTRUCTOR(Name, SSN, Department, Rank).

Tuples from the two relations are matched based on having the same combination of values of the shared attributes— Name, SSN, Department.

If a student is also an instructor, both Advisor and Rank will have a value; otherwise, one of these two attributes will be null.

The result relation STUDENT_OR_INSTRUCTOR will have the following attributes:

STUDENT_OR_INSTRUCTOR (Name, SSN, Department, Advisor, Rank)

Examples of Queries in Relational Algebra: Procedural Form

Q1: Retrieve the name and address of all employees who work for the ‘Research’ department.

Q6: Retrieve the names of employees who have no dependents.

Examples of Queries in Relational Algebra – Single Expressions

As a single expression, these queries become:

Q1: Retrieve the name and address of all employees who work for the ‘Research’ department.

Q6: Retrieve the names of employees who have no dependents.

Relational Calculus (1 of 2)

A relational calculus expression creates a new relation, which is specified in terms of variables that range over rows of the stored database relations (in tuple calculus) or over columns of the stored relations (in domain calculus).

In a calculus expression, there is no order of operations to specify how to retrieve the query result—a calculus expression specifies only what information the result should contain.

This is the main distinguishing feature between relational algebra and relational calculus.

Relational Calculus (2 of 2)

Relational calculus is considered to be a nonprocedural or declarative language.

This differs from relational algebra, where we must write a sequence of operations to specify a retrieval request; hence relational algebra can be considered as a procedural way of stating a query.

Tuple Relational Calculus (1 of 2)

The tuple relational calculus is based on specifying a number of tuple variables.

Each tuple variable usually ranges over a particular database relation, meaning that the variable may take as its value any individual tuple from that relation.

A simple tuple relational calculus query is of the form

where t is a tuple variable and COND (t) is a conditional expression involving t.

The result of such a query is the set of all tuples t that satisfy COND (t).

Tuple Relational Calculus (2 of 2)

Example: To find the first and last names of all employees whose salary is above $50,000, we can write the following tuple calculus expression:

The condition EMPLOYEE(t) specifies that the range relation of tuple variable t is EMPLOYEE.

The first and last name

of each EMPLOYEE tuple t that satisfies the condition

will be retrieved.

The Existential and Universal Quantifiers (1 of 2)

Two special symbols called quantifiers can appear in formulas; these are the universal quantifier

and the existential quantifier

Informally, a tuple variable t is bound if it is quantified, meaning that it appears in an

clause; otherwise, it is free.

If F is a formula, then so are

where t is a tuple

variable.

The formula

is true if the formula F evaluates to true for some (at least one) tuple assigned to free occurrences of t in F; otherwise

is false.

The formula

is true if the formula F evaluates to true for every tuple (in the universe) assigned to free occurrences of t in F; otherwise

is false.

The Existential and Universal Quantifiers (2 of 2)

is called the universal or “for all” quantifier because every tuple in “the universe of” tuples must make F true to make the quantified formula true.

is called the existential or “there exists” quantifier because any tuple that exists in “the universe of” tuples may make F true to make the quantified formula true.

Example Query Using Existential Quantifier (1 of 2)

Retrieve the name and address of all employees who work for the ‘Research’ department. The query can be expressed as :

The only free tuple variables in a relational calculus expression should be those that appear to the left of the bar ( | ).

In above query, t is the only free variable; it is then bound successively to each tuple.

If a tuple satisfies the conditions specified in the query, the attributes F NAME, L NAME, and ADDRESS are retrieved for each such tuple.

The conditions EMPLOYEE (t) and DEPARTMENT(d) specify the range relations for t and d.

The condition d.D NAME = ‘Research’ is a selection condition and corresponds to a SELECT operation in the relational algebra, whereas the condition d.D NUMBER = t.D NO is a JOIN condition.

Example Query Using Existential Quantifier (2 of 2)

Find the names of employees who work on all the projects controlled by department number 5. The query can be:

Exclude from the universal quantification all tuples that we are not interested in by making the condition true for all such tuples.

The first tuples to exclude (by making them evaluate automatically to true) are those that are not in the relation R of interest.

In query above, using the expression not(PROJECT(x)) inside the universally quantified formula evaluates to true all tuples x that are not in the PROJECT relation.

Then we exclude the tuples we are not interested in from R itself. The expression not (x.DNUM=5) evaluates to true all tuples x that are in the project relation but are not controlled by department 5.

Finally, we specify a condition that must hold on all the remaining tuples in R.

Languages Based on Tuple Relational Calculus (1 of 2)

The language S Q L is based on tuple calculus. It uses the basic block structure to express the queries in tuple calculus:

SELECT <list of attributes>

FROM <list of relations>

WHERE <conditions>

SELECT clause mentions the attributes being projected, the FROM clause mentions the relations needed in the query, and the WHERE clause mentions the selection as well as the join conditions.

S Q L syntax is expanded further to accommodate other operations. (See Chapter 8).

Languages Based on Tuple Relational Calculus (2 of 2)

Another language which is based on tuple calculus is QUEL which actually uses the range variables as in tuple calculus. Its syntax includes:

RANGE OF <variable name> IS <relation name>

Then it uses

RETRIEVE <list of attributes from range variables>

WHERE <conditions>

This language was proposed in the relational D B M S INGRES. (system is currently still supported by Computer Associates – but the QUEL language is no longer there).

The Domain Relational Calculus (1 of 2)

Another variation of relational calculus called the domain relational calculus, or simply, domain calculus is equivalent to tuple calculus and to relational algebra.

The language called Q B E (Query-By-Example) that is related to domain calculus was developed almost concurrently to S Q L at I B M Research, Yorktown Heights, New York.

Domain calculus was thought of as a way to explain what Q B E does.

Domain calculus differs from tuple calculus in the type of variables used in formulas:

Rather than having variables range over tuples, the variables range over single values from domains of attributes.

To form a relation of degree n for a query result, we must have n of these domain variables— one for each attribute.

The Domain Relational Calculus (2 of 2)

An expression of the domain calculus is of the form

where

are domain variables that range over domains (of attributes)

and C O N D is a condition or formula of the domain relational calculus.

Example Query Using Domain Calculus (1 of 2)

Retrieve the birthdate and address of the employee whose name is ‘John B. Smith’.

Query :

Abbreviated notation EMPLOYEE(qrstuvwxyz) uses the variables without the separating commas: EMPLOYEE(q,r,s,t,u,v,w,x,y,z)

Ten variables for the employee relation are needed, one to range over the domain of each attribute in order.

Of the ten variables

only u and v are free.

Specify the requested attributes, B DATE and ADDRESS, by the free domain variables u for B DATE and v for ADDRESS.

Example Query Using Domain Calculus (2 of 2)

Specify the condition for selecting a tuple following the bar ( | )—

namely, that the sequence of values assigned to the variables q r s t u v w x y z be a tuple of the employee relation and that the values for q (F NAME), r (MINIT), and s (L NAME) be ‘John’, ‘B’, and ‘Smith’, respectively.

Q B E: A Query Language Based on Domain Calculus (Appendix C) (1 of 2)

This language is based on the idea of giving an example of a query using “example elements” which are nothing but domain variables.

Notation: An example element stands for a domain variable and is specified as an example value preceded by the underscore character.

P. (called P dot) operator (for “print”) is placed in those columns which are requested for the result of the query.

A user may initially start giving actual values as examples, but later can get used to providing a minimum number of variables as example elements.

Q B E: A Query Language Based on Domain Calculus (Appendix C) (2 of 2)

The language is very user-friendly, because it uses minimal syntax.

Q B E was fully developed further with facilities for grouping, aggregation, updating etc. and is shown to be equivalent to S Q L.

The language is available under Q M F (Query Management Facility) of D B2 of I B M and has been used in various ways by other products like ACCESS of Microsoft, and PARADOX.

For details, see Appendix C in the text.

Q B E Examples (1 of 3)

Q B E initially presents a relational schema as a “blank schema” in which the user fills in the query as an example:

Example Schema as a Q B E Query Interface

Figure C.1 The relational schema of Figure 3.5 as it may be displayed by Q B E.

Q B E Examples (2 of 3)

The following domain calculus query can be successively minimized by the user as shown:

Query :

Four Successive Ways to Specify a Q B E Query

Figure C.2 Four ways to specify the query Q0 in Q B E.

Q B E Examples (3 of 3)

Specifying complex conditions in Q B E :

A technique called the “condition box” is used in Q B E to state more involved Boolean expressions as conditions.

The C.4(a) gives employees who work on either project 1 or 2, whereas the query in C.4(b) gives those who work on both the projects.

Complex Conditions with and Without a Condition Box as a Part of Q B E Query

Figure C.3 Specifying complex conditions in Q B E. (a) The query Q0A. (b) The query Q0B with a condition box. (c) The query Q0B without a condition box.

Handling AND conditions in a Q B E Query

Figure C.4 Specifying EMPLOYEES who work on both projects. (a) Incorrect specification of an AND condition. (b) Correct specification.

Join in Q B E : Examples

The join is simply accomplished by using the same example element (variable with underscore) in the columns being joined from different (or same as in C.5 (b)) relation.

Note that the Result is set us as an independent table to show variables from multiple relations placed in the result.

Performing Join with Common Example Elements and Use of a Result Relation

Figure C.5 Illustrating JOIN and result relations in Q B E. (a) The query Q1. (b) The query Q8.

Aggregation in Q B E

Aggregation is accomplished by using .C N T for count, .MAX, .MIN, .A V G for the corresponding aggregation functions

Grouping is accomplished by .G operator.

Condition Box may use conditions on groups (similar to HAVING clause in S Q L – see Section 8.5.8)

Aggregation in Q B E : Examples

Figure C.6 Functions and grouping in Q B E. (a) The query Q23. (b) The query Q23A. (c) The query Q24. (d) The query Q26.

Negation in Q B E : Example

Figure C.7 Illustrating negation by the query Q6.

Updating in Q B E : Example

Figure C.8 Modifying the database in Q B E. (a) Insertion. (b) Deletion. (c) Update in Q B E.

Chapter Summary

Relational Algebra

Unary Relational Operations

Relational Algebra Operations From Set Theory

Binary Relational Operations

Additional Relational Operations

Examples of Queries in Relational Algebra

Relational Calculus

Tuple Relational Calculus

Domain Relational Calculus

Overview of the Q B E language (appendix C)

(

)

(

symbol sigma

)

(

)

symbol

(

:ppi

)

(

)

symbol

(

:prho

)

UNION ,INTERSECITON

()()

ÈÇ

(

)

DNO= 4

EMPLOYEE

(

)

Salary>30,000

EMPLOYEE

(

)

wher

(

)

σR

(

)

(

)

(

)

(

)

<condition 1><condition 2><condition 2><

condition 1>

σσRσσR

(

)

(

)

(

)

(

)

(

)

(

)

<cond1><cond2><cond3><cond2><cond3><cond

σσσRσσσR

(

)

(

)

(

)

(

)

<cond1><cond2><cond3><cond2>AND<cond2>AN

D<cond3>

σσσRσR)

(

)

LNAME, FNAME,SALARY

EMPLOYEE

(

)

(

)

<list>

(

)

(

)

ppp

() as long as <list2>

contains the attributes in <list1>

(

)

(

)

(

)

Dno=4 AND Salary>25000 OR Dno=5 AND Sala

ry>30000

Lname,Fname, SalarySex, Sal

(()

ary

)

(a)

σEMPLOYEE.

(b)EMPLOYEE. (c) EMPLOYEE.

(

)

FNAME, LNAME,SALARYDNO=5

σ(EMPLOYEE)

DNO=5

DEP5_EMPS

σ(EMPLOYEE)

(

)

FNAME, LNAME,SALARY

RESUL

P5_

EMPS

¬p

(rho)

(

)

SB1B2Bn

()

, , …,

changes both:

(

)

changes:

(

)

, , …

()

changes:

B1B2Bn

(

)

FNAME, LNAME, SALARY

RESULTDEP5_EMPS

¬p

(

)

(

)

RESULT F.M.L.S.B,A,SX,SAL,SU, DNO

DEP5_EMPS

(

)

Fname,Lname, Salary Dno=5

σEMPLOY

(

)

(

)

(

)

(

)

(

)

¬p

¬È

DNO=5

SSN

SUPERSSN

DEP5_EMPS

σEMPLOYEE

RESULT1DEP5_EMPS

RESULT2SsnDEP5_EMPS

RESULTRESULT1RESULT2

ÈÇ-

UNION,also for INTERSECTION,and SET DIFF

ERENCE

(

ÈÇ-

121212

RR also for RR, or RR, see next sl

(

ides

)

STUDENTINSTRUCTOR.

RS = SR, and RS = SR

ÈÈÇÇ

RS SR

-¹-

R(ST) = (RS)T (RS)T = R(ST)

(denoted as

|| =

)

(

)

SEX=’F’

FEMALE_EMPS

σEMPLOYEE

(

)

FNAME, LNAME, SSN

EMPNAMESFEMALE_EMPS

¬p

EMP_DEPENDENTSEMPNAMES x DEPENDENT

(

)

FNAME, LNAME, SSN

EMPNAMESFEMALE_EMPS

¬p

(

)

SSN=ESSN

ACTUAL_DEPS

σEMP_DEPENDENTS

(

)

FNAME, LNAME, DEPENDENT_NAME

RESULTACTUAL_DEPS

¬p

Mgr_ssn=Ssn

DEPT_MGRDEPARTMENT EMPLOYEE

Mgr_ssn=Ssn

DEPT_MGR DEPARTMENT EMPLOYEE

← �

.=.B

12n12m

()

(A, A, . . ., A) B, B, . . ., B

(, . . ., , , , . . ., ), in that order

12,n12m

QAAABBB

theta

DEPT_LOCSDEPARTMENT * DEPT_LOCATIONS

(

)

(

)

QRA,B,C,D * SC,D,E

(a) proj_dept project * dept. (b) dept_l

ocs department *dept_locations.

¬¬

= –

()(()())

ÇÈ-Ç-

RSRSRSSR

(

)

SRS

[

]

appear in with = ,

tRtYt

[

]

= in .

forevery tuple

RSS

tXttS

(

)

(

)

(

)

(

)

, OR

R R

(

)

(

)

* , OR

OR *

212

RRR

(

)

(

)

RZRY

(

)

MAX Salary

EMPLOYEE

(

)

MIN Salary

EMPLOYEE

(

)

SUM Salary

EMPLOYEE

(

)

COUNT Ssn,AVERAGE Salary

EMPLOYEE

(

)

DnoCOUNT Ssn, AVERAGE Salary

EMPLOYEE

 DNUMBER= DNOEMPLOYEEFNAME, LNAME, ADDRESSDNAME=’Research’RESEARCH_DEPTDEPARTMENTRESEARCH_EMPSRESEARCH_DEPT EMPLOYEERESULTRESEARCH_EMPS()

SSNESSNLNAME, FNAME ALL_EMPS()EMPLOYEEEMPS_WITH_DEPSSSNDEPENDENTEMPS_WITHOUT_DEPS()()ALL_EMPSEMPS_WITH_DEPSRESULTEMPS_WITHOUT_DEPS * EMPL(OEE)Y

Fname,Lname, Address

Dnumber=Dno

DnameResearch

DEPARTMENTEMPLOYEE

= ‘

(

)

’

(

Lname,FnameSsnSsnEssn

EMPLOYEE)

DEPENDENTEMPLOYEE

(((

()))

(

) *

pprp

(

)

{

}

OND

t t

(

)

{

}

.FName,.LName|EMPLOYEE AND.Salary>50000

tttt

FNAME, LNAME

PROJECTION

()

SALARY >50000

.SALARY>50000 SELECTION

()

(

)

(

)

.FNAME,.LNAME,.ADDRESS EMPLOYEE andd

DEPARTMENTd andd.DNAME=‘Research’ and

d.DNUMBER

{

|()

t.DN

(

}

)

tttt

12nn+1n+2n+m

x1, x2, . . .,xn

CONDx, x, . . .,x, x, x, . . .,x

()}

12nn+1n+2n+m

x, x, . . .,x, x, x, . . .,x

uv q r s t w x y z

EMPLOYE

{|()()()()()()()()

(()

Eqrstuvwxyz and q=’John’ and r=’B’ and s

=’Smith’

)}

$$$$$$$$