RelationalCalculus

Download Report

Transcript RelationalCalculus

CG096 Advanced Database
Technologies
Lecture 1 [Self Study]
Relational Calculus
Relational Calculus



Declarative language based on predicate logic - checks what is
true in the database rather then looking to get it
The main difference in comparison with the relational algebra is
the introduction of variables which range over attributes or
tuples
Two different variations of the relational calculus:
 domain calculus - specification of formal properties for
different data types, used for describing data
 tuple calculus - querying and checking formal properties of
stored relational data
CG096 Advanced Database Technologies
Relational Calculus
2
Predicate Calculus




Vocabulary of constant names, functional attributes and predicate
properties, used for describing the information
Phrases for specification of constant, functionally dependant or
predicated properties build using proper vocabulary terms
Statements about the world, formulated as meaningful phrases,
connected through logical connectives in logical sentences
 conjunction ()
 disjunction ()
 negation ()
 implication ()
 equivalence ()
Possible quantification of the sentences using existential () or
universal () quantifiers, ranging over variables
Example: All units registered in the database have unit leaders
among the lecturers
(x).(Unit (x)  (y).(Lecturer(y)  Leader(y,x)))
CG096 Advanced Database Technologies
Relational Calculus
3
Relational DB as a Predicate Calculus model



Semantic interpretation of the calculus is given in a set, so either all
type domains of the relational schema (domain calculus), or the set of
all relations in the database (tuple calculus) can serve a model for it
All meaningful sentences in the model are true or false, so the
relation tuples can be interpreted as truthful facts describing the world
The constraints describe logical regularities among the attribute
values, so they can be expressed as logical sentences
Example: All records of unit leaders have primary keys
 Relation names are predicates with a place for each attribute
Leader(Lno:INTEGER,Lname:CHAR,Uname:CHAR) - Lno, Lname and Uname
are attributes of Leader

Data values in the relation tuples are constants from the domains
Leader(2,‘Johnson’,’CS234’) - 2,Johnson and CS234 are constants
forming one Leader tuple

Constraints can be stated using quantified variables over domains
(x)(y,z) .(Leader(x,y,z)) - x stands for the primary key of Leader
CG096 Advanced Database Technologies
Relational Calculus
4
Notes:
1. In predicate calculus sentences contain quantified variables only
2. The sub-expressions following the quantified variables form the
scope of quantification; it is usually closed in round parentheses
Example: The table for unit leaders has foreign keys to both the
lecturers and units tables

Relation names are predicates with place for each attribute
Unit(Uno:INTEGER, Uname:CHAR) - Uno and Uname are attributes of
relation Unit
Lecturer(Lno:INTEGER, Lname:CHAR) - Lno and Lname are attributes of
relation Lecturer
Leader(LUno:INTEGER,Lno:INTEGER,Uno:INTEGER) - LUno, Lno and Uno
are attributes of relation Leader

All foreign key constraints can be stated logically using quantified
sentences, in which variables range over the respective values
( LUno,Uno,Lno).(Leader(LUno,Uno,Lno) 
( Lname).(Lecturer(Lno,Lname)) 
( Uname).(Unit(Uno,Uname))
)
CG096 Advanced Database Technologies
Relational Calculus
5
Relational Calculus as database
query language



Queries are logical expressions, which contain non-quantified (free)
variables for tuples
The free variables are placeholders for the information, we are
looking for from the database relations
The logical expressions, used in the query, are its conditions which
need to be met during answering the query
Example: Who are the employees with salary greater than 40 000?
{e.FNAME,e.LNAME | Employee(e)  e.SALARY > 40 000}

An answer is a replacement of the free variables in the query with
tuple attributes from the relations used to formulate the query
conditions; they should make the statement of the query true in
database (pattern matching)
Answer: James Borg and Jennifer Wallace
Free variables Matching values
e.FNAME
e.LNAME
CG096 Advanced Database Technologies
James
Borg
Jennifer
Wallace
Relational Calculus
6
Notes:
1. The question variables are always listed in front of the
expression, separated by | from the question condition;
2. Question condition can contain free variables only from the list
in the beginning; all other variables should be quantified

Querying related tables requires check of the corresponding keys
for equality
Example: Retrieve the name and address of all employees
who work for the ‘Research’ department
{e.FNAME,e.LNAME,e.ADDRESS |
Employee(e) 
( d).(Department(d) 
d.DNAME = ‘Research’ 
d.DNUMBER = e.DNO
)
}
CG096 Advanced Database Technologies
Relational Calculus
7
Equvalence between relational algebra and
relational calculus



Relational algebra and relational calculus are equivalent with
respect to their ability to formulate queries against relational
databases (Codd 1972)
Relational algebra concentrates on the procedural (“how-to”)
aspects and because of this it is used as an intermediate
language for optimization of database queries
Relational calculus is more appropriate to specify declaratively
the model properties (“what is true”), without worrying about the
way it is achieved and as such it can be used as a specification
or querying language
Note: The relational language Query-By-Example (QBE), which is
developed by IBM during 70ties and is implemented in Paradox
and Access desktop database systems is based on the
relational calculus
CG096 Advanced Database Technologies
Relational Calculus
8