Relational Calculus

Question 1

First order logic is propositional logic with _________

Answer 1

quantifiers

Question 2

A _____ variable is a variable not defined by a quantifier

Answer 2

free

Question 3

________ queries are queries without free variables

Answer 3

boolean

Question 4

______ defines whether a formula is true or false given a description of the database

Answer 4

semantics

Question 5

What is Codd’s theorem?

Answer 5

Relational Algebra and Relational Calculus have essentially the same expressive power

Question 6

For every _______ ______ E, there is an equivalent relational calculus expression

Answer 6

relational expression

Question 7

When converting from RA to RC, the _________ v function maps each attribute A in the schema to a variable X_A

Answer 7

environment

Question 8

If R is a base relation over A,B
ν={A |→ x_A, B |→ x_B, …}
then R is translated to …

Answer 8

R(x_A,x_B)

Question 9

What are the three steps to convert renaming from RA to RC?

Answer 9

• Translate E to φ
• If there is no mapping for B in ν, add{B |→ x_B}
• Replace every occurrence of ν(A) in φ by ν(B)

Question 10

From RA to RC, projection is translated as…

Answer 10

π_L (E) is translated to∃X φ, where X are attributes that are NOT projected

Question 11

From RA to RC, Selection is translated as…

Answer 11

σθ(E) is translated to φ∧ν(θ), where ν(θ) is obtained from θ by replacing each attribute A by ν(A)

Question 12

Convert σ_(A=B)(R) to RC

Answer 12

R(x_A,x_B)∧x_A=x_B

Question 13

From RA to RC, Cartesian Product is translated as…

Answer 13

conjuction

Question 14

From RA to RC, _____ is translated as disjunction

Answer 14

union

Question 15

From RA to RC, difference is translated as…

Answer 15

A ^ -B

Question 16

Can every RC expression be converted into an RA expression?

Answer 16

NO

Question 17

Whether a RC query is ____ is undecidable

Answer 17

safe

Question 18

The ADOM(R) =

Answer 18

all unique constants occurring in R

Question 19

Only ______ RC can be converted to RA

Answer 19

safe

Question 20

When is RC safe?

Answer 20

Adom(Q(D))⊆Adom(D)

Question 21

From RC to RA, how do you translate predicate symbols?

Answer 21

R(x_1,…,x_n) is translated to ρ_(A_1→ν(x_1),…,A→ν(xn))(R)

Question 22

From RC to RA, how do you translate existential quantification?

Answer 22

∃x φis translated to π_ν(X−{x})(E) where X=free(φ)

Question 23

From RC to RA, how do you translate comparisons?

Answer 23

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))

Question 24

From RC to RA, how do you translate negations?

Answer 24

¬φ is translated into (X_(x∈free(φ))Adomν(x))−E

Question 25

From RC to RA, how do you translate Disjunction?

Answer 25

φ1∨φ2 is translated toE_1x(X_(x∈X2−X1)Adomν(x))∪E2x(X_(x∈X1−X2)Adomν(x))