Midterm 1

Aufgabe 1

(a)

• entity Games:
• attribute year key
• attribute place
• entity Athlete:
• attribute name key
• entity Discipline:
• attribute name key
• relationship gold medal:
• Athlete functionality 1
• Discipline functionality 1
• Games functionality 1
• relationship silver medal:
• Athlete functionality 1
• Discipline functionality 1
• Games functionality 1
• relationship bronze medal:
• Athlete functionality 1
• Discipline functionality 1
• Games functionality 1

(I think the functionalities for the medal relationships should be: Games functionality M Discipline functionality N Athlete functionality 1

An athlete could win the same discipline in different games or could win in different disciplines. )

Alternative Solution:

+----------------+                +----------------+
|                |1    (Weak)    N|                |
|      Games     +----------------+   Discipline   |
|                |                |                |
+----------------+                +----------------+
N|   N|    N|
|    |     |
+------+    +     +-------+
Bronze       Silver       Gold
+            +            +
|            |            |
|            |            |
|           1|            |
|      +----------------+ |
|     1|                | |
+------+    Athlete     +-+
|                |1
+----------------+

Comment: This alternative solution does not make much sense to me. What is when we have new Games all 4 years we additionally want to create all disciplines again? No we just want to assign the disciplines we want to use this games. So The Gold Silver Bronze should obvs handled in a way like this: Gold: Games_id x Discpline -> Athlth_id , Silver: Ditto, Bronze ditto. As someone above already noted.

Attributes:

Game: year, place Discipline: name Athlete: name

Discipline is a weak entity which only exists together with Game. Thus the key of Discipline is (name, year). The key of Games is year, and the key of Athlete is name.

(b)

• Games: ${\displaystyle \{({\underline {\text{year: int}}},{\text{place: string}})\}}$
• Athlete: ${\displaystyle \{({\underline {\text{name: string}}})\}}$
• Discipline:${\displaystyle \{({\underline {\text{name: string}}})\}}$
• Gold:$\displaystyle \{(\text{year: int, a_name: string, d_name: string})\}$
• Silver:$\displaystyle \{(\text{year: int, a_name: string, d_name: string})\}$
• Bronze: $\displaystyle \{(\text{year: int, a_name: string, d_name: string})\}$

The key for the medals is any pair of attributes, or the whole triple.

Alternative Solution (according to figure from a)

• Games: ${\displaystyle {\text{participates}}\div \Pi _{\text{Year}}(\sigma _{\text{isSummer}}({\text{Games}})}$
• Athlete: ${\displaystyle C{\text{ magic operator here }}(\sigma _{\text{equal attributes must be equal}}(A\times B)}$
• Discipline:$\displaystyle \{(\underline{\text{name: string, year: int}} \text{, bronce_athlete: string, silver_athlete: string, gold_athlete: string})\}$

All the relationships from the figure above got merged into Discipline, as they are 1:N.

Aufgabe 2

• B(b (key))
• C(c (key))
• D(c, d (both constitute key))
• R(D.c, D.d, C.c, B.b, R.r) (key are either both attributes from D and from C or both attributes from D and from B)

Midterm 2

Aufgabe 1

(a)

$\displaystyle \Pi_\text{Location}(\sigma_{\text{Name}=\text{"John Doe"}}(\text{participates}\bowtie \text{Games}))$

(b)

${\displaystyle T{\text{'leftOuterJoin'}}C=(T\bowtie C)\cup ((T-\pi _{T.a,T.b.T.c}(T\bowtie C))\times \{(\omega )\})}$

(c)

${\displaystyle \omega }$

Aufgabe 2

It is not clear to me, how the six base operators can be used to create NULL values in a schema. That is meant with the magic operator. ${\displaystyle \pi _{...}}$

Suggestion according to Wikipedia: [1]:

${\displaystyle \sigma _{...}}$

${\displaystyle \times }$

${\displaystyle \Pi _{\text{number}}({\text{Departement}})-\Pi _{\text{number}}(\sigma _{{\text{Employee.salary }}>{\text{ Manager.salary}}}({\text{Departement}}\times {\text{Employee}}\times \rho _{\text{Manager}}({\text{Employee}})))}$ where ${\displaystyle \Pi _{\text{number}}({\text{Departement}})-\Pi _{\text{number}}(\sigma _{{\text{ E.salary}}>{\text{M.salary}}}({\text{Departement D}}\bowtie _{{\text{ D.number}}={\text{E.departement}}}{\text{Employee E}}\bowtie _{{\text{ D.manager}}={\text{M.name}}}{\text{Employee M}}))}$ denotes a NULL value.

As far as I know the Join operator is not a basic operator, therefore it has to be replaced by ${\displaystyle \alpha \rightarrow \beta ,\alpha }$, ${\displaystyle \alpha \rightarrow \beta }$ and ${\displaystyle A\neq \alpha \subset A}$, analogue to the replacement in T

Aufgabe 3

(a)

Possible Solution:

INSERT INTO Participants (
SELECT S.Year as Year, P.Name as Name
FROM Participants P, Games G, Games S
WHERE
G.Year = P.Year AND
G.IsSummer = No AND
G.Location = "Vancouver" AND
S.Location = "Sotchi" AND
S.IsSummer = NO
)

Explanation: The first 3 conditions in the WHERE part just do a normal join to get all the participants of the winter games in vancouver. For the insert we still need the year of Sotchi. So by selecting from Games a second time we do a cross product. By restricting this second Games relation to S.Location = "Sotchi" and S.IsSummer = NO we have only all the participants from Vancouver combined with the information about Sotchi.

INSERT INTO Participants (
SELECT (SELECT Year FROM Games WHERE Location = "Sotchi" AND IsSummer=No) as Year, P.Name as Name
FROM Participants P, Games G
WHERE
P.Year = G.Year AND
G.Location = "Vancouver"
)

(b)

WITH summergames AS (SELECT p.name AS Name, count(*) AS count
FROM Participates p, Games g
WHERE g.isSummer
GROUP BY p.name)
WITH wintergames AS (SELECT p.name AS Name, count(*) AS count
FROM Participates p, Games g
WHERE NOT g.isSummer
GROUP BY p.name)
SELECT s.Name
FROM summergames s, wintergames w
WHERE s.count > w.count
s.Name  = w.Name

Endterm

Aufgabe 1

(b)

create table Person (
name varchar primary key
age numeric(3,0) not null
check (age >= AND age < 150) # empirical value
)
create table Group (
name varchar primary key
)
create table Year (
value int primary key
)
create table Country (
name varchar primary key
)
create table City (
name varchar
country_name varchar foreign key references Country on update cascade on delete cascade
primary key (name, country)
)
create table Member_of (
person_name varchar foreign key references Person on update cascade on delete cascade
group_name varchar foreign key references Group on update cascade on delete cascade
Year_no int foreign key references Year on update cascade on delete cascade
)

create table travels_to (
group_name varchar foreign key references Group on update cascade on delete cascade
year_no int foreign key references Year on update cascade on delete cascade
city_name varchar foreign key references City on update cascade on delete cascade
country_name varchar foreign key references City on update cascade on delete cascade
)

Aufgabe 2

(a)

${\displaystyle A':=A-(\beta -\alpha )}$

Does not work, because we don't only consider managers from the employees departement!

Alternative: ${\displaystyle \alpha \rightarrow \beta }$

(b)

SELECT number
FROM Department
EXCEPT
(SELECT DISTINCT d.number
FROM Department d, Employee e, Employee m
WHERE d.number = e.department AND
m.name = d.manager AND
e.salary > m.salary);

Aufgabe 3

(a)

A candidate key is a set of attributes that contains all attributes in its closure wrt FDs. Since we are no FDs given the only way to get all attributes is to take them all as key.

(b)

A relation is in BCNF iff for every nontrivial ${\displaystyle \beta }$ is a superkey. Assume R is not in BCNF, then there is such an ${\displaystyle \alpha }$ with ${\displaystyle A'\rightarrow \beta }$. Set ${\displaystyle \alpha }$. A' is not A, because ${\displaystyle A'\rightarrow \beta \cup A'=A}$ isn't trivial, ${\displaystyle A'}$ not subset of ${\displaystyle \alpha _{1},\alpha _{2},...\subset A}$. Then ${\displaystyle \neq A}$ (because ${\displaystyle \rightarrow }$ remains in A). But then ${\displaystyle \rightarrow }$ and ${\displaystyle T_{k}}$ would be a key, in contradiction to a).

(a, alternative)

A key is defined as a minimal set of attributes on which all other attributes are functionally dependent.

Assume there is another key k of R. Then, k = ${\displaystyle T_{k}}$, and k ${\displaystyle w_{1},w_{2},...,w_{n}}$. But then, A is not minimal; it could be reduced to k. Proof by contradiction.

Aufgabe 4

• ABE

(b)

• It is not possible to check for 1NF because the domains are unknown
• It is not in 2NF because the attribute C is not minimally dependent on the key ABE, but only on B.

(c)

Computing the minimal basis yields the FDs:

• B ${\displaystyle T_{1}\rightarrow T_{2}\rightarrow ...\rightarrow T_{n}}$ CD
• AD ${\displaystyle r\cdot e*s+s}$ B

Now we create the tables X(B, C, D), Y(A, B, D) and Z(A, B, E). The first two are formed from the FDs in the minimal basis. Z is needed because none of the keys found in (a) is contained in X and Y.

Aufgabe 5

(a)

A cycle in the serialisability graph arises from 4 operations (2 in each transaction) which conflict with each other. But all transactions have only one operation that can possibly conflict, so it is not possible to form a cycle in the graph. Therefore every history consisting of such transactions is serialisable.

(a, alternative)

A history of many consecutive transactions with only writes to the same tupel is equivalent to all histories with the same write in last position, as this is the only change between before and after. So of course it is serializable; it is equivalent to any serial history with ${\displaystyle T_{k}}$ in last position, where ${\displaystyle T_{k}}$ is the transaction writing last.

I don't know whether we can use this definition of equivalence (namely, "equivalent iff reads give same result and endstate is the same"). If not:

The position of the commits doesn't matter for serializability (as long as they are after their respective writes :P), so any such history ${\displaystyle w_{1},w_{2},...,w_{n}}$ is equivalent to ${\displaystyle T_{1}\rightarrow T_{2}\rightarrow ...\rightarrow T_{n}}$.

(b)

One cannot assume that the write operation is executed atomically. Thus it would not be guaranteed that the thread that performs the first step of the operation first also finishes first (mind the scheduler).

Aufgabe 6

(a)

• Compute the nested query first. Do a table scan filtering the correct tuples and project them to the attribute S.c.
• Scan R and check for each tuple whether the b attribute is contained in the precomputed table. If so, mark the tuple
• For each marked tuple the a field is set to 5.

(b)

Let r, s denote the respective table sizes and e denote the selectivity.

• nested table scan: s comparisons.
• iteration of R: r * s *e comparisons.

That yields ${\displaystyle r\cdot e*s+s}$ comparisons in total.