RDF w RDBMSs [wertykalne partycjonowanie]

- autor: tsissput

Składnica danych powinna charakteryzować się niskim czasem dostępu do informacji i łatwością w zarządzaniu nią. Wraz z zapotrzebowaniem na struktury semantyczne i ich specyficzny format danych, konieczne było przedsięwzięcie kroków podnoszących ogólnie rozumianą sprawność bazy danych. Korzystanie z danych semantycznych, czyli przede wszystkim formułowanie zapytań bardzo często, wręcz zawsze wykorzystuje mechanizm łączenia tabel. Struktura pojedynczego faktu określa relację między podmiotem a obiektem. Takie trójki mogą być przechowywanie w bazie danych w tabeli o trzech atrybutach po jednym na każdą składową. Aby tak utworzona struktura spełniała wymagania projektowe konieczne jest określenie ogólnego wzorca według, którego rozróżnialne będą fakty. Nie dopuszczalne jest modyfikowanie właściwości (drugiego atrybutu) określonego np. jako „isAuthor” na znaczącą to samo lecz inną z punktu semantyki „authored”. Należy zachować pewną konwencję i się jej trzymać.

Pierwszym sposobem na poprawę wydajności jest podział bazy na fragmenty powiązane z jednym rzeczywistym obiektem. Rozważmy następujące fakty:

< http://helion.pl, autor, Michael McLaughlin >

<http://helion.pl, tytuł, Oracle Database 11g. Programowanie w języku PL/SQL >

< http://helion.pl, ISBN, 978-83-246-1938-2 >

Wszystkie fakty dotyczą książki. Domniemać można, że zapytania do bazy danych operować będą na tej grupie z większą intensywnością niż chociażby na dwóch pierwszych (autor, tytuł) i poniższym:

<http://www.cs.put.poznan.pl, strona, PP>

Dlatego też pewnego typu prognozowanie bądź prościej dopasowanie faktów, które dotyczą jednego rzeczywistego obiektu jest ważnym procesem, który pozwala pogrupować dane w strukturze fizycznej nośnika (np. dysku twardego).

Logiczna implementacja polega na utworzeniu „tabeli właściwości”, która jest tabelą bitową mającą  kolumnę wartości „Subject”, i wiersz „Property”. Oczywiście pojawienie się jedynki informowałoby o istnieniu zależności. Taka struktura przyspieszy działanie bazy, jednak niesie za sobą pewne niedogonienia. Przede wszystkim nie każdy obiekt wykorzystuje całość kolekcji właściwości, zatem tablica ta była by tablicą rzadką. Zmienność danych na poziomie narodowościowym. Mowa o różnych tytułach książek związanych z miejscem jej wydania(wersja angielska, wersja polska). Konieczność kompleksowego przeszukiwania bazy danych w momencie pomyłki, np. literówki jakieś właściwości. Dlaczego całość musiała by być przeczytana? Odpowiedź jest prosta w tym podejściu dane utrzymywane są w jednej globalne tabeli, aż prosi się, żeby je podzielić według jakiegoś kryterium i uzyskać w ten sposób dane bardziej „indywidualne”.

Tablice właściwości.

Poddając analizie tablice a.) oraz stosując pierwsze podejście reorganizacja danych polegać będzie na skupieniu tożsamych co do opisywanego obiektu elementów. I tak otrzymamy nową tablicę, a właściwie to dwie z których jedna zgromadzi obiekty „podobne –[b.)]”, a druga pozostałe elementy nazwijmy je „osobliwe – [c.)]”;0.

ID1 Prawo autorskie 2001
ID1 Tytuł XYZ1
ID1 Autor _a1
ID2 Prawo autorskie 2002
ID2 Tytuł XYZ2
ID2 Autor _a2
ID3 Prawo autorskie 2003
ID3 Tytuł XYZ3
ID3 Autor _a3
ID3 Język PL

a.)    Przykład trójek RDF

Subj. Tytuł Autor Prawa autorskie
ID1 XYZ1 _a1 2001
ID2 XYZ2 _a2 2002
ID3 XYZ3 _a3 2003

b.)    Tabela właściwości

Subject Property Object
ID3 Język PL

c.)    Pozostałe „trójki”

Metodą, która również zwiększa efektywność przetwarzania jest utworzenie „klas”, osobno dla każdego typu obiektu rzeczywistego i podporządkowanie mu dopasowanych na drodze analizy trójek RDF. I tak w naszym przykładzie powstała by jedna klasa „Class: BookType”. Ta dwa podejścia są wspierane przez framework Jena [http://jena.sourceforge.net/ – A Semantic Web Framework for Java].

Wertykalne partycjonowanie – zalety.

Bardziej wydajną strukturą jest wygenerowanie tabeli dla każdej właściwości. Taka tabela ma tylko dwie kolumny pierwsza odwzorowuje podmiot a druga obiekt, dodatkowo sortuje się ją po pierwszym atrybucie. W końcu łączenie tabel wymagało by załadowania mniejszej ilości danych (selekcja związana z wyszukiwaną właściwością i przekopiowaniem do pamięci operacyjnej określonych rekordów, a nie całości) co w konsekwencji zaoszczędzałoby czas związany z czytanie danych, bądź ogólniej wykonywaniem zapytania. Co ciekawe taka struktura nie wymaga jakiś specjalnych zabiegów dopasowujących  bazę danych do stawianych wymagań, a zatem jest to jak najbardziej możliwe do wykonania na podstawowej instancji środowiska.

Takie podejście umożliwia poprawne z punktu semantyki utrzymywanie  atrybutów wielowartościowych. Ogranicza się to tylko do dodatkowego wpisu w tablicy.

ID1 _nazwa1_PL
ID1 _nazwa2_EN

a.)    Wielowartościowość atrybutów

Oczywiście wertykalne partycjonowanie pozwala uniknąć tabel rzadkich ze względu na charakter składowania danych. Nie musimy używać żadnych algorytmów grupowania, ponieważ ta kwestia jest gwarantowana przez strukturę tabel bądź ogólnie organizację informacji, z góry zapewnioną przez projektanta, twórcę systemu. Należy również nadmienić, że w konsekwencji bliskość poszczególnych obiektów implikuje szybsze wyszukiwanie , a zatem modyfikacje w składowaniu przynoszą oczekiwany rezultat, czyli zwiększenie wydajności bazy danych i tylko nietypowe z punktu widzenia semantyki (niewłaściwe) zapytania mogą pogorszyć znacząco jakość rozumianą jako czas odpowiedzi systemu.

Niestety mimo podjętych kroków nie bez znaczenia są koszty wykonywania zapytań. Z pomocą przychodzi nam systemowe udogodnienie, a mianowicie „widoki zmaterializowane”.

Rozważmy problem wydobywania informacji z  trójki RDF. Okazuje się, że podczas korzystania z tablic właściwości zorientowanych np. obiektowo koszt dostępu wymaga n-1 połączeń tabel, gdzie n oznacza długość ścieżki, natomiast przy wertykalnym partycjonowaniu dochodzi parametr uporządkowania danych co ciekawe samo połączenie odbywa się na atrybucie drugi, nieposortowanym. Wspierana wielowartościowość atrybutów nie komplikuje tworzenia widoków zmaterializowanych, co zupełnie inaczej wygląda w przypadku tabeli właściwości, gdzie jest to utrudnione. Należy również zaimplementować adekwatną do potrzeb ilość widoków, aby odciążyć system przy wykonywaniu częstych co do występowania w czasie zapytań, różnych bądź tych samych użytkowników. Trzeba mieć na uwadze zmienność wyników związaną z pojawianiem się nowych danych i tym samym nieaktualność wyników. Zbyt duża bądź całkowita materializacja danych doprowadziłaby nierzadko do kłopotów z stabilnością wręcz dostępnością bazy danych.

Reasumując semantyczne bazy danych potrzebują narzędzi, które przełożą ich zawartość na strukturę wydajną bez utraty informacji w nich zapisanych. Dynamiczny wzrost ilości trójek RDF dodatkowo potęguje tę potrzebę. Główną operacją mającą największy narzut czasowy na wykonanie zapytań jest operacja łączenia. To tutaj właśnie można optymalizować hierarchię danych w najprostszym przypadku je sortując. Początkowo zaproponowana struktura oparta na tabelach właściwości nie znalazła „poparcia” wśród systemów baz danych ze względu na utrudnią implementację atrybutów wielowartościowych. Dowiedziono również, że rzadka co do wypełnienia tabela opóźnia czas wyszukania danych. Tabele zorientowane wertykalnie rozszerzają możliwości składowania informacji, mają akceptowalny czas odpowiedzi na zapytanie SQL i są na pewno łatwiejsze w implementacji. Co do ostatniego faktu można by polemizować bo jedyną trudnością jest przemyślane utworzenie odpowiednich tabel dobrze obrazujących opisywaną rzeczywistość. Czyli dochodzi nam tylko parametr rozgarnięcia osoby tworzącej wspominaną hierarchię. Dzięki próbą poprawy przetwarzania w semantycznych bazach danych  być może w przyszłości złożone zapytania semantyczne generować będą wyniki w czasie krótszym niż dziś i nie będzie to związane tylko z wzrostem mocy obliczeniowej.

 

Tomasz Bzura(103893)

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: