Domain Relational Calculus (1)
The formal specification of the domain calculus was proposed
after the development of the QBE language and system.
Domain calculus differs from tuple calculus in the type of
variables used in formulas: 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.

60 trang |

Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 13 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu **Bài giảng Database systems - Relational data model (3)**, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

DATABASE SYSTEMS
Nguyen Ngoc Thien An
RELATIONAL DATA MODEL
Spring 2014
Contents
2
Overview of Relational Data Model
ER- & EER-to-Relational Mapping
Relational Algebra
Relational Algebra 3
Contents
4
Overview
Unary Relational Operations
Relational Algebra Operations from Set Theory
Binary Relational Operations
Additional Relational Operations
Brief Introduction to Relational Calculus
Reading Suggestion: [1] Chapter 6
Overview (1)
5
A data model must include
Concepts for defining the database’s structure and
constraints.
A set of operations to manipulate the database.
Relational Data Model
Structure and constraints relation, attribute, tuple,
integrity constraints.
Operations
Formal languages: the relational algebra and the relational
calculus.
Practical language: SQL (Chapter 5).
Overview (2)
6
Relational Algebra
A basic set of operations for the relational data model.
Specify retrieval requests (or queries) as relational algebra
expressions.
Relational algebra expression: Sequence of relational
algebra operations.
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).
Importance:
A formal foundation for relational model operations.
A basis for implementing and optimizing queries in relational
DBMSs.
Its concepts are incorporated into the SQL standard query
language.
Overview (3)
7
Relational Calculus
A higher-level declarative language for specifying relational
queries.
Based on the branch of mathematical logic called predicate
calculus.
A relational calculus expression creates a new relation.
Not specify how to retrieve the query result.
Only specify what information the result should contain.
Importance:
Having a firm basis in mathematical logic.
SQL has some of its foundations.
Two variations of relational calculus:
Tuple relational calculus: variables range over tuples.
Domain relational calculus: variables range over the domains
(values) of attributes.
Relational Algebra
8
Set operations from mathematical set theory:
UNION (∪), INTERSECTION (∩), DIFFERENCE (or MINUS,−)
CARTESIAN PRODUCT (×)
Operations developed specifically for relational databases:
Unary Relational Operations:
SELECT symbol: 𝝈 (sigma)
PROJECT symbol: 𝝅 (pi)
RENAME symbol: 𝝆 (rho)
Binary Relational Operations:
JOIN (several variations of JOIN exist)
DIVISION
Additional Relational Operations:
OUTER JOINs, OUTER UNIONs
Aggregate functions (SUM, COUNT, AVG, MIN, MAX)
9
Fname Minit Lname SSN Bdate Address Sex Salary Super_SSN Dno
Dname Dnumber Mgr_SSN Mgr_start_date
Dnumber Dlocation
PnumberPname Plocation Dnum
Essn Pno Hours
Essn Dependent_name BdateSex Relationship
EMPLOYEE
DEPARTMENT
DEPT_LOCATIONS
PROJECT
WORKS_ON
DEPENDENT
10
Contents
11
Overview
Unary Relational Operations
Relational Algebra Operations from Set Theory
Binary Relational Operations
Additional Relational Operations
Brief Introduction to Relational Calculus
Unary Operations – SELECT (1)
12
The SELECT operation
Select a subset of the tuples from a relation
based on a selection condition filter/restrict.
Horizontal partition of the relation.
Denotation: 𝑆 = 𝜎(𝑅)
𝜎 (sigma): the SELECT operator.
𝑅: a relational algebra expression whose result is a
relation.
: Boolean expression on
attributes of R.
Result: tuples that make the condition true.
Unary Operations – SELECT (2)
13
The SELECT operation
Properties:
𝐷𝑒𝑔𝑟𝑒𝑒(𝑆) = 𝐷𝑒𝑔𝑟𝑒𝑒(𝑅): S has the same attributes as R.
|𝑆| ≤ |𝑅|: The number of tuples of S is less than (or equal
to) R.
SELECT is commutative:
𝜎 𝜎 𝑅 = 𝜎 𝜎 𝑅
Can combine a cascade (or sequence) of SELECT
operations into a single SELECT operation:
𝜎 𝜎 𝜎 𝑅
= 𝜎 𝜎 𝜎 𝑅 = ⋯
= 𝜎𝐴𝑁𝐷𝐴𝑁𝐷(𝑅)
Unary Operations – SELECT (3)
14
The Boolean expression
Made up of a number of clauses of the form:
or
: one of the operators { =, ,
≥, ≠, 𝑆𝑈𝐵𝑆𝑇𝑅𝐼𝑁𝐺_𝑂𝐹, } (dependent on domains).
Clauses can be connected by the standard Boolean
operators 𝐴𝑁𝐷, 𝑂𝑅, 𝑁𝑂𝑇 to form a general selection
condition.
Unary Operations – SELECT (4)
15
E.g.:
Select the EMPLOYEE tuples whose department
number is 4: 𝜎𝐷𝑛𝑜=4(𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)
Select the employee tuples whose salary is greater
than $30,000: 𝜎𝑆𝑎𝑙𝑎𝑟𝑦>30,000(𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)
Select the tuples for all employees who either work in
department 4 and make over $25,000 per year, or
work in department 5 and make over $30,000:
𝜎 𝐷𝑛𝑜=4 𝑨𝑵𝑫 𝑆𝑎𝑙𝑎𝑟𝑦>25,000 𝑶𝑹 (𝐷𝑛𝑜=5 𝑨𝑵𝑫 𝑆𝑎𝑙𝑎𝑟𝑦>30,000)(𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)
Unary Operations – PROJECT (1)
16
The PROJECT operation
Select certain columns from a relation and discard
the other columns project the relation over these
attributes only.
Vertical partition of the relation.
Denotation: 𝑆 = 𝜋(𝑅)
𝜋 (pi): the PROJECT operator.
𝑅: a relational algebra expression whose result is a relation.
: the desired sublist of attributes from R.
Result: has only the attributes specified in <
𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 𝑙𝑖𝑠𝑡 > in the same order as they appear in
the list.
Unary Operations – PROJECT (2)
17
The PROJECT operation
Properties:
The degree of S is equal to the number of attributes in
.
Duplicate elimination: The PROJECT operation
removes any duplicate tuples 𝑆 ≤ 𝑅
If the list of attributes includes a superkey of R: 𝑆 = 𝑅 .
PROJECT is not commutative:
𝜋 𝜋 𝑅 = 𝜋(𝑅) as long as
contains the attributes in ; otherwise, the left-hand
side is an incorrect expression.
Unary Operations – PROJECT (3)
18
E.g.:
List each employee’s first
and last name and salary:
𝜋𝐿𝑛𝑎𝑚𝑒,𝐹𝑛𝑎𝑚𝑒,𝑆𝑎𝑙𝑎𝑟𝑦(𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)
List sex and salary of
employees:
𝜋𝑆𝑒𝑥,𝑆𝑎𝑙𝑎𝑟𝑦(𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸)
Relational Algebra Expressions
19
Specify several relational algebra operations
one after the other by one of two ways:
Write the operations as a single relational
algebra expression by nesting the operations.
Apply one operation at a time and create
intermediate result relations.
Must give names to the relations that hold the
intermediate results.
Unary Operations – RENAME (1)
20
The RENAME operation
Change the name of a relation or its attributes or
both.
Useful when a query requires multiple operations.
Necessary in some cases (JOIN, UNION,).
Without renaming, the attribute names and their
order in the resulting relation:
SELECT: the same as those in the original relation.
PROJECT: the same as those in the projection list.
Unary Operations – RENAME (2)
21
The RENAME operation
Denotation:
Change the relation name only: 𝜌𝑆 𝑅
Change the attribute names only: 𝜌 𝐵1,𝐵2,,𝐵𝑛 (𝑅)
Change both the relation name and the attribute
names: 𝜌𝑆 𝐵1,𝐵2,,𝐵𝑛 𝑅
𝜌 (rho): the RENAME operator.
𝑆: the new relation name.
𝐵1, 𝐵2, , 𝐵𝑛: the new attribute names.
Unary Operations – RENAME (3)
22
E.g.:
A single relational algebra
expression:
𝜋𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒,𝑆𝑎𝑙𝑎𝑟𝑦(𝜎𝐷𝑛𝑜=5 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸 )
Give a name to each intermediate
relation:
𝑇𝐸𝑀𝑃 ← 𝜎𝐷𝑛𝑜=5 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸
𝑅 (𝐹𝑖𝑟𝑠𝑡_𝑛𝑎𝑚𝑒,𝐿𝑎𝑠𝑡_𝑛𝑎𝑚𝑒,𝑆𝑎𝑙𝑎𝑟𝑦)
← 𝜋𝐹𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒,𝑆𝑎𝑙𝑎𝑟𝑦 𝑇𝐸𝑀𝑃
Contents
23
Overview
Unary Relational Operations
Relational Algebra Operations from Set Theory
Binary Relational Operations
Additional Relational Operations
Brief Introduction to Relational Calculus
Set Operations
24
Include: UNION, INTERSECTION, MINUS (also called SET
DIFFERENCE or EXCEPT).
Merge the elements of two sets.
These are binary operations (applied to two sets of tuples).
Two relations on which a operator is applied must have the same
type of tuples.
Type compatibility.
Type compatibility (Union compatibility): Two relations
𝑅 𝐴1, 𝐴2, , 𝐴𝑛 and 𝑆 𝐵1, 𝐵2, , 𝐵𝑛 are type compatible if
they have:
The same degree 𝑛.
𝑑𝑜𝑚 𝐴𝑖 = 𝑑𝑜𝑚 𝐵𝑖 𝑓𝑜𝑟 1 ≤ 𝑖 ≤ 𝑛.
Convention: the resulting relation has the same attribute
names as the first relation R.
Set Operations – UNION
25
The UNION operation
Denotation: 𝑅 ∪ 𝑆
The result of this operation is a relation including
all tuples that are either in R or in S or in both R
and S.
Duplicate tuples are eliminated.
UNION is commutative: 𝑅 ∪ 𝑆 = 𝑆 ∪ 𝑅
UNION is associative: 𝑅 ∪ (𝑆 ∪ 𝑇) = (𝑅 ∪ 𝑆) ∪ 𝑇
Set Operations – INTERSECTION
26
The INTERSECTION operation
Denotation: 𝑅 ∩ 𝑆
The result of this operation is a relation including
all tuples that are in both R and S.
INTERSECTION is commutative: 𝑅 ∩ 𝑆 = 𝑆 ∩ 𝑅
INTERSECTION is associative:
𝑅 ∩ (𝑆 ∩ 𝑇) = (𝑅 ∩ 𝑆) ∩ 𝑇
INTERSECTION can be expressed in terms of
union and set difference:
𝑅 ∩ 𝑆 = 𝑅 ∪ 𝑆 − 𝑅 − 𝑆 − (𝑆 − 𝑅)
Set Operations – MINUS
27
The MINUS (or SET DIFFERENCE)
operation
Denotation: 𝑅 − 𝑆
The result of this operation is a relation including
all tuples that are in R but not in S.
MINUS is not commutative: 𝑅 − 𝑆 ≠ 𝑆 − 𝑅
Set Operations – Example (1)
28
E.g.:
Retrieve the Ssn of all employees who either work in
department 5 or directly supervise an employee who
works in department 5:
𝐷𝐸𝑃5_𝐸𝑀𝑃𝑆 ← 𝜎𝐷𝑛𝑜=5 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸
𝑅𝐸𝑆𝑈𝐿𝑇1 ← 𝜋𝑆𝑠𝑛(𝐷𝐸𝑃5_𝐸𝑀𝑃𝑆)
𝑅𝐸𝑆𝑈𝐿𝑇2 (𝑆𝑠𝑛) ← 𝜋𝑆𝑢𝑝𝑒𝑟_𝑆𝑠𝑛(𝐷𝐸𝑃5_𝐸𝑀𝑃𝑆)
𝑅𝐸𝑆𝑈𝐿𝑇 ← 𝑅𝐸𝑆𝑈𝐿𝑇1 ∪ 𝑅𝐸𝑆𝑈𝐿𝑇2
Set Operations – Example (2)
29
Set Operations - CARTESIAN PRODUCT
30
The CARTESIAN PRODUCT operation
Also known as CROSS PRODUCT or CROSS JOIN.
A binary set operation.
Two operand relations do NOT have to be type compatible.
Produce a new element by combining every member
(tuple) from one relation (set) with every member from the
other relation.
Denotation: 𝑅 × 𝑆 (with 𝑅 𝐴1, 𝐴2, , 𝐴𝑛 , 𝑆(𝐵1, 𝐵2, , 𝐵𝑚))
Result: 𝑄(𝐴1, 𝐴2, , 𝐴𝑛, 𝐵1, 𝐵2, , 𝐵𝑚) , in that order.
Properties:
𝐷𝑒𝑔𝑟𝑒𝑒 𝑄 = 𝑛 + 𝑚
𝑅 = 𝑛𝑅, 𝑆 = 𝑛𝑆 𝑅 × 𝑆 = 𝑛𝑅 ∗ 𝑛𝑆
Useful when followed by a selection that matches values of
attributes.
Contents
31
Overview
Unary Relational Operations
Relational Algebra Operations from Set Theory
Binary Relational Operations
Additional Relational Operations
Brief Introduction to Relational Calculus
Binary Operations – JOIN (1)
32
The JOIN operation
Combine related tuples from two relations into single
“longer” tuples.
Denotation: 𝑅 ⋈ 𝑆
𝑅 𝐴1, 𝐴2, , 𝐴𝑛 , 𝑆(𝐵1, 𝐵2, , 𝐵𝑚) : relations that result from
general relational algebra expressions.
= AND
AND AND : The join condition is specified on
attributes from R and S and is evaluated for each combination
of tuples.
= 𝐴𝑖 𝜃 𝐵𝑗
𝐴𝑖: an attriute of R 𝐵𝑗: an attribute of S
𝐴𝑖 𝑎𝑛𝑑 𝐵𝑗 : have the same domain.
𝜃: one of the comparison operators {=, , ≥, ≠}.
Binary Operations – JOIN (2)
33
The JOIN operation
Result:
Only combinations of tuples satisfying the join condition appear in Q
as a single combined tuple 𝑄(𝐴1, 𝐴2, , 𝐴𝑛, 𝐵1, 𝐵2, , 𝐵𝑚) , in that
order.
Tuples whose join attributes are NULL or for which the join condition
is FALSE do not appear in the result.
Properties:
𝐷𝑒𝑔𝑟𝑒𝑒 𝑄 = 𝑛 + 𝑚
𝑅 = 𝑛𝑅, 𝑆 = 𝑛𝑆 0 ≤ 𝑄 ≤ 𝑛𝑅 ∗ 𝑛𝑆
The expected size of the join result divided by the maximum size 𝑛𝑅 ∗ 𝑛𝑆
leads to a ratio called join selectivity.
Can be specified as a CARTESIAN PRODUCT operation followed by
a SELECT operation.
A JOIN operation with a general join condition is called a THETA
JOIN.
Binary Operations – JOIN (3)
34
E.g.:
Retrieve the name of the manager of each
department:
𝐷𝐸𝑃𝑇_𝑀𝐺𝑅 ← 𝐷𝐸𝑃𝐴𝑅𝑇𝑀𝐸𝑁𝑇 ⋈𝑀𝑔𝑟_𝑆𝑠𝑛=𝑆𝑠𝑛 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸
𝑅𝐸𝑆𝑈𝐿𝑇 ← 𝜋𝐷𝑛𝑎𝑚𝑒,𝐿𝑛𝑎𝑚𝑒,𝐹𝑛𝑎𝑚𝑒(𝐷𝐸𝑃𝑇_𝑀𝐺𝑅)
Binary Operations – JOIN (4)
35
The EQUIJOIN operation
A join where the only comparison operator used is
“=“.
The result of an EQUIJOIN always has one or
more pairs of attributes (whose names need NOT
to be identical) that have identical values in every
tuple.
Binary Operations – JOIN (5)
36
The NATURAL JOIN operation
Created to get rid of the second (superfluous)
attribute in an EQUIJOIN condition.
The standard definition of NATURAL JOIN
requires that the two join attributes, or each pair
of corresponding join attributes, have to have
the same name in both relations.
If not, a RENAME operation is applied first.
Denotation: 𝑅 ∗ 𝑆
Binary Operations – JOIN (6)
37
Binary Operations – DIVISION (1)
38
The DIVISION operation
Denotation: 𝑅 ÷ 𝑆
Applied to two relations 𝑅(𝑍) ÷ 𝑆(𝑋) where
𝑍 = 𝑋 ∪ 𝑌 (Y is the set of attributes of R that are
not attributes of S).
Result: a relation 𝑇(𝑌) that includes a tuple t if
tuples 𝑡𝑅 appear in 𝑅 with 𝑡𝑅 𝑌 = 𝑡 , and with
𝑡𝑅 𝑋 = 𝑡𝑆 for every tuple 𝑡𝑆 in S, i.e., 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.
Binary Operations – DIVISION (2)
39
Complete Set of Relational Operations
40
{𝜎, 𝜋,∪, 𝜌, −,×} : complete set of relational
algebra operations.
Any of the other original relational algebra
operations can be expressed as a sequence of
operations from this set.
E.g.:
𝑅 ∩ 𝑆 ≡ 𝑅 ∪ 𝑆 − ( 𝑅 − 𝑆 ∪ 𝑆 − 𝑅 )
𝑅 ⋈ 𝑆 ≡ 𝜎(𝑅 × 𝑆)
Notation for Query Trees
41
Query Tree
Represents the
input relations of
query as leaf
nodes of the
tree.
Represents the
relational
algebra
operations as
internal nodes.
Contents
42
Overview
Unary Relational Operations
Relational Algebra Operations from Set Theory
Binary Relational Operations
Additional Relational Operations
Brief Introduction to Relational Calculus
Additional Relational Operations (1)
43
Generalized Projection
Denotation: 𝑆 = 𝜋𝐹1,𝐹2,,𝐹𝑛(𝑅)
𝐹1, 𝐹2, , 𝐹𝑛: functions over the attributes in relation R and
may involve arithmetic operations and constant values
E.g.:
𝑅𝐸𝑃𝑂𝑅𝑇
← 𝜌 𝑆𝑠𝑛,𝑁𝑒𝑡𝑆𝑎𝑙𝑎𝑟𝑦,𝐵𝑜𝑛𝑢𝑠,𝑇𝑎𝑥 (𝜋𝑆𝑠𝑛,𝑆𝑎𝑙𝑎𝑟𝑦 −𝐷𝑒𝑑𝑢𝑐𝑡𝑖𝑜𝑛,
2000∗𝑌𝑒𝑎𝑟𝑆𝑒𝑟𝑣𝑖𝑐𝑒,
0.25∗𝑆𝑎𝑙𝑎𝑟𝑦
𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸 )
Additional Relational Operations (2)
44
Aggregate Functions
Specify mathematical aggregate functions on collections of
values from the database.
E.g.: retrieving the average or total salary of all employees or the total
number of employee tuples.
Common functions applied to collections of numeric values
include SUM, AVERAGE, MAXIMUM, and MINIMUM.
COUNT function: used for counting tuples or values.
Grouping
Group the tuples in a relation by the value of some of their
attributes and apply an aggregate function independently to
each group.
E.g.: Group EMPLOYEE tuples by Dno and list each Dno value
along with the average salary of employees within the
department.
Additional Relational Operations (3)
45
Denotation:
ℱ(𝑅)
: list of attributes of the
relation specified in R.
: list of ( <
𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 >) pairs.
: one of the allowed functions (SUM,
AVERAGE , MAXIMUM, MINIMUM, COUNT).
: an attribute of the relation specified by R.
Resulting relation has the grouping attributes plus one
attribute for each element in the function list.
If no grouping attributes are specified, the functions
are applied to all the tuples in R.
Additional Relational Operations (4)
46
Use of the Functional operator ℱ
ℱ𝑀𝐴𝑋 𝑆𝑎𝑙𝑎𝑟𝑦 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸 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.
𝐷𝑛𝑜ℱ𝐶𝑂𝑈𝑁𝑇 𝑆𝑠𝑛,𝐴𝑉𝐸𝑅𝐴𝐺𝐸 𝑆𝑎𝑙𝑎𝑟𝑦 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸 groups
employees by DNO (department number) and
computes the count of employees and average salary
per department.
Note: Duplicates are NOT eliminated when an
aggregate function is applied.
Additional Relational Operations (5)
47
E.g.:
𝐷𝑛𝑜ℱ𝐶𝑂𝑈𝑁𝑇 𝑆𝑠𝑛,𝐴𝑉𝐸𝑅𝐴𝐺𝐸 𝑆𝑎𝑙𝑎𝑟𝑦 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸
ℱ𝐶𝑂𝑈𝑁𝑇 𝑆𝑠𝑛,𝐴𝑉𝐸𝑅𝐴𝐺𝐸 𝑆𝑎𝑙𝑎𝑟𝑦 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸
Additional Relational Operations (6)
48
Recursive Closure Operations
In general, recursive closure cannot be specified in
the basic original relational algebra. 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.
We cannot, in general, specify a query such as
“retrieve the supervisees of ‘James Borg’ at all levels”
without utilizing a looping mechanism unless we know
the maximum number of levels.
The SQL3 standard includes syntax for recursive
closure.
Details: Read [1] 6.4.3
Additional Relational Operations (7)
49
The INNER JOIN operation
Tuples with no match are eliminated.
Tuples without a matching (or related) tuple are eliminated
from the join result.
Tuples with NULL in the join attributes are also eliminated.
Include: THETA JOIN, EQUIJOIN, NATURAL JOIN.
The OUTER JOIN operation
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.
Include: LEFT OUTER JOIN ⊐⋈, RIGHT OUTER JOIN,
FULL OUTER JOIN.
The Outer Union operation: Read [1] 6.4.5
Additional Relational Operations (8)
50
The LEFT OUTER JOIN operation
Denotation: 𝑅 ⋈ 𝑆
Keep every tuple in the first, or left, relation R. If no matching
tuple is found in S, then the attributes of S in the join result are
filled or “padded” with NULL values.
The RIGHT OUTER JOIN operation
Denotation: 𝑅 ⋈ 𝑆
Keep every tuple in the second, or right, relation S. If no
matching tuple is found in R, then the attributes of R in the join
result are filled or “padded” with NULL values.
The FULL OUTER JOIN operation
Denotation: 𝑅 ⋈ 𝑆
Keep all tuples in both the left and the right relations when no
matching tuples are found, padding them with NULL values as
needed.
Additional Relational Operations (9)
51
E.g.: List all employee names and also the name of the
departments they manage if they happen to manage a
department (if they do not manage one, we can indicate
it with a NULL value).
Homework !!!
52
Reading:
[1] 6.5 (Examples of Queries in Relational Algebra)
Contents
53
Overview
Unary Relational Operations
Relational Algebra Operations from Set Theory
Binary Relational Operations
Additional Relational Operations
Brief Introduction to Relational Calculus
Relational Calculus
54
A relational calculus expression creates a new
relation, which is specified in terms of variables that
range over rows (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.
Relational calculus is considered to be a
nonprocedural language.
Relational algebra can be considered as a procedural way
of stating a query.
Tuple Relational Calculus (1)
55
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
𝐶𝑂𝑁𝐷 (𝑡) is a conditional expression involving t.
E.g.: To find the first and last names of all
employees whose salary is above $50,000:
{𝑡. 𝐹𝑁𝐴𝑀𝐸, 𝑡. 𝐿𝑁𝐴𝑀𝐸 | 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸(𝑡) 𝐴𝑁𝐷 𝑡. 𝑆𝐴𝐿𝐴𝑅𝑌
> 50000}
Tuple Relational Calculus (2)
56
Quantifiers can appear in formulas:
The universal quantifier: ∀
The existential quantifier: ∃
Informally, a tuple variable t is bound if it is
quantified, meaning that it appears in an (∃𝑡)
or (∀𝑡) clause; otherwise, it is free.
Details: Read [1] 6.6
Tuple Relational Calculus (3)
57
E.g.:
Retrieve the name and address of all employees who work for
the ‘Research’ department.
𝑡. 𝐹𝑛𝑎𝑚𝑒, 𝑡. 𝐿𝑛𝑎𝑚𝑒, 𝑡. 𝐴𝑑𝑑𝑟𝑒𝑠𝑠 𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸 𝑡
𝑨𝑵𝑫 (∃ 𝑑) (𝐷𝐸𝑃𝐴𝑅𝑇𝑀𝐸𝑁𝑇 𝑑 𝑨𝑵𝑫 𝑑. 𝐷𝑛𝑎𝑚𝑒
= ‘𝑅𝑒𝑠𝑒𝑎𝑟𝑐ℎ’ 𝑨𝑵𝑫 𝑑. 𝐷𝑛𝑢𝑚𝑏𝑒𝑟 = 𝑡. 𝐷𝑛𝑜) }
Find the names of employees who work on some projects
controlled by department number 5.
{𝑒. 𝐿𝑛𝑎𝑚𝑒, 𝑒. 𝐹𝑛𝑎𝑚𝑒|𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸(𝑒)
𝑨𝑵𝑫((∃ 𝑥)(∃ 𝑤)(𝑃𝑅𝑂𝐽𝐸𝐶𝑇 𝑥 𝑨𝑵𝑫 𝑊𝑂𝑅𝐾𝑆_𝑂𝑁 𝑤 𝑨𝑵𝑫 𝑥. 𝐷𝑛𝑢𝑚𝑏𝑒𝑟
= 5 𝑨𝑵𝑫 𝑤. 𝐸𝑆𝑆𝑁 = 𝑒. 𝑆𝑆𝑁 𝑨𝑵𝑫 𝑥. 𝑃𝑁𝑈𝑀𝐵𝐸𝑅 = 𝑤. 𝑃𝑁𝑂))}
Domain Relational Calculus (1)
58
The formal specification of the domain calculus was proposed
after the development of the QBE language and system.
Domain calculus differs from tuple calculus in the type of
variables used in formulas: 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.
An expression of the domain calculus is of the form:
𝑥1, 𝑥2, , 𝑥𝑛 𝐶𝑂𝑁𝐷 𝑥1, 𝑥2, , 𝑥𝑛, 𝑥𝑛+1, 𝑥𝑛+2, , 𝑥𝑛+𝑚 }
Where 𝑥1, 𝑥2, , 𝑥𝑛 , 𝑥𝑛+1, 𝑥𝑛+2, , 𝑥𝑛+𝑚 are domain variables that
range over domains (of attributes) and 𝐶𝑂𝑁𝐷 is a condition or
formula of the domain relational calculus.
Details: Read [1] 6.7
Domain Relational Calculus (2)
59
E.g.: List the birth date and address of the
employee whose name is ‘John B. Smith’.
{𝑢, 𝑣| ∃𝑞 ∃𝑟 ∃𝑠 ∃𝑡 ∃𝑤 ∃𝑥 ∃𝑦 ∃𝑧
𝐸𝑀𝑃𝐿𝑂𝑌𝐸𝐸 𝑞𝑟𝑠𝑡𝑢𝑣𝑤𝑥𝑦𝑧 𝐴𝑁𝐷 𝑞 =′ 𝐽𝑜ℎ𝑛′
𝐴𝑁𝐷 𝑟 =′ 𝐵′𝐴𝑁𝐷𝑠 = ′𝑆𝑚𝑖𝑡ℎ′
}
Q & A
60

Các file đính kèm theo tài liệu này:

- 4_relational_data_model_section_3_1223.pdf