Relational Algebra Practice Questions

To optimize the given query $\Pi _{c-name}(\sigma _{b-city="Agra" \wedge bal < 0} (branch \Join (account \Join depositor)))$, we apply the principle of pushing selections as deep as possible into the expression tree to minimize the size of intermediate relations.

1. Reduce $branch$: Apply $\sigma_{b-city="Agra"}$ to the $branch$ relation first, as $branch$ is small, significantly reducing the tuples involved in subsequent joins.
2. Join with $account$: Join the filtered $branch$ with the $account$ relation. This results in only those $account$ tuples belonging to branches in "Agra".
3. Filter and Join: Apply $\sigma_{bal < 0}$ to the result of this join, further reducing the dataset.
4. Final Join: Finally, join the reduced result with the large $depositor$ relation. This sequence minimizes the number of tuples involved in the join with the largest relation, $depositor$.

This process corresponds to the algebraic expression: $\Pi _{c-name} (\sigma_{bal < 0} (\sigma_{b-city="Agra"} branch \Join account) \Join depositor)$.

The join $r_1 \Join r_2$ is performed on the common attribute $R$.
In relation $r_2$, $R$ is the primary key, meaning each value of $R$ appears at most once.
Consequently, for each of the 2000 tuples in $r_1$, there can be at most one matching tuple in $r_2$ that shares the same $R$ value.
Therefore, the maximum number of tuples produced by the join is limited by the cardinality of $r_1$.
Since $|r_1| = 2000$, the maximum size of the join is 2000.

For any relation instance $r$ and projections $r_1 = \Pi_{A,B,C}(r)$ and $r_2 = \Pi_{A,D}(r)$, the natural join $s = r_1 * r_2$ always satisfies $r \subseteq s$, as the join of projections can only ever reconstruct $r$ or add extraneous tuples. A decomposition is defined as lossy when the join operation produces tuples that were not in the original relation, implying $r \neq s$. Given that $r \subseteq s$ and $r \neq s$, it follows that $r$ is a proper subset of $s$, denoted as $r \subset s$. Thus, the property $r \subset s$ correctly characterizes a lossy decomposition.

The referential integrity constraint ensures that every value of the foreign key $C$ in relation instance $r_1$ must exist as a value of the primary key $D$ in relation instance $r_2$.
Formally, this constraint is expressed as the set inclusion: $\Pi_C(r_1) \subseteq \Pi_D(r_2)$.
The relational algebra expression in option B is $\Pi_C(r_1) - \Pi_D(r_2)$.
In set theory, for any two sets $X$ and $Y$, if $X \subseteq Y$, then the set difference $X - Y$ results in the empty set $\emptyset$.
Since $\Pi_C(r_1)$ is a subset of $\Pi_D(r_2)$, the expression $\Pi_C(r_1) - \Pi_D(r_2)$ necessarily results in an empty relation.

To analyze the given relational algebra expression:

1. Left Expression: $\Pi_{name} (\sigma_{sex=female} (Student))$ retrieves the set of names of all female students.
2. Right Expression: The term $\Pi_{name} (\sigma_{sex=female \land x=male \land marks \leq m} (Student \times \rho_{n,x,m}(Student)))$ identifies the set of all female students who have marks less than or equal to ($marks \leq m$) at least one male student.
3. Set Difference: The operation performs a set difference: {All female students} $-$ {Female students with marks $\leq$ at least one male student}.
4. Result: By removing all females who have marks less than or equal to any male student, we are left with only those female students whose marks are strictly greater than the marks of all male students.

Codd's Theorem establishes that relational algebra and relational calculus have equivalent expressive power if and only if the calculus expressions are "safe." Unrestricted relational calculus allows for expressions that generate infinite relations, such as $\{ t \mid \neg(t \in R) \}$, which cannot be represented by finite relational algebra operations. Safe relational calculus restricts queries to those that result in a finite set of tuples defined over the active domain of the database. Therefore, the expressive power of relational algebra is exactly equal to that of safe relational calculus.

Relational algebra operations, such as selection ($\sigma$), projection ($\pi$), and join ($\bowtie$), are equivalent to First-Order Logic ($FO$). Options A, B, and C involve fixed-length queries: A uses $\sigma_{X=c}(Adj)$, B uses $\sigma_{X=Y}(Adj)$, and C uses joins like $Adj(X, Y) \bowtie Adj(Y, X)$ to detect small cycles. However, option D requires finding the Transitive Closure of the graph to determine all reachable vertices. It is a fundamental theorem in database theory that Transitive Closure is not expressible in standard relational algebra because it requires recursion or a fixed-point operator, which cannot be captured by a query of constant length for a graph of arbitrary size.

The relational algebra property $\sigma_{C}(r \Join s) = \sigma_{C}(r) \Join s$ holds whenever the selection condition $C$ involves only attributes present in relation $r$. In this expression, the condition $C$ is $A=a$. Since the attribute $A$ belongs to the relation scheme $R$ (the schema of $r$), the condition relies solely on attributes of $r$. Consequently, the selection operation can be pushed inside the join operation. Therefore, $\sigma_{A=a}(r \Join s) = \sigma_{A=a}(r) \Join s$.

The relational algebra expression $\pi_{A_1} (\sigma_{C_1} (R_1))$ is valid because the selection condition $C_1$ is applied to $R_1$ before the projection, ensuring all necessary attributes for $C_1$ are present. However, the expression $\sigma_{C_1} (\pi_{A_1} (R_1))$ is incorrect if the condition $C_1$ references attributes of $R_1$ that are not included in the set $A_1$. Because the projection $\pi_{A_1}$ removes attributes not in $A_1$, the subsequent selection $\sigma_{C_1}$ cannot access them, making the right-hand side operation invalid. Therefore, the transformation $\pi_{A_1} (\sigma_{C_1} (R_1)) \to \sigma_{C_1} (\pi_{A_1} (R_1))$ is not universally equivalent.

This question is an example of Theta Join , $r \bowtie_\theta s= \sigma_\theta(r \times s)$ The join here will be selecting only those tuples where $A = C$ and $B = D,$ meaning it is the intersection. D option.

Division operator is used for 'for all' type queries.