Relational Model
Tuple Relational Calculus
Copyright By PowCoder代写 加微信 powcoder
Operations of Relational Algebra
Operations of Relational Algebra
Tuple Relational Calculus Basics
Basics: Variables & Range Relations
Expressions
Existential and Universal Quantifiers
Relational Algebra vs. Relational Calculus
RA: Basic operations for relational model
RC: Higher-level declarative language for specifying relational queries
Relational Algebra and Relational Calculus are equivalent in expressive power
Any relational algebra expression can be written as a relational calculus expression and vice versa
Why study both?
Both help us get a deeper understanding of relational models
Both have impacted development of SQL
Relational Calculus provides a different viewpoint – formal logic
Relational Calculus Basics
Relational Calculus is based on the idea of First Order Logic
Declarative, not procedural
Not even a hint of “how” to perform the operation, only a declaration of what is wanted
i.e. table JOINs in relational algebra
Basic form of query:
{t | COND(t)}
t is a tuple variable
COND(t) is a boolean conditional expression
Evaluates to TRUE or FALSE for every tuple t
Relational Calculus Basics
Result of query – all tuples that satisfy the conditional expression COND(t)
Ex: Find all employees whose salary is more than $50,000:
{t | EMPLOYEE(t) AND t.Salary>50000}
Relational Calculus Basics
Ex: Find all employees whose salary is more than $50,000:
{t | EMPLOYEE(t) AND t.Salary>5000}
attributes
Selection condition
Range relation – states that the tuple t is a member of the relation EMPLOYEE
True for tuples that are in EMPLOYEE, false otherwise
Attributes may be entire tuple (as here)
Can also select specific attributes
Relational Calculus Basics
Another example:
Retrieve birth date and address of employees who have the name “ . Smith”
{ | EMPLOYEE(t) AND t.Fname=‘John’ AND t.Minit=‘B’ AND t.Lname=‘Smith’}
Here only birthdate and address attributes are retrieved
t.Bdate, t.Address
Expressions
An expression in tuple relational calculus can be generally expressed as:
Where each “t” denotes a tuple variable, each “A” denotes an attribute of that tuple variable, and COND is a formula
A formula is a boolean expression, composed of one or more atoms connected via logical operators (AND, OR, NOT)
Atom – a single element of a formula of one of the following:
R(t) – R is a relation name, t is a tuple variable
Range relation – TRUE when t is a tuple in relation R
ti.A op tj.B – where op is a comparison operator (i.e. >, <, =, etc.), ti and tj are tuple variables and A and B are tuple attributes
ti.A op c – where op is a comparison operator (i.e. >, <, =, etc.), ti and tj are tuple variables, A is a tuple attribute , and c is a constant
Formula - Atoms
A few sample Atoms:
EMPLOYEE(t)
t.Fname=‘John’
t.Salary < 50000
DEPARTMENT(t2)
t.Dno=t2.Dnumber
t2.Dname=‘Research’
Note that each Atom individually evaluates to either TRUE or FALSE
A formula is a boolean expression, composed of one or more atoms connected via logical operators (AND, OR, NOT)
Defined by two rules:
Every Atom is a Formula
If F1 is a formula and F2 is a formula, then the following are all formula:
(F1 AND F2)
(F1 OR F2)
A few sample formula:
EMPLOYEE(t) AND t.Fname=‘John’
EMPLOYEE(t) AND t.Salary < 50000
EMPLOYEE(t) AND t.Fname=‘John’ OR t.Salary<50000
DEPARTMENT(t2)
DEPARTMENT(t2) AND t.Dno=t2.Dnumber AND t2.Dname=‘Research’
Note that each formula evaluates to TRUE or FALSE
Formula – Quantifiers
Relational calculus gives us more power than just manipulating individual tuples and attributes
Can talk about the existence of tuples
Can talk about whether something is true for all tuples
For these ideas we have two new operators:
Universal quantifier: - read as “For All”
Existential quantifier: - read as “There Exists”
Formula – Universal Quantifier
The formula is TRUE if every possible value in F makes F TRUE
∀x(x2≥0), i.e., the square of any number is not negative
∀x∀y(x+y=y+x), i.e., the commutative law of addition.
i.e. “For all t F is true”
Formula – Existential Quantifier
A sentence ∃t F is true if and only if there is at least one value that makes F true.
∃x(x≥x2) is true since x=0 is a solution. There are others.
∃x∃y(x2+y2=2xy) is true since x=y=1 is one solution.
i.e. “There exists a t such that F is true”
Formula – Quantifiers
Quantifiers are meaningless unless they are “bound” to a tuple variable
“bound” variables – variables attached to a quantifier
“free” variables – variables that are not “bound”
(t)(d.Dnumber=t.Dno)
d is a free tuple variable, t is bound by the existential quantifier
(d)(d.Mgr_ssn=‘333445555’)
d is bound by the universal quantifier
Formula – Quantifiers
Extend our definition of formula by
If F is a formula, than so is (t)(F), where t is a tuple variable.
A sentence t(F) is TRUE if there is at least one tuple that can be assigned to the occurrences of t in F makes F TRUE.
If F is a formula, then so is (t)(F), where t is a tuple variable.
A sentence ∀t(F) is true if and only if F is true no matter what value is substituted for t.
COMPANY DB:
List the name and address of all employees who work for the ‘Research’ Department:
Note our “join” and “selection” conditions
Note free (t) and bound (d) tuple variables
Compare it with:
Π fname, lname, address (σ d.Dname=‘Research’ AND d.Dnumber=t.Dno (EMPLOYEE X DEPARTMENT))
{t.Fname, t.Lname, t.Address | EMPLOYEE(t) AND (d)(DEPARTMENT(d) AND d.Dname=‘Research’ AND d.Dnumber=t.Dno)}
S (EMPLOYEE) X (DEPARTMENT)
For every project located in ‘Stafford’, list the project number, controlling department number, and the department manager’s last name and DOB:
Note our “join” and “selection” conditions
Note free (m,p) and bound (d) tuple variables
Same query written in relational algebra:
{p.Pnumber, p.Dnum, m.Lname, m.Bdate | PROJECT(p) AND EMPLOYEE(m) AND p.Plocation=‘Stafford’ AND (d)(DEPARTMENT(d) AND p.Dnum=d.Dnumber AND d.Mgr_ssn=m.Ssn)}
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com