Spis treści:

Kategoria:SQL Server


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ń:

CREATE TABLE Rights
(
  Flag int NOT NULL,
  Name nvarchar(10) NOT NULL,
  CONSTRAINT PK_Rights_Flag
  PRIMARY KEY (Flag)
)

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:

ALTER TABLE Rights
ADD CONSTRAINT CHK_Rights_Flags
CHECK (LOG(Flag)/LOG(2)=ROUND(LOG(Flag)/LOG(2),0))

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ść:

loga(x) = logb(x)/logb(a)

Mamy zatem:

log2(x) = ln(x)/ln(2)

Przyjrzyjmy się jeszcze następującemu zapytaniu:

SELECT N, LOG(N)/LOG(2) 'LOG(N)'
FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10)) T(N)

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

NLOG(N)
10
21
31,58496250072116
42
52,32192809488736
62,58496250072116
72,8073549220576
83
93,16992500144231
103,32192809488736

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ć:

SELECT N, LOG(N)/LOG(2) 'LOG(N)'ROUND(LOG(N)/LOG(2),0) 'ROUND(LOG(N))'
FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10)) T(N)

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))):

NLOG(N)ROUND(LOG(N))
100
211
31,584962500721162
422
52,321928094887362
62,584962500721163
72,80735492205763
833
93,169925001442313
103,321928094887363

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:

CREATE TABLE BitValues
(
  Name nvarchar(10) NOT NULL,
  Rights int NOT NULL,
  CONSTRAINT PK_BitValues_Name
  PRIMARY KEY (Name)
)

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:

INSERT INTO Rights
VALUES (1, N'Odczyt'),
(2, N'Zapis'),
(4, N'Zmiany'),
(8, N'Usuwanie')

--Taka operacja nie powiedzie się
--Sprzeczne z więzem integralności CHK_Rights_Flags
--INSERT INTO Rights VALUES (9, N'Spanie')
FlagName
1Odczyt
2Zapis
4Zmiany
8Usuwanie

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

INSERT INTO BitValues
VALUES (N'Paweł', 15),
(N'Robert', 1),
(N'Grzegorz',7),
(N'Tomasz',35)
NameRights
Grzegorz7
Paweł15
Robert1
Tomasz35

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ść:

SELECT B.Name, R.Name [Right] FROM BitValues B
JOIN Rights R ON B.Rights & R.Flag = R.Flag
ORDER BY B.Name
NameRight
GrzegorzOdczyt
GrzegorzZapis
GrzegorzZmiany
PawełOdczyt
PawełZapis
PawełZmiany
PawełUsuwanie
RobertOdczyt
TomaszOdczyt
TomaszZapis

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

SELECT B.Name, dbo.GROUP_CONCAT(R.Name, ', ') [Right]
FROM BitValues B
JOIN Rights R ON B.Rights & R.Flag = R.Flag
GROUP BY B.Name
ORDER BY B.Name
NameRight
GrzegorzOdczyt, Zapis, Zmiany
PawełOdczyt, Zapis, Zmiany, Usuwanie
RobertOdczyt
TomaszOdczyt, Zapis

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:

SELECT V.Name, Q.Flags & V.Rights Violations
FROM (SELECT ~SUM(R.Flag) Flags FROM Rights R) Q
CROSS JOIN BitValues V

--Lub podobnie

SELECT V.Name, Q.Flags & V.Rights Violations
FROM BitValues V
CROSS APPLY (SELECT ~SUM(R.Flag) Flags FROM Rights R) Q
NameViolations
Grzegorz0
Paweł0
Robert0
Tomasz32

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:

CREATE TRIGGER BitValuesFlag
ON BitValues
INSTEAD OF INSERTUPDATE
AS
BEGIN
  IF EXISTS(SELECT *
            FROM inserted V
            CROSS APPLY (SELECT ~SUM(R.Flag) Flags FROM Rights R) Q
       WHERE Q.Flags & V.Rights != 0)
  BEGIN
    --Jeżeli ustawiona jest niezdefiniowana flaga, wycofaj transakcję
    ROLLBACK
RETURN
  END
  
  --Można wstawiać jednocześnie wiele rekordów, należy to uwzględnić!
  --Wyzwalacz wywoływany jest raz dla wszystkich nowych rekordów
  IF (EXISTS(SELECTFROM deleted)) -- UPDATE = INSERT + DELETE
    UPDATESET B.Rights=I.Rights
    FROM BitValues B
    JOIN inserted I ON B.Name=I.Name;
  ELSE
    INSERT INTO BitValues(Name, Rights)
    SELECT Name, Rights FROM inserted
END

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

Kategoria:SQL Server

, 2013-12-20

Brak komentarzy - bądź pierwszy

Dodaj komentarz
Wyślij
Ostatnie komentarze
Dzieki za te informacje. były kluczowe
Dobrze wyjaśnione, dzięki !
a z innej strony - co gdybym ciąg znaków chciał mieć rozbity nie na wiersze a na kolumny? Czyli ciąg ABCD: 1. kolumna: A, 2. kolumna: B, 3. kolumna: C, 4 kolumna: D?
Ciekawy artykuł.
Czy można za pomocą EF wysłać swoje zapytanie?
Czy lepiej do tego użyć ADO.net i DataTable?