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:
Spis treści
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_iwtedy 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).