Modyfikacje MLI

Modyfikacje list inwersyjnych mają na celu walkę z dużą redundancją jak prowadzają. Już przy poprzednim temacie jedna z modyfikacji nasuwała się na myśl niejako automatycznie:

Metoda ze zmniejszonym zbiorem list inwersyjnych

Analizując przypadek z zadania 1 z poprzedniego tematu można zauważyć, że nie wszystkie atrybuty (lub ich wartości) są wykorzystywane w wyszukiwaniu, zatem nie dla wszystkich deskryptorów trzeba tworzyć listy inwersyjne. Takie listy są tworzone dla pewnego podzbioru $D' \subset D$ deskryptorów. Taki zbiór $D'$ może być podstawą dla wygenerowania list inwersyjnych w zmniejszonej ilości tylko dla tych deskryptorów, które najczęściej występują w zapytaniach do systemu $S$ lub dla deskryptorów części atrybutów, bądź nawet tylko dla niektórych wartości tych atrybutów. Tworzenie list inwersyjnych $\alpha(d_i)$, dla $d_i \in D' \;$ i $\;\underset{i}\bigcup \ d_i = D'$.

Zadanie pytania do systemu $S$ w postaci termu t będącego sumą termów składowych powoduje uzyskanie odpowiedzi $\sigma(t)$ będącej sumą odpowiedzi na termy składowe.

Przypadek 1: $d_j \in D'$

Jeżeli wszystkie deskryptory pytania $d_j \in D'$, to wyszukiwanie niczym nie różni się od klasycznej metody list inwersyjnych.

$\sigma(t_i) = \alpha(d_1) \cap \alpha(d_2) \cap ... \cap \alpha(d_k), \quad d_j \in D', \quad 1 \leq j \leq k$

gdzie: k – liczba deskryptorów pytania $t_i$.

Przypadek 2: $\underset{j}\bigvee \; d_j \notin D'$

W tym przypadku część deskryptorów nie należy do $D'$, dlatego wyszukiwanie jest dwufazowe. Wpierw znajdujemy obiekty (adresy) odpowiadające tym deskryptorom umieszczonym w dziedzinie $D'$ uzyskując odpowiedź przybliżoną zawierającą zbiór $X_{D'}$.

$X_{D'} = \underset{j \in J}\bigcap \alpha(d_j), \quad J = \{ j : d_j \in D', d_j \in t_i \}$

Jest oczywistym, że $X_{D'} \supseteq X_{t_i}$. Tak otrzymany zbiór obiektów przeglądamy metodą list prostych po pozostałych deskryptorach w celu wyłonienia całkowitej odpowiedzi na zadane do systemu pytanie.

$\sigma(t_i) = X_{t_i} = \{ x \in X_{D'}, \rho_x(a_i) = v_i, (a_i, v_i)=d_i \in t_i \iff d_i \notin D' \}$

Przypadek 3: $\underset{j}\bigwedge d_j \notin D'$

W sytuacji, gdy wszystkie deskryptory pytania nie należą do wydzielonej dziedziny $D'$ to odpowiedź znajdujemy metodą przeglądu zupełnego.

Metoda redukcji liczby list inwersyjnych pozwala znacząco zmniejszyć redundancję, ale kluczowym jest tutaj właściwy dobór które listy inwersyjne są konieczne, a z których można zrezygnować. Dokonanie złego podziału spowoduje co prawda zmniejszenie redundancji w systemie, ale wydłuży czas wyszukiwania, który w krańcowym przypadku może osiągnąć czasy otrzymywane w metodzie list prostych.

Zadanie

Dla Zadania 1 z poprzedniego tematu zaproponuj modyfikację MLI zakładając występowanie pytań wg wzoru:
$t = (Wiek, średni) \cdot (Staż, duży)$,
$t = (Stanowisko, sprzedawca) \cdot (Pensja, średnia)$.
Przeprowadź zapytanie (sformalizuj) typu:
1) Znajdź wszystkich pracowników młodych stażem, zatrudnionych jako handlowiec.
2) Znajdź pracowników posiadających imię na “T” nie pracujących w księgowości.

Metoda dekompozycji obiektowej

Ta modyfikacja ma zastosowanie w systemach o dużej liczbie obiektów opisanych tymi samymi atrybutami, które można podzielić pomiędzy kilkoma mniejszymi systemami (np z powodów uwarunkowań lokalizacyjnych, kategoryzacyjnych itp.).

$S = \underset{i=1}{\overset{n}\bigcup} \; S_i$, gdzie:

$S_i = < X_i, A_i, V_i, \rho_i > \\$ $X_i \subseteq X \quad i \quad \underset{i}\bigcup \; X_i = X \\$ $\rho_i: X_i \times A \to V \\$ $\rho_i = \rho |_{_{X_i}}$

Można wtedy wyróżnić dwa przypadki wpływające na czas wyszukiwania.

Przypadek 1: Pytanie składowe do systemu dotyczy obiektów tylko jednego podsystemu $S_i$

W takiej sytuacji odpowiedź na pytanie znajdujemy w systemie $S_i$:

$\sigma(t_i) = \underset{j}\bigcap \alpha(d_j)|_{_{X_i}}, \; dla \; t_i = d_1 \cdot d_2 \cdot ... \cdot d_k, \quad 1 \le j \le k$

Przypadek 2: Pytanie składowe do systemu dotyczy obiektów z dwu lub więcej podsystemów $S_i, S_2, ..., S_n$

W sytuacji złożonej, gdzie zapytanie dotyczy kilku podsystemów odpowiedź uzyskujemy jako sumę odpowiedzi z podsystemów:

$\sigma(t_i) = \underset{j}\bigcap \alpha(d_j)|_{_{S_1}} \quad \cup \quad \underset{j}\bigcap \alpha(d_j)|_{_{S_2}} \quad \cup ... \cup \quad \underset{j}\bigcap \alpha(d_j)|_{_{S_n}}$

lub

$\sigma(t_i) = \underset{j}\bigcap \alpha(d_j)|_{_{X_1}} \quad \cup \quad \underset{j}\bigcap \alpha(d_j)|_{_{X_2}} \quad \cup ... \cup \quad \underset{j}\bigcap \alpha(d_j)|_{_{X_n}}$

Redundancja

Redundancja w takim systemie opisana jest wzorem:

$\Large R = \frac{ \sum\limits_{i=1}^r \overline{\overline{\alpha(d_i)}}|_{_{X_i}} - N }{N}$, gdzie:

• $r$ – liczba deskryptorów w systemie,
• $N$ – liczba obiektów (lub wskaźników na obiekt).

Metoda dekompozycji atrybutowej

Ten rodzaj dekompozycji jest stosowany w przypadkach gdy można wyróżnić różnych użytkowników systemu stosujących zapytania będące podzbiorem deskryptorów, czyli że każdy z nich “zazwyczaj” pyta o inne cechy (wartości atrybutów) obiektów. Wtedy można stworzyć podsystemy zawierające odpowiednio zawężone podzbiory atrybutów lub wartości atrybutów, przez co zmniejsza się ilość list w podsystemie.

W sytuacji, gdy pytania zadawane do systemu można podzielić na pewne podzbiory deskryptorowe Atrybut-wartość, system $S$ można podzielić na podsystemy zawierające te same obiekty ale inne podzbiory atrybutów. Wtedy system $S = <X, A, V, \rho >$ składa się z podsystemów $S_i$ i powiązany zbiór $D_i$tak, że:

$S = \underset{i}\bigcup \; S_i, \\ S_i = < X, A_i, V_i, \rho_i > \\$ $A_i \subseteq A \quad oraz \quad \underset{i}\bigcup \; A_i = A \\$ $V_i \subseteq V \\$ $\rho_i : X \times A_i \to V_i \\$ $\rho_i = \rho|_{_{X \times A_i}}$

Listy inwersyjne $\alpha_i(d_j), gdzie d_j \in D_i$ tworzone są osobno dla każdego podsystemu $S_i$. Pytania składowe zadajemy do systemu i znajdujemy odpowiedź $\sigma(t)$ będący sumą odpowiedzi na pytania składowe. Tutaj także możemy wyróżnić dwa przypadki:

Przypadek 1:

Zapytanie dotyczy jednego podsystemu:

$t_i = d_1 \cdot d_2 \cdot ... \cdot d_k \quad i \quad d_1, d_2, ...,d_k \in D_i$

wtedy odpowiedź jest przecięciem list inwersyjnych podsystemu $S_i$:

$\sigma(t_i) = \alpha(d_1) \cap \alpha(d_2) \cap ... \cap \alpha(d_k)$.

Przypadek 2:

Zapytanie dotyczy więcej jak jednego podsystemu:

$t_i = d_1 \cdot d_2 \cdot ... \cdot d_k \quad i \quad d_1, d_2, ...,d_n \in D_i, \quad a \; d_{n+1}, ..., d_k \notin D_i$, gdzie $1 \le n \le k$

Odpowiedź na takie pytanie można uzyskać tylko jako przybliżone w systemie $S_i$, a w tak uzyskanym zbiorze odpowiedź dokładną uzyskujemy metodą przeglądu zupełnego lub jako przecięcie (część wspólną) odpowiedzi z kilku podsystemów $S_i$ w których istnieją deskryptory powiązane z pytaniem.

$\sigma(t_i) = \sigma(T_{i_1}) \cap \sigma(t_{i_2}) \cap ... \cap \sigma(t_{i_m})$, gdzie:

$\sigma(t_{i_1}) = (\alpha_1(d_1) \cap \alpha_1(d_2) \cap ... \cap \alpha_1(d_{k_1})|_{_{D_1}}, \quad D_1 \in S_1$, oraz

$\sigma(t_{i_2}) = (\alpha_2(d_1) \cap \alpha_2(d_2) \cap ... \cap \alpha_2(d_{k_2})|_{_{D_2}}, \quad D_2 \in S_2$,

są odpowiednio odpowiedziami na pytanie $t_i$ znalezionymi w podsystemach $S_1 \; i \; S_2$

Należy zauważyć, że liczba deskryptorów $k$ dla pytania $t_i$ w rozbiciu na podsystem $S_1 i S_2$ może być różna. Podsumowując odpowiedź to:

$\large \sigma(t_i) = \bigcap\limits_{j=1}^{m} \sigma(t_{i_j})$,

$\sigma(t_{i_j}) = (\alpha_j(d_1) \cap \alpha_j(d_2) \cap ... \cap \alpha_j(d_{k_j})|_{_{D_j}}, \quad D_1 \subseteq D S_1 \quad i \quad D_j \in S_j$, a m – to liczba podsystemów do których skierowano pytanie.

Redundancja

Ta metoda wnosi dużą redundancję zmniejszoną w podsystemach tylko poprzez zmniejszenie ilości list dla niektórych deskryptorów.

$\Large R = \frac{ \sum\limits_{i=1}^r \overline{\overline{\alpha(d_i)}}|_{_{D_j}} - N }{N}$, gdzie:

• $r$ – liczba deskryptorów w systemie,
• $N$ – liczba obiektów (lub wskaźników na obiekt).

Przykład użycia

Dany jest system $S$ zawierający 20 obiektów odwzorowujących studentów, opisanych atrybutami A1 (płeć), A2 (ukończona szkoła średnia), A3 (średnia ocena), A4 (stypendium), A5 (miejsce zamieszkania) określonych zbiorami wartości:

• $V_{A1} = \{ K, M \}$ – ( kobieta, mężczyzna ),
• $V_{A2} = \{ L, T, Z \}$ – (liceum, technikum, liceum zawodowe ),
• $V_{A3} = \{ N, P, D, B \}$ – ( N ≤ 3 < P ≤ 3.3 < D ≤ 4 < B ),
• $V_{A4} = \{ \varnothing, S, F \}$ – ( nie pobiera, zwykłe, naukowe ),
• $V_{A5} = \{ DS, DR, KP \}$ – (dom studenta, dom rodzinny, kwatera prywatna ).

Dokonano dekompozycji systemu na dwa, z których jeden dedykowano informacjom o kandydatach, drugi o świadczonej pomocy materialnej.

$S_1 = < X, A', V', \rho' > \\ X = \{ x_1, ... , x_{20} \} \\ A' = \{ A1, A2 \} \\ V_{A1} = \{ K, M \} \\ V_{A2} = \{ L, T, Z \} \\ \\ ~\\ S_2 = < X, A'', V'', \rho'' > \\ X = \{ x_1, ... , x_{20} \} \\ A'' = \{ A3, A4, A5 \} \\ V_{A3} = \{ N, P, D, B \} \\ V_{A4} = \{ \varnothing, S, F \} \\ V_{A5} = { DS, DR, KP }$

Utworzono listy inwersyjne dla systemów:

$S_1$:

$\alpha_1(K) = \{ x_1, x_2, x_3, x_8, x_9, x_{12}, x_{18}, x_{19}, x_{20} \}, \\ \alpha_1(M) = \{ x_4, x_5, x_6, x_7, x_{10}, x_{11}, x_{13}, x_{14}, x_{15}, x_{16}, x_{17} \}, \\ \alpha_1(L) = \{ x_1, x_3, x_6, x_{10}, x_{12}, x_{14}, x_{15}, x_{16}, x_{17}, x_{19}, x_{20} \}, \\ \alpha_1(T) = \{ x_4, x_5, x_7, x_8, x_{13} \}, \\ \alpha_1(Z) = \{ x_2, x_9, x_{11}, x_{18} \}$.

$S_2$:

$\alpha_2(N) = \{ x_2, x_4, x_9, x_{10} \}, \\ \alpha_2(P) = \{ x_1 x_3, x_5, x_7, x_{13}, x_{15}, x_{16}, x_{17}, x_{20} \}, \\ \alpha_2(D) = \{ x_6, x_8, x_{11}, x_{14}, x_{18}, x_{19} \}, \\ \alpha_2(B) = \{ x_{12} \}, \\ \alpha_2(\varnothing) = \{ x_4, x_8, x_9, x_{11}, x_{12}, x_{15} \}, \\ \alpha_2(S) = \{ x_1, x_2, x_3, x_5, x_6, x_7, x_{10}, x_{18}, x_{19} \}, \\ \alpha_2(P) = \{ x_{13}, x_{14}, x_{16}, x_{17}, x_{20} \}, \\ \alpha_2(DS) = \{ x_1, x_2, x_3, x_5, x_{11}, x_{13}, x_{15}, x_{19} \}, \\ \alpha_2(DR) = \{ x_4, x_8, x_9, x_{16}, x_{17}, x_{20} \}, \\ \alpha_2(KP) = \{ x_6, x_7, x_{10}, x_{12}, x_{14}, x_{18} \}$.

Do systemu zadano pytanie:

$t_i = (A2, T) \cdot (A3, D) \cdot (A4, \varnothing)$

Odpowiedź na pytanie $t_i$ można znaleźć w podsystemie $S_2$ jako przecięcie list:

$\sigma(t_{i_2}) = \alpha_2(D) \cap \alpha_2(\varnothing)$ co daje w rozpisaniu:

$\sigma(t_{i_2}) = \{ x_6, x_8, x_{11}, x_{14}, x_{18}, x_{19} \} \cap \{ x_4, x_8, x_9, x_{11}, x_{12}, x_{15} \}$, czyli:

$\sigma(t_{i_2}) = \{ x_8, x_{11} \}$

Następnie metodą przeglądu zupełnego sprawdzamy czy w opisach znalezionych obiektów zawierają się pozostałe składowe deskryptory pytania tj.:

$x_8 \leq t_i \quad x_{11} \nleq t_i \Rightarrow \sigma(ti) = {x_8}$

Można też drugi system ($S_1$) przeszukać korzystając z MLI, a wtedy:

$\sigma(t_{i_1}) = \alpha_1(T)$, czyli:

$\sigma(t_{i_1}) = \{ x_4, x_5, x_7, x_8, x_{13} \}$

Obie uzyskane listy obiektów z $S_2 i S_1$ przecinamy przez siebie szukając części wspólnej:

$\sigma(t_i) = \sigma(t_{i_1}) \cap \sigma(t_{i_2})$ i uzyskujemy:

$\sigma(t_i) = \{ x_4, x_5, x_7, x_8, x_{13} \} \cap \{ x_8, x_{11} \}$, co daje nam odpowiedź:

$\sigma(t_i) = \{ x_8 \}$.

Parametry list inwersyjnych

Struktura bazy danych

Struktura bazy danych w metodzie list inwersyjnych jest złożona i wynika z konieczności przechowywania samych opisów obiektów oraz struktury wszystkich list inwersyjnych.

Aktualizacja bazy danych

Aktualizacja opisów obiektów często wymaga usunięcia obiektów z odpowiednich list inwersyjnych, a po dodaniu/zmianie opisu obiektu umieszczeniu odniesień do niego w adekwatnych listach. W zasadzie upraszczając zagadnienie można przyjąć, że zmiana opisu obiektu, usunięcie, czy dodanie nowego wymaga reorganizacji bazy oraz wygenerowania na nowo list inwersyjnych. Poziom skomplikowania procesów związanych ze zmianą bazy danych predestynuje oparte na MLI bazy do przetwarzania wsadowego.

Czas wyszukiwania

Czas wyszukiwania w tej metodzie jest zdecydowanie najkrótszy w odniesieniu do poprzednio poznanych sposobów. W sytuacji zapytania prostego tj. zawierającego sumę deskryptorów to czas znalezienia odpowiedzi jest równy czasowi wygenerowania listy:

$\tau = \tau_g$

W przypadku, gdy pytanie składa się z sumy pytań składowych, czyli takich, które wymagają znalezienia części wspólnej zbiorów, to taki czas określany jest następująco:

$\tau = \sum\limits_{i}(\tau_{g_i} + \tau_{p_i})$, gdzie:

• $\tau_{g_i}$ – czas generowania list,
• $\tau_{p_i}$ – czas przecięcia list (określenia części wspólnej).