Mapy bitowe - implementacja i integralność w SQL

Zapotrzebowanie na flagi bitowe

Flagi bitowe wykorzystywane są w informatyce od bardzo dawna. Od asemblera, który posiada cały zestaw operacji bitowych, przez języki nieco wyższego poziomu, takie jak C i C++, czy języki platformy .NET, takie jak Visual Basic i C#. Te operacje bitowe nie są tam przypadkowo. Wiele informacji może być przechowywanych w postaci jednego bitu, a dobrą praktyką jest stosowanie najmniejszej możliwej struktury do przechowywania informacji. Procesor nie jest w stanie zaadresować jednego bitu, więc programiści jakoś musieli sobie z tym radzić i nauczyli się pakować zestaw bitów do jednego słowa (słowo w rozumieniu rozmiaru podstawowego rejestru procesora). Nie chodzi tylko o stare komputery i oszczędność pamięci, nie chodzi tylko o szybkość przetwarzania. Chodzi o prostotę systemu i prostotę wykonywania zapytań i obliczeń.

Istnieje szereg praktycznych zastosowań, z których wymienię kilka:

1. Bitowe określenie stylu czcionki. Przypuśćmy, że styl czcionki może być definiowany na dowolnym poziomie i poszczególne bity oznaczają: 0-pogrubiona, 1-pochylona, 2-podkreślona, 3-przekreślona, 4-indeks dolny, 5-indeks górny. Gdy pola zgrupowane są w jednym słowie, wystarczy wykonać sumę bitową wszystkich elementów nadrzędnych włączających poszczególne style. Gdybyśmy mieli 6 oddzielnych pól, należałoby każde z nich sumować oddzielnie. To znacznie więcej pisania!
2. Uprawnienia pochodzące z różnych ról. Zakładamy, że użytkownik ma prawo lub nie ma prawa do czegoś. Jeżeli choć jedna z ról, do której jest przypisany, przydziela mu takie prawo, uznajemy że użytkownik jest upoważniony do pewnej akcji. Te akcje to mogą być, powiedzmy: wstawianie, usuwanie, pobieranie, modyfikacja, zmiana praw, przesyłanie. To właśnie kolejne flagi bitowe. Znów łatwiej to zrobić w grupie.
3. Flagi bitowe sterujące urządzeniami zewnętrznymi. W tym przypadku schodzimy na nieco niższy poziom niż zwykle, ale aplikacje są różne. Każdy bit to nóżka procesora, której sygnał włącza lub wyłącza konkretne urządzenie. Włączone urządzenie może przysyłać wyniki pomiarów, a my chcemy decydować, kiedy takich danych potrzebujemy. Zamiast stosować wiele zmiennych w programie/kolumn w bazie można zastosować mapę bitową. W tym przypadku jest to bardziej naturalne rozwiązanie.

Języki proceduralne i obiektowe pozwalają na symboliczny opis poszczególnych bitów (np. typ enum z atrybutem Flags w C#). W SQL Server jest nieco trudniej. Tam pola bitowe przechowujemy w zmiennej typu całkowitego (tinyint, smallint, int, bigint). Taka kolumna niewiele nam mówi, ale można to zmienić.

Identyfikatory jako flagi bitowe

Flagi bitowe przyjmują najczęściej wartości równe kolejnym potęgom liczby 2. Najmłodszy bit to 2^0, kolejny 2^1, potem 2^2. Dziesiętnie są to wartości 1, 2, 4, 8, 16 i tak dalej. Jak zatem zmusić SQL Server do użycia tylko flagowych identyfikatorów? Popatrzmy na definicję przykładowej tabeli z flagami, tabelę uprawnień:

Tabela zawiera klucz główny oraz opis prawa. Tyle - przykład ma być prosty. Teraz należy wymusić flagowość klucza. Jak to zrobić? Można użyć odpowiedniego wyzwalacza INSTEAD OF, ale można to zrobić przy pomocy prostego wyrażenia CHECK. Popatrzmy na przykładowe rozwiązanie:

Metoda może się wydawać dziwna, dlatego zamierzam ją szerzej opisać.

Sprawdzanie, czy wartości są kolejnymi potęgami 2

Wspomniałem, że flagi bitowe są opisywane przez kolejne potęgi liczby 2 (1, 2, 4, 8, 16...). Mamy do czynienia z funkcją potęgową, więc trzeba ją nieco spłaszczyć. Co się do tego najlepiej nadaje? Co jest funkcją odwrotną? Funkcja logarytmiczna! Funckja potęgowa przepuszczona przez funkcję logarytmiczną (o ile podstawa logarytmu jest taka sama jak podstawa potęgi) staje się funkcją liniową. Problem w tym, że SQL Server 2008 i niższe wersje posiadają tylko logarytm naturalny. Tutaj z pomocą przychodzi matematyka i znana powszechnie zależność:

Mamy zatem:

Przyjrzyjmy się jeszcze następującemu zapytaniu:

A następnie wynikom otrzymanym po wykonaniu powyższej instrukcji:

Logarytm o podstawie 2 z liczby będącej potęgą liczby 2 jest wartościa całkowitą. Wystarczy zatem zaokrąglić wynik i sprawdzić, czy wartość logarytmu i zaokrąglenia logarytmu są sobie równe. Popatrzmy na poniższe zapytanie i wszystko powinno się wyjaśnić:

Rezultat widoczny jest jak na dłoni - tam gdzie wartości są takie same, tam mamy do czynienia z flagą (LOG(N) = ROUND(LOG(N))):

Myślę, że teraz jest już wszystko jasne. Można oczywiście zastosować bardziej mechaniczne sprawdzanie warunku z bezpośrednimi porównaniami (N=1 OR N=2 OR N=4 OR N=8 ...), ale lubię czasem przemycić takie ciekawostki matematyczne. Także, a może przede wszystkim, dla tych, którzy myślą, że matematyka nie jest przydatna.

Tabela z flagami jest wystarczająco dobrze zabezpieczona. Czas na tabelę z wartościami.

Tabela korzystająca z flag

Przypuśćmy, że tabela będzie zawierała listę użytkowników i przypisane do nich prawa w postaci maski bitowej. Tabela znów będzie prosta, żeby nie zaciemniać rzeczy najważniejszych. Przyjrzyjmy się poniższej deklaracji:

Pierwsza kolumna to nazwa użytkownika, druga to prawa. Problem w polega na tym, że do kolumny z prawami możemy wstawić dowolną wartość. Takich nieścisłości chcemy uniknąć. O co dokładnie chodzi? Uzupełnijmy sobie obie tabele konkretnymi wartościami:

Wstawmy sobie i do tej drugiej tabeli jakieś wartości:

Przyjrzyjmy się binarnej postaci poszczególnych wartości. Grzegorz ma wartość 7, co daje binarnie 00000111, czyli włączone bity kolejno od prawej 2^0 (1), 2^1 (2) oraz 2^2 (4). W sumie 7. Paweł ma dodatkowo włączony bit 2^3 (8), czyli w sumie 15. Robert ma ustawiony tylko najmłodszy bit (1). A co z Tomaszem? Jego postać binarna to 00100011. Ma włączony bit 2^5 (32), który nie jest związany z żadną flagą! Tak być nie może! Zaraz do tego wrócimy. Najpierw pokażę, jak można pobrać zestaw praw dla kolejnych użytkowników.

Łączenie tabeli z opisem flag

Mając na myśli złączenia zwykle myślimy o złączeniach równościowych. Rzadko myśli popłyną w stronę złączeń funkcyjnych lub nierównościowych - są to złączenia teta (Θ, teta, theta - grecka litera alfabetu wykorzystywana do oznaczania złączeń nierównościowych). Ja wykorzystam operację bitową AND - jeżeli oba bity są ustawione, zwróć wartość:

Wykorzystanie funkcji agregującej wykonującej złączenie tekstów pozwala na jeszcze przyjemniejszy rezultat (zob. wpis GROUP_CONCAT w SQL Server):

Takie rozwiązanie jest przydatne dla kogoś, kto chce obejrzeć wartości przy pomocy języka SQL. Aplikacja najczęściej będzie posiadała inne mechanizmy do oglądania wartości (np. enum z atrybutem Flags w .NET).

Kontrola wartości pól przechowujących flagi

Mogliśmy się już przekonać, że tabela wartości nie zabezpiecza nas przed wstawieniem niepoprawnych wyników. Tomasz ma ustawioną flagę, która nic nie oznacza. Takie wartości to potencjalne źródło problemów. Nie chodzi tylko o SQL. Takie wartości najczęściej są gdzieś przesyłane, aplikacje rzutują te wartości na typy wyliczeniowe. Jeden błąd - szereg problemów. Czy można się przed tym zabezpieczyć? Zwykle w takich przypadkach zakłada się klucze obce, ale SQL Server nam na to nie pozwoli. O ile nierównościowe złączenia mogą być stosowane, o tyle nierównościowych kluczy obcych zrobić nie możemy. Da się założyć klucz obcy na kolumnie wyliczanej, ale są inne problemy:

• Kolumna wyliczana musi mieć atrybut PERSISTED - znaczy to, że dane przechowywane są razem z tabelą.
• Dla każdego używanego bitu trzeba zdefiniować oddzielną kolumna i oddzielny klucz. Nie po to grupujemy bity, żeby je teraz rozdzielać.

Tam gdzie klucze obce i więzy typu CHECK nie wystarczają, tam są jeszcze wyzwalacze. Jak znaleźć rekordy, które korzystają z niezdefiniowanych bitów? Popatrzmy na poniższy listing:

Na czym polega sztuczka? Najpierw sumujemy wszystkie bity z tabeli Rights (są unikalne, bity nie pokrywają się - wystarczy standardowa agregacja SUM). Wartość negujemy, otrzymując maskę bitową z ustawionymi wartościami tam, gdzie nie ma flag. Tak uzyskany rezultat łączymy bitowym operatorem AND (&) z prawami z tabeli BitValues. Jeżeli któryś z bitów spoza zakresu jest ustawiony, wynik będzie inny niż 0.

Wyposażeni w taką wiedzę możemy spokojnie napisać odpowiedni wyzwalacz INSTEAD OF. Przykładowe rozwiązanie pokazałem na poniższym listingu:

Teraz próba wstawienia nowego rekordu z nieprawidłową maską bitową nie powiedzie się - zablokuje nas wyzwalacz.

Kategoria:SQL Server