Relational Calculus Flashcards
First order logic is propositional logic with _________
quantifiers
A _____ variable is a variable not defined by a quantifier
free
________ queries are queries without free variables
boolean
______ defines whether a formula is true or false given a description of the database
semantics
What is Codd’s theorem?
Relational Algebra and Relational Calculus have essentially the same expressive power
For every _______ ______ E, there is an equivalent relational calculus expression
relational expression
When converting from RA to RC, the _________ v function maps each attribute A in the schema to a variable X_A
environment
If R is a base relation over A,B
ν={A |→ x_A, B |→ x_B, …}
then R is translated to …
R(x_A,x_B)
What are the three steps to convert renaming from RA to RC?
- Translate E to φ
- If there is no mapping for B in ν, add{B |→ x_B}
- Replace every occurrence of ν(A) in φ by ν(B)
From RA to RC, projection is translated as…
π_L (E) is translated to∃X φ, where X are attributes that are NOT projected
From RA to RC, Selection is translated as…
σθ(E) is translated to φ∧ν(θ), where ν(θ) is obtained from θ by replacing each attribute A by ν(A)
Convert σ_(A=B)(R) to RC
R(x_A,x_B)∧x_A=x_B
From RA to RC, Cartesian Product is translated as…
conjuction
From RA to RC, _____ is translated as disjunction
union
From RA to RC, difference is translated as…
A ^ -B
Can every RC expression be converted into an RA expression?
NO
Whether a RC query is ____ is undecidable
safe
The ADOM(R) =
all unique constants occurring in R
Only ______ RC can be converted to RA
safe
When is RC safe?
Adom(Q(D))⊆Adom(D)
From RC to RA, how do you translate predicate symbols?
R(x_1,…,x_n) is translated to ρ_(A_1→ν(x_1),…,A→ν(xn))(R)
From RC to RA, how do you translate existential quantification?
∃x φis translated to π_ν(X−{x})(E) where X=free(φ)
From RC to RA, how do you translate comparisons?
x op y is translated to σ_(ν(x) op ν(y) (Adomν(x)×Adomν(y)) and
x op c is translated to σ_(ν(x) op c) (Adomν(x))
From RC to RA, how do you translate negations?
¬φ is translated into (X_(x∈free(φ))Adomν(x))−E
From RC to RA, how do you translate Disjunction?
φ1∨φ2 is translated toE_1x(X_(x∈X2−X1)Adomν(x))∪E2x(X_(x∈X1−X2)Adomν(x))
