System informacyjny S = < X, A, V, \rho > przechowuje obiekty w dowolnej kolejności. Istnieje funkcja adresacji \mu przyporządkowująca adresy numeryczne wszystkim obiektom zbioru X :
\mu: X \to N
gdzie: N – to zbiór liczb naturalnych.
Analogicznie jak w przypadku list inwersyjnych zachodzi zależność:
\mu(x) = \mu(y) \quad \iff \quad t_x = t_y
W takim systemie S dla każdego deskryptora d_i = ( a_i, v_i ) \in D tworzymy listę:
\mathcal{L}(d_i) = \{n_1 - \overline{n}_2 - ... - \overline{n}_n \}
gdzie: n_1 = \mu(x^i_1) jest adresem pierwszego wystąpienia obiektu zawierającego w swoim opisie deskryptor d_i , a kolejne są referencjami względnymi (odsyłaczami w adresacji pośredniej względem obiektu bazowego x_1 o adresie n_1 ). Tak stworzona lista \mathcal{L}(d_i) jest listą łańcuchową deskryptora )d_i. Bazując na liście można łatwo określić adresy obiektów zawierających w swoim opisie deskryptor d_i :
\mu(x^i_1) = n_1, \quad \mu(x^i_2) = n_1 + \overline{x}_2, \quad ... , \quad \mu(x^i_j) = n_1 + \overline{n}_j
gdzie: x^1_j to j-ty obiekt zawierający w swoim opisie deskryptor d_i .
UWAGA: Można także alternatywnie ustalić adresację obiektów posługując się adresem pośrednim pomiędzy dwoma kolejnymi obiektami x_i zawierającymi d_i – w ten sposób wyznaczanie adresu każdego obiektu w systemie polega na zsumowaniu adresów wszystkich poprzedzających go elementów należących do danej listy łańcuchowej \mathcal{L}(d_i).
Tak określone listy łańcuchowe nie są jednakże pamiętane w systemie. System przechowuje opisy obiektów x wraz z odnośnikami do kolejnych obiektów ze zgodnym deskryptorem; oraz tworzona jest tablica zakotwień list łańcuchowych, gdzie przechowuje się informację o pierwszym adresie obiektu zawierającym poszukiwany deskryptor i długość listy łańcuchowej dla tego deskryptora.
tab(d_1) = \lgroup n_1, \overline{\overline{\mathcal{L}(d_i)}} \rgroup dla d_i \in D
gdzie: n_1 = \mu(x^i_1) .
Spis treści
Wyszukiwanie w systemie
Do systemu S zadajemy pytanie t będącego sumą termów składowych t = t_1 + t_2 + ... + t_m, a odpowiedź jest sumą odpowiedzi na termy składowe.
Przypadek 1
Jeśli pytaniem jest term prosty t_i = d_i to odpowiedź uzyskujemy odnajdując w tablicy zakotwień adres pierwszego obiektu będącego odpowiedzią na pytanie oraz moc (liczebność) zbioru (n_1, \overline{\overline{\mathcal{L}(d_i)}} ). Generując listę łańcuchową dla tego deskryptora uzyskujemy dostęp do wszystkich obiektów posiadających go w swoim opisie.
Przypadek 2
W sytuacji, gdy pytaniem jest term złożony t_1 = d_1 \cdot d_2 \cdot ... \cdot d_k poszukiwanie rozpoczynamy od znalezienia wszystkich inicjatorów list łańcuchowych w tablicy zakotwień dla deskryptorów będących częścią termu. Następnie wybieramy łańcuch \mathcal{L_{min}} o najniższej liczebności.
\mathcal{L}_{min}(d_i) = \underset{d_i}{min} \{\overline{\overline{\mathcal{L}(d_1)}}\}
Następnie możliwe są dwa scenariusze postępowania:
Przegląd zupełny obiektów x_i wchodzących w skład najkrótszej listy łańcuchowej celem zweryfikowania, które obiekty z listy posiadają zgodność dla pozostałych deskryptorów pytania.
\sigma(t_i) = \{ x_i \in \mathcal{L}_{min}(d_i)\mathcal{\&} \quad \underset{d_j \in t_i}\bigwedge d_j \neq d_i \Rightarrow d_j \in t_{x_i} \}
Przecięcie list łańcuchowych dla pozostałych deskryptorów z wybraną, najkrótszą listą łańcuchową obiektów celem określenia zbioru obiektów z części wspólnej przecięcia tych list.
\sigma(t_i) = \{ x_i \in \lgroup \mathcal{L}_{min}(d_i) \cap ( \underset{j}\bigcap \; \mathcal{L}(d_j)) \rgroup, d_i, d_j \in t_{x_i} \}
Przykład wyszukiwania
Odnosząc się do naszego flagowego przykładu bazy informacyjnej dokonajmy jej przekształcenia do list łańcuchowych. Taka kartoteka wtórna może przyjąć postać:
| Adres obiektu | Opis obiektu | Odsyłacze | Adres obiektu | Opis obiektu | Odsyłacze | |
|---|---|---|---|---|---|---|
| x_{1} | M | +3 | x_{11} | K | +10 | |
| b | +2 | b | +11 | |||
| W | +4 | W | +13 | |||
| D | +4 | D | +13 | |||
| PR | +16 | DR | +8 | |||
| x_{2} | K | +1 | x_{12} | K | +12 | |
| c | +4 | b | +12 | |||
| S | +2 | S | +11 | |||
| A | +1 | T | +9 | |||
| BT | +1 | BT | +11 | |||
| x_{3} | K | +5 | x_{13} | M | +14 | |
| b | +4 | b | +13 | |||
| PR | ø | S | ø | |||
| A | ø | T | ø | |||
| BT | +2 | BT | ø | |||
| x_{4} | M | +4 | x_{14} | K | +17 | |
| a | ø | b | +17 | |||
| S | +10 | W | +14 | |||
| T | +8 | D | +14 | |||
| BT | +10 | DR | +12 | |||
| x_{5} | M | +5 | x_{15} | M | +15 | |
| b | +8 | c | +14 | |||
| W | +5 | W | +15 | |||
| D | +5 | D | +15 | |||
| MR | +5 | DC | +8 | |||
| x_{6} | M | +7 | x_{16} | M | +16 | |
| c | +5 | c | +15 | |||
| W | +6 | W | +16 | |||
| D | +6 | D | +16 | |||
| DR | +1 | DC | ø | |||
| x_{7} | K | +7 | x_{17} | M | +17 | |
| c | +6 | c | ø | |||
| W | +7 | W | +17 | |||
| D | +7 | D | +17 | |||
| DR | +3 | PR | ø | |||
| x_{8} | M | +9 | x_{18} | M | ø | |
| c | +13 | b | +18 | |||
| W | +8 | W | +18 | |||
| D | +8 | D | +18 | |||
| DC | +7 | DR | +14 | |||
| x_{9} | K | +9 | x_{19} | K | +18 | |
| b | +9 | b | +19 | |||
| W | +9 | W | +19 | |||
| D | +9 | D | +19 | |||
| DR | +5 | MR | ø | |||
| x_{10} | M | +12 | x_{20} | K | ø | |
| b | +10 | b | ø | |||
| W | +10 | W | ø | |||
| D | +10 | D | ø | |||
| MR | +14 | DR | ø |
Dla uproszczenia przyjęto, że numer obiektu jest jego adresem. Na podstawie kartoteki wtórnej jesteśmy w stanie wygenerować listy łańcuchowe i przybiorą one postać:
- \mathcal{L}(M) = {1 – 3 – 4 – 5 – 7 – 9 – 12 – 14 – 15 – 16 – 17 – ø},
- \mathcal{L}(K) = {2 – 1 – 5 – 7 – 9 – 10 – 12 – 17 – 18 – ø},
- \mathcal{L}(a) = {4 – ø},
- \mathcal{L}(b) = {1 – 2 – 4 – 8 – 9 – 10 – 11 – 12 – 13 – 17 – 18 – 19 – ø},
- \mathcal{L}(c) = {2 – 4 – 5 – 6 – 13 – 14 – 15 – ø},
- \mathcal{L}(P) = {3 – ø},
- \mathcal{L}(S) = {2 – 2 – 10 – 11 – ø},
- \mathcal{L}(W) = {1 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – ø}
- \mathcal{L}(A) = {2 – 1 – ø},
- \mathcal{L}(D) = {1 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – ø},
- \mathcal{L}(T) = {4 – 8 – 9 – ø},
- \mathcal{L}(BT) = {2 – 1 – 2 – 10 – 11 – ø},
- \mathcal{L}(MR) = {5 – 5 – 14 – ø},
- \mathcal{L}(DR) = {6 – 1 – 3 – 5 – 8 – 12 – 14 – ø},
- \mathcal{L}(DC) = {8 – 7 – 8 – ø},
- \mathcal{L}(PR) = {1 – 16 – ø}.
Jak widać listy łańcuchowe w przypadku tego systemu zostały zdefiniowane jako adres bazowy + przesunięcie względem adresu bazowego. Kolejną cechą jest terminowanie takiej listy znakiem ø (null) informującym, że nie występuje już kolejny obiekt posiadający ten deskryptor w opisie.
W takim systemie niezbędna jest tabela zakotwień, gdzie umieścimy adresy bazowe dla wszystkich występujących w systemie deskryptorów i wygląda ona następująco:
| Deskryptor d_i | Adres bazowy | Długość łańcucha |
|---|---|---|
| M | 1 | 11 |
| K | 2 | 9 |
| a | 4 | 1 |
| b | 1 | 12 |
| c | 2 | 7 |
| P | 3 | 1 |
| S | 2 | 4 |
| W | 1 | 15 |
| A | 2 | 2 |
| D | 1 | 15 |
| T | 4 | 3 |
| BT | 2 | 5 |
| MR | 5 | 3 |
| DR | 6 | 7 |
| DC | 8 | 3 |
| PR | 1 | 2 |
Przeanalizujmy procedurę znalezienia odpowiedzi na zadane do systemu pytania.
Przykład 1
Podaj osoby będące pracownikami dydaktycznymi w wieku pomiędzy 20 a 35 lat.
Takie pytanie można sformalizować w postaci termu:
t_1 = (A4, D) \cdot (A2,b)
W tablicy zakotwień odnajdujemy oba deskryptory i wybieramy krótszą listę do dalszego przetwarzania:
tab(D) = (1, 15) \qquad tab(b) = (1,12) \quad \Rightarrow \quad \mathcal{L}_{min} = \mathcal{L}(b)
Dokonując porównania w celu znalezienia części wspólnej (przecięcia) \mathcal{L}_{min}() z pozostałymi listami łańcuchowymi (tu: \mathcal{L}(D)) określamy zbiór obiektów spełniających ten warunek i będących odpowiedzią na zadanie do systemu pytanie:
\sigma(t_1) = \{ x_1, x_3, x_5, x_9, x_{10}, x_{11}, x_{12}, x_{13}, x_{14}, x_{18}, x_{19}, x_{20} \} \\ \cap \\ \{ x_1, x_5, x_6, x_7, x_8, x_9, x_{10}, x_{11}, x_{14}, x_{15}, x_{16}, x_{17}, x_{18}, x_{19}, x_{20} \} \\ \Downarrow \\ \sigma(t_1) = \{ x_{1}, x_{5}, x_{9}, x_{10}, x_{11}, x_{14}, x_{18}, x_{19}, x_{20} \}
Przykład 2
Podaj osoby zajmujące stanowiska techniczne w wieku pomiędzy 20 a 35 lat lub osoby z wykształceniem średnim nie pracujące w administracji.
t_2 = (A_2, b) \cdot (A_4, T) + (A_3, S) \cdot ( \neg (A_4, A))
W tym przypadku ponownie musimy rozpisać pytanie na pytania składowe z wykorzystaniem dopełnienia przy użytej negacji, a więc:
t_2 = (A_2, b) \cdot (A_4, T) + (A_3, S) \cdot ( (A_4, T) + (A_4, D) )
⇓
t_2 = (A_2, b) \cdot (A_4, T) + (A_3, S) \cdot (A_4, T) + (A_3, S) \cdot (A_4, D)
Zajmując się każdym powstałym t_2^1, t_2^2 i t_2^3termem składowym z osobna, szukamy sumy zbiorów odpowiedzi na takie pytanie, a więc:
\sigma(t_2) = \sigma(t_2^1) \cup \sigma(t_2^2) \cup \sigma(t_2^3)
Dla t^1_2 z tablicy zakotwień odszukujemy odpowiednie deskryptory i uzyskujemy:
tab (b) = (1, 12), \qquad tab (T) = (4, 3) \quad \Rightarrow \quad \mathcal{L}_{min} = \mathcal{L}(T)Z uwagi na bardzo krótką listę dokonujemy przeglądu zupełnego elementów zbioru odszukując te, które są relewantne dla drugiego składnika (deskryptora) termu składowego (A2, b). W rezultacie otrzymujemy:
\mathcal{L}(T) = \{ x_4, x_{12}, x_{13} \} |_{_{(A2,b)}} \quad \Rightarrow \quad \sigma(t^1_2) = \{x_{12}, x_{13}\}.
Analogicznie postępujemy z pozostałymi termami składowymi, każdorazowo dokonując wyboru czy posłużymy się przeglądem zupełnym, czy też dokonamy przecięcia zbiorów w celu określenia ich części wspólnej.
Na koniec odpowiedzią jest suma tak określonych zbiorów.
Zadanie 1
Dla tablicy opisów obiektów 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
Modyfikacje list łańcuchowych
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.
Parametry list łańcuchowych
Struktura bazy danych wśród wszystkich poznanych uprzednio metod jest najbardziej skomplikowana. Wynika to z faktu konieczności pamiętania odnośników, wprowadzenia kartoteki wtórnej i tablicy zakotwień.
Redundancja wprowadzona tą metodą praktycznie nie występuje, jednakże z uwagi na konieczność przechowywania dodatkowych składników zajętość pamięci jest znacząco większa i wynosi:
M = M_x + M_o + M_t
gdzie:
- M_x – zajętość pamięci przez opisy obiektów,
- M_o – zajętość pamięci przez konieczność pamiętania odsyłaczy,
- M_t – zajętość pamięci przez tablicę zakotwień.
Aktualizacja bazy informacyjnej z uwagi na jej skomplikowanie jest kłopotliwa. System oparty na metodzie list łańcuchowych dedykowany jest raczej pracy wsadowej. Zmiana opisu obiektu może wpływać na konieczność ponownej generacji tablicy zakotwień i wymagać reorganizacji bazy danych.
Czas wyszukiwania informacji w tego typu systemie jest bardzo krótki i jest zdecydowaną zaletą tego systemu. W zasadzie czas ten opiera się na sumie czasów generowania łańcuchów dla deskryptorów występujących w pytaniu:
\tau = \underset{i}\sum\tau_{g_i}
W przypadku pytań złożonych dochodzi czas znalezienia części wspólnej wygenerowanych łańcuchów (bądź czas przeglądu zupełnego opisów obiektów względem najkrótszego łańcucha). Porównując czasy wyszukiwania z metodą list inwersyjnych można zauważyć przewagę na korzyść metody list łańcuchowych z powodu faktu, iż korzystamy tutaj z najkrótszej listy dla przeszukania, a metoda list inwersyjnych nie uwzględnia długości list.