Poziom skomplikowania struktury list łańcuchowych nie sprzyja aktualizacji takiego systemu, dlatego też wprowadzono ich modyfikacje celem uproszczenia struktury bądź ułatwienia przeprowadzania aktualizacji.
Wyróżnione modyfikacje list łańcuchowych to:
- Metoda z łańcuchowaniem w tył,
- Metoda z łańcuchowaniem dwukierunkowym (w przód i w tył),
- Metoda z łańcuchowaniem grup obiektów.
Spis treści
Łańcuchowanie w tył
Metoda ta nie wpływa na wyszukiwanie obiektów. Jej modyfikacja wprowadza w zasadzie jedną różnicę w budowie łańcuchów. W Tablicy Zakotwień znajduje się adres ostatniego (zamiast pierwszego) obiektu (n_k = \mu(x^1_k)), a łańcuchy wyglądają analogicznie.
\mathcal{L}(d_i) = \{ n_k - \overline{n}_{k-1} - \overline{n}_{k-2} - ... - \overline{n}_1 \}
Przekształcenia obiektów na ich adres wykonywane są analogicznie za pośrednictwem funkcji adresującej \mu i adresacji względnej (pośredniej, lub absolutnej) omówionej już poprzednio.
\mu(x^i_k) = n_k, \quad \mu(x^i_{k-1}) = n_k - \overline{n}_{k-1}, ... , \mu(x^i_j) = n_k - \overline{n}_j
Z uwagi na brak różnicy w wyszukiwaniu, proces odbywa się identycznie. Stosowanie tej akurat modyfikacji jest ewentualnie uzależnione od sposobu umieszczenia obiektów w bazie danych, co może mieć wpływ na proces aktualizacji. Wygenerowane łańcuchy przybierają zatem postać od ostatniego elementu z offsetem do kolejnych jak w poniższym przykładzie:
\mathcal{L}(M) = \{ 18 - 1 - 2 - 3 - 5 - 8 - 10 - 12 - 13 - 14 - 17 - ø \} \\ \mathcal{L}(K) = \{ 20 - 1 - 6 - 8 - 9 - 11 - 13 - 17 - 18 - ø \}Takie podejście może sprzyjać dodawaniu nowych obiektów do bazy – w tym przypadku wystarczy zaktualizować jedynie tablicę zakotwień.
Łańcuchowanie w przód i w tył
Ta modyfikacja również nie wpływa na sposób wyszukiwania, ale pozwala na szybką lokalizację każdego obiektu np. celem aktualizacji.
Łańcuchowanie grup obiektów
Analizując pytania zadawane do bazy danych nie sposób nie zauważyć, że niektóre ich rodzaje nader często się powtarzają, podczas, gdy niektóre występują nad wyraz rzadko bądź wcale. Celem uproszczenia struktury można założyć, że wydzielenie pewnego podzbioru D_0 \subset D może wpływać upraszczająco dla całości konstrukcji bazy danych, jeśli tylko dla tego podzbioru utworzymy tablicę zakotwień, odsyłacze i listy łańcuchowe d_j \in D_0.
\mathcal{L}(d_j) = \{ n_1 - \overline{n}_2 - \overline{n}_3 - ... - \overline{n}_k \}, \quad d_j \; \in \; D_o, \quad 1 \leq j \leq k
Roztrząsając przykład analogiczny do poprzednich tematów, pytanie do systemu zadajemy w postaci termu t = d_1 \cdot d_2 \cdot ... \cdot d_k .
Możliwe są następujące sytuacje:
- wszystkie deskryptory pytania należą do D_0
Odpowiedź znajdujemy klasycznie jak w metodzie List Łańcuchowych bez modyfikacji. - istnieją deskryptory d_i, które nie należą do D_0
Odpowiedź znajdujemy dla termu przybliżonego t_j \leq t_i zawierającego deskryptory d_j \in D, a w określonym w ten sposób zbiorze X_j \supseteq X_i przybliżonym (odpowiedź przybliżona) wyłaniamy obiekty zgodne z pozostałymi deskryptorami zapytania metodą przeglądu zupełnego: \sigma(t_i) = \{ x_i \in X_j, \bigwedge\limits_{d_i \notin D_0} d_i \in T_{x_i} \to d_i \in t_i \} - wszystkie deskryptory pytania nie należą do D_0
W tej sytuacji odpowiedź jest lokalizowana metodą przeglądu zupełnego wszystkich obiektów bazy danych.
Kryteria określenia które deskryptory będą wzięte pod uwagę w tworzeniu grupy D_0 decydują te same kryteria co przy tworzeniu zbioru D' dla metody list inwersyjnych. Wprowadzone grupowanie upraszcza strukturę bazy danych.
Przykład zastosowania:
W odniesieniu do systemu informacyjnego stworzonego dla MLŁ zgrupujmy deskryptory które dotyczą tylko wykształcenia. Spowoduje to ograniczenie liczby łańcuchów tylko dla deskryptorów: BT, MR, DR, DC, PR. Tak więc wydzielony został zbiór D_0 = \{ (A5, BT), (A5, MR), (A5, DR), (A5, DC), (A5, PR) \}. Oparta na tym tablica zakotwień przyjmuje postać:
| Deskryptor d_i | Adres początkowy | Długość łańcucha |
|---|---|---|
| BT | 2 | 5 |
| MR | 5 | 3 |
| DR | 6 | 7 |
| DC | 8 | 3 |
| PR | 1 | 2 |
Zadane do systemu pytanie przyjmuje postać: t = (A1, M) \cdot (A3, W) \cdot (A5, DC). Analizując pytanie zauważamy, że tylko A5 jest atrybutem dla którego (A5, DC) \in D_0. Odpowiedź znajdujemy:
Z tablicy zakotwień tab(DC) = (8, 3) generujemy łańcuch \mathcal{L}(DC) = \{ 8 - 7 - 8 - ø \}, następnie z tak odnalezionych obiektów będących odpowiedzią przybliżoną na pytanie odnajdujemy zbiór dokładny metodą przeglądu zupełnego:
t_{x_8} \leq t, \qquad t_{x_{15}} \leq t, \qquad t_{x_{16}} \leq t
co daje nam odpowiedź:
\sigma(t) = \{ x_8, x_{15}, x_{16} \}
Zadanie 1:
Dany jest system informacyjny, w którym opisy obiektów są następujące:
X1 = a1*b2*c3*d1
X2 = a2*b1*c4*d2
X3 = a2*b2*c3*d3
X4 = a3*b2*c4*d3
X5 = a3*b2*c4*d1
X6 = a1*b1*c4*d2
Zbuduj KW opartą o metodę list łańcuchowych oraz:
dopisz nowy obiekt x7, o opisie a1*b2*c1*d2 na początku kartoteki (przed x1)
usuń x3
zaktualizuj opis deskryptorowy obiektu x2 – nowy opis ma postać: a1*b1*c4*d1.
Zadanie 2:
Dla tablicy opisów obiektów zaproponuj modyfikację MLŁ i wygeneruj kartotekę wyszukiwawczą, tablicę zakotwień oraz listy łańcuchowe
Znajdź odpowiedź na pytanie o płyty główne posiadające grafikę i umożliwiające zamontowanie 4 kości RAM.
.
Model Socket Chipset RAM gniazda RAM Taktowanie VGA / HDMI ASRock A320M-DVS R4.0 AM4 AMD A320 DDR4 2 3200 Tak MSI A520M PRO AM4 AMD A520 DDR4 2 4600 Tak MSI B450-A PRO MAX AM4 AMD B450 DDR4 4 4133 Tak Gigabyte X570S AERO G AM4 AMD X570 DDR4 4 5400 Tak Gigabyte B550 AORUS PRO AC AM4 AMD B550 DDR4 4 5400 Tak Gigabyte TRX40 AORUS PRO WIFI TR4 AMD TRX40 DDR4 8 4400 Nie ASUS X399 ROG ZENITH EXTREME ALPHA TR4 AMD X399 DDR4 8 3600 Nie ASUS PRIME Z690-A DDR5 s1700 Intel Z690 DDR5 4 6000 Tak MSI MAG Z590 TORPEDO s1200 Intel Z590 DDR4 4 5333 Tak Gigabyte B560 AORUS PRO AX s1200 Intel B560 DDR4 4 3200 Tak Gigabyte X299X AORUS MASTER s2066 Intel X299 DDR4 8 4333 Nie MSI H510M-A PRO s1200 Intel H510 DDR4 2 3200 Tak
Zadanie 3
Wiedząc, że system informacyjny S dotyczący wybranych pozycji literaturowych zadany jest tabelą:
Autor Tytuł Gatunek Wydawnictwo Stan Promocja Pochodzenie Asimov Isaak Fundacja SF Rebis duży nie USA Koontz Dean Mroczne ścieżki serca Sensacja Prima mały nie USA Koontz Dean Ziarno demona Horror Amber średni tak USA Koontz Dean Intensywność Romans Prima duży tak USA Asimov Isaak Narodziny Fundacji SF Rebis mały nie USA Asimov Isaak Druga Fundacja SF Rebis brak nie USA Asimov Isaak Bajki robot?w SF Amber mały nie USA Masterton Graham Tengu Horror Zysk średni tak Wielka Brytania Sheckley Robert Idealna ofiara SF Amber średni tak USA Callison Brian Wojna Trappa Batalistyczny Amber średni nie Wielka Brytania Van Vogt Alfred Elton Producenci broni SF Amber średni tak Kanada Zahn Timothy Triplet SF Amber mały tak USA Norton Andre Zapach magii Fantastyka Amber średni tak USA Norton Andre Smocza magia Fantastyka Amber brak tak USA Wager Walter 58 minut Sensacja Pegasus brak nie USA Curwood James Oliver Najdziksze serca Przygoda Iskry brak nie USA Dębski Eugeniusz Flash Back Kryminał CIA books mały nie Polska Dębski Eugeniusz Upi?r z playbacku Kryminał CIA books mały nie Polska Trepka Andrzej Totem leśnych ludzi Przygoda KAW brak nie Polska Lindgren Astrid Dzieci z Bullerbyn Przygoda Nasza Księgarnia duży tak Szwecja
Zdefiniuj formalnie system oraz zbuduj kartotekę wyszukiwawczą w oparciu o modyfikację metody list łańcuchowych, która zapewni krótki czas wyszukiwania odpowiedzi na pytania o książki określonego gatunku oraz będące aktualnie w promocji. Uzasadnij wybór danej modyfikacji. W zmodyfikowanym przez siebie systemie, przedstaw proces wyszukiwania na pytanie o książki będące w promocji i charakteryzujące się średnią sprzedażą. Oszacuj redundancję i zajętość pamięci zmodyfikowanego systemu.