ZSBD-2st-1.2-w6.tresc-1.1-Slajd19

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Sygnatury zbiorów

Sygnatury zbiorów


Metoda, która pozwala na wydajną realizację operacji porównania zbiorów zastępuje zbiory wartości lub zawiązków specjalnymi wartościami numerycznymi nazywanymi sygnaturami.

Dla każdego elementu zbiorów składowanych w obiektach, czyli pojedynczej wartości atrybutu wielowartościowego lub pojedynczej referencji związku wielokrotnego, jest wyznaczana unikalna sygnatura. Równość elementów oznacza równość ich sygnatur.

Następnie za pomocą logicznego sumowania sygnatur wszystkich elementów zbiorów są tworzone zbiorcze sygnatury dla całych zbiorów. Sumaryczne sygnatury są prostymi wartościami liczbowymi, dzięki czemu można je łatwo porównywać i porządkować, co pozwala na zastosowanie wydajnych metod łączenia, takich jak wspomniane metody sort-merge lub hash-join.

Specyficzne zależności zachodzące między wartościami sygnatur zbiorów oznaczają określone zależności zachodzące między samymi zbiorami. Na slajdzie pokazano zależność, która musi zachodzić między sygnaturami zbiorów, by między tymi zbiorami zachodziła relacja podzbioru. W tym konkretnym wypadku zależność, w której iloczyn logiczny sygnatury zbioru „s ”, z negacją sygnatury zbioru „t jest równa zero, oznacza, że zbiór „t jest podzbiorem zbioru „s ”.

Na dole slajdu pokazano przykład utworzenia sygnatury dla zbioru punktów A i B, którym przypisano dwie dowolnie ustalone sygnatury. Dla uzyskanej sygnatury zbioru punktów A i B można zweryfikować na podstawie zdefiniowanej wyżej zależności, zastosowanej dla sygnatury zbioru punktów A i B oraz sygnatury punktu A, że zbiór punktów A i B zawiera w sobie punkt A.


<< Poprzedni slajd | Spis treści | Następny slajd >>