next up previous contents index
Next: Algebra delle modifiche degli Up: Rappresentazione formale degli schemi Previous: Schema graph ridotto   Indice   Indice analitico


Proiezione sugli schema graph

Dato un insieme F di dipendenze funzionali sugli attributi $ U$ e dato $ X \subseteq U$, la proiezione di F su X è data da $ \pi_X(F) := \{A_1 \to A_2 \in
F^+ \:\vert\: A_1 A_2 \subseteq X\}$. Basandoci sui risultati in [LV03] e [Lec04], in questa sezione dimostreremo che l'operazione di proiezione $ \pi$ è chiusa sugli schema graph. Questo risultato è importante perché ci permetterà di definire con precisione l'effetto della cancellazione di un attributo da uno schema graph.

Il nostro scopo è quello di mantenere il maggior numero di informazioni possibile sulle dipendenze funzionali durante le operazioni di cancellazione degli attributi. Dato che le proiezioni sono definite come un sottoinsieme della chiusura, esistono diverse problematiche sull'applicazione diretta di $ \pi$:

  1. In generale la proiezione di un insieme di dipendenze funzionali coinvolge dipendenze funzionali non semplici, che sono al di fuori del nostro studio
  2. Il risultato della chiusura può crescere esponenzialmente con l'aumentare degli attributi coinvolti.

Lemma 1 ([LV03])   Sia $ U$ un insieme di attributi, $ F$ un insieme di dipendenze funzionali semplici su $ U$, e sia $ A \in U$ ed $ X \subseteq U$ tali che $ X \neq \emptyset$, $ A \notin X$, e $ X \to A \in F^+$. Allora esiste una sequenza di $ n \geq 2$ attributi $ A_1, \ldots, A_n \in U$ tale che $ A_1 \in X$, $ A_n = A$, e $ A_i \to A_{i+1} \in F$, $ 1 \leq i \leq n-1$.

Lemma 2 ([Lec04])   Sia $ U$ un insieme di attributi, $ F$ un insieme di dipendenze semplici su $ U$, ed $ X \subseteq U$. Sia $ F_X = \pi_{X}(F)^0$ e $ F_X' = \{A_1 \to A_2 \in F^* \: \mid \:{} A_1 A_2 \subseteq X\}^-$.
  1. $ F_X$ contiene solo dipendenze funzionali semplici
  2. $ F_X \equiv F_X'$.

Visto il lemma 2, d'ora in avanti daremo per assunto che per un insieme $ F$ di dipendenze funzionali semplici, la proiezione è definita come $ \pi_X(F) := \{A_1 \to A_2 \in F^* \: \mid \:{} A_1 A_2 \subseteq X\}$, che è per definizione un insieme di dipendenze funzionali semplici.

Teorema 1   Sia $ S=(\hat{U}, F)$ uno schema graph, ed $ X \subseteq \hat{U}$ tale che $ E \in X$. Allora $ (X, \{A_1 \to A_2 \in F^* \: \mid \:{} A_1 A_2 \subseteq X\}^-)$ è uno schema graph ridotto.


next up previous contents index
Next: Algebra delle modifiche degli Up: Rappresentazione formale degli schemi Previous: Schema graph ridotto   Indice   Indice analitico
Alessandro Ronchi 2005-07-16