Mikrozadanie 12

back

Treść

Napisz wyrażenie algebry relacji (selekcja, rzut, produkt, suma, różnica) wyliczające wynik operacji
$$R:S = \{t\,|\,\{t\} \times S \subseteq R\}$$

Wzorcówka

Najpierw zauważamy, że zapytanie nie ma sensu kiedy $S = \emptyset$, bo wtedy dowolna krotka pasuje do $R:\emptyset$ i wynik nie jest nawet dobrze zdefiniowany w sensie algebry relacji (te krotki mają dowolną arność). Zakładamy więc, że $S \neq \emptyset$.

$$arity(R) = r \\ arity(S) = s \\ Head(X) := \pi_{1, 2, \ldots, r - s} X\\ Missing = (Head(R) \times S) \setminus R\\ R : S := Head(R) \setminus Head(Missing)$$

Najpierw bierzemy wszystkich kandydatów na $t$, czyli prefiksy $R$ odpowiedniej dłguości. Potem liczymy produkt z $S$ i odejmujemy $R$, żeby dostać wszystkie takie krotki, które ,psują’’ nam wynik, i.e. $\{t\,|\,\exists u \in S:\,t \times u \not \in R\}$. Wszyscy pozostali kandydaci działają, więc zwracamy różnicę.

Przykład:

$R = \{ (1, 1), (1, 2), (2, 1), (1, 3) \}$
$S = \{ (1), (2) \}$
$Head(R) = \{ (1), (2) \}$
$Head(R) \times S = \{(1, 1), (1, 2), (2, 1), (2, 2)\}$
$Missing = \{(2, 2)\}$
$Head(Missing) = \{(2)\}$
$R : S = \{(1)\}$

Większy przykład:

$R = \{(1, 1, 1, 1), (1, 1, 1, 2), (2, 1, 1, 1), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 2, 1)\}$
$S = \{(1, 1), (1, 2), (2, 1)\}$
$Head(R) = \{(1, 1), (2, 1), (2, 2)\}$
$Head(R) \times S = \{ \\ \;\;\;\; (1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), \\ \;\;\;\; (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1), \\ \;\;\;\; (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 2, 1) \\\}$
$Missing = \{(1, 1, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1)\}$
$Head(Missing) = \{(1, 1), (2, 1)\}$
$R : S = \{(2, 2)\}$

Uwagi

back