Zależności funkcyjne - kiedyś mnie tego uczono

Home

Ostatnia przeglądając pytania na stackoverflow.com natknąłem się na takie dotyczące wyznaczania kluczy głównych na podstawie zależności funkcyjnych. Uczono mnie tego na studiach, ale obecnie w praktyce tego nie stosuję i kiedy projektuję bazę danych to nie zaprzątam sobie tym głowy.

Pytanie skłoniło mnie  jednak do odświeżenia sobie wiedzy i sięgnąłem po klasykę w tej dziedzinie czyli "Systemy baz danych" Connollly'ego raz Begg'a. Po kilku minutach lektury okazało się, że w głowie pozostało więcej informacji niż się spodziewałem. Doszedłem jednak do wniosku, że może i zabawa z zależności funkcyjnymi jest dobra dla naszych szarych komórek, ale jednak jest to żmudny proces i fajnie by to zautomatyzować.

Trochę poszperałem w Internecie i znalazłem narzędzie dostępne on-line, które na podstawie zależności funkcyjnych wyznacza klucze kandydujące, weryfikuje w której postaci normalnej jest baza danych itp. Ma ograniczenia, ale zamieszczam link ku pamięci. A to dwa przykłady użycia tego narzędzi do rozwiązania pytań zadanych na stackoverflow.com:

• Pytanie 1 - Przykład 1
• Pytanie 2 - Przykład 2

A tak na marginesie. Czy w swojej praktyce zawodowej stosujecie lub znacie kogoś kto stosuje przy projektowaniu relacyjnych baz danych zależności funkcyjne i na tej podstawie sprawdza czy baza danych jest w odpowiedniej postaci normalnej?

Słów kilka na temat Attach to Process

Home

Post z serii ku pamięci, o poleceniu Debug->Attach to Processz, które umożliwia podczepienie się pod już uruchomiony program i jego debugowanie, a które znane jest chyba wszystkim programistom pracującym z Visual Studio. Rzadziej stosowaną i znaną opcją Attach to Process jest możliwość wybrania rodzaju kodu jaki chcemy debugować (Native, Managed, Script...). Służy do tego okno Select Code Type, które pojawia się po wybraniu przycisku Select. Domyślnie typ kodu określany jest automatycznie i w większości wypadków jest to najlepsza opcja, można to jednak zmienić i wybrać debugowanie kodu na przykład tylko dla platformy .NET w określonej wersji.

Problem z tą opcją jest taki, że jak już się jej użyje to łatwo o tym zapomnieć,a Visual Studio zapamiętuje wybrane ustawienia. Załóżmy, że wybraliśmy debugowanie kodu zarządzanego w wersji 3.5. Wszystko fajnie działa, ale po paru dniach chcemy debugować kod dla platformy 4.0. Podczepiamy się pod wybrany proces, a tu nic się nie dzieje, żaden z naszych breakpoint'ów nie zadział, a Visual Studio nie zgłasza żadnych problemów.

I bądź tu mądry człowieku w takiej sytuacji, albo sobie przypomnimy, że zmieniliśmy tą opcję (o ile wiemy jak dokładnie działa) albo będziemy sobie rwać włosy z głowy.

SizeLimit, PageSize i dokumentacja

Home

W poście wspomniałem o właściwościach DirectorySearcher.SizeLimit oraz DirectorySearcher.PageSize, których poprawne ustawienie zapewnia, że z bazy danych AD można pobrać więcej obiektów niż ustawiony na serwerze limit. Tym razem chciałbym sprecyzować do czego służą obie właściwości bo moim zdaniem dokumentacja nie jest precyzyjna, co potwierdza zresztą spora liczba pytań w Internecie na ten temat.

Otóż SizeLimit określa maksymalną liczbę obiektów jaka może zostać zwrócona w wyniku wyszukiwania (zero oznacza brak limitu) przy czym limit ustawiony na serwerze ma priorytet. PageSize służy natomiast do skonfigurowania stronicowania i wartość różna od zera je włącza. Na przykład wartość 100 oznacza, że obiekty będą zwracane w paczkach po 100, przy czym .NET jest na tyle miły, że samemu obsługuje doczytywanie kolejnych stron.

Teraz spójrzmy na przykład. W bazie danych AD znajdowało się 1580 obiektów spełniających kryteria wyszukiwania, a limit ustawiony na serwerze wynosił 1500. Poniższa tabelka pokazuje ile obiektów zwróci zapytanie w zależności od ustawień.

SizeLimit	PageSize	Liczba obiektów w AD	Liczba zwróconych obiektów	Uwagi
0	0	1580	1500	Brak stronicowania + domyślny limit z serwera
100	0	1580	100	Brak stronicowania + limit określony przez nas
0	100	1580	1580	Stronicowanie włączone
200	100	1580	1580	Stronicowanie włączone + limit określony przez nas
100	200	1580	100	Stronicowanie włączone + limit określony przez nas

Dwa ostatnie scenariusze są trochę zagadkowe. W obu przypadkach obie właściwości są różne od zera, ale liczba zwróconych obiektów jest inna tj. jeśli SizeLimit > PageSize to z AD pobrano wszystkie dostępne obiekty, a w przeciwnym wypadku tyle ile wynosił SizeLimit. Przypuszczam, że DirectorySearcher działa tak, że pobiera dane póki nie zostanie przekroczony limit. W pierwszym przypadku przy pobieraniu kolejnych stron liczba pobieranych obiektów nie przekracza limitu, a więc udało się odczytać wszystko. W drugim wypadku już przy pobraniu pierwszej strony liczba obiektów przekroczyła limit i dalsze pobieranie zostało zakończone. Pewnie można było to zaimplementować inaczej, ale cóż zrobić i po prostu warto o tym wiedzieć.

Jak napisać szybki program pobierający dane z AD

Home

Post ten dotyczy tematu efektywnego pobierania danych z Active Directory. Załóżmy, że chcemy pobrać listę użytkowników przy czym interesują nas tylko niektóre właściwości, które ich opisują. Pokażę trzy niewiele różniące się z pozoru sposoby odczytania potrzebnych nam danych. Pozornie ponieważ te trzy podejścia znacząco różnią się wydajnością. W celu zademonstrowania różnic napisałem prostą klasę ADTester. Zawiera ona tylko jedną metodę Run w parametrach, której określamy tryb działania oraz liczbę obiektów do pobrania. Różnica pomiędzy trybami jest następująca:

• W trybie szybkim (Mode.Fast) dla każdego obiektu z bazy danych Active Directory pobrane zostają tylko wybrane 4 właściwości, a to dzięki zastosowaniu właściwości DirectorySearcher.PropertiesToLoad
• W trybie normalnym (Mode.Normal) dla każdego obiektu z bazy danych Active Directory pobrane zostają wszystkie dostępne dla danego obiektu właściwości.
• W trybie wolnym (Mode.Slow) zamiast użyć danych zawartych w obiektach SearchResult korzystam z metody SearchResult.GetDirectoryEntry.

Poniższa tabela pokazuje czas działania programu w ms w zależności od trybu działania oraz liczby obiektów do pobrania:

maxNumberOfObjects	Mode.Fast	Mode.Normal	Mode.Slow
100	363	463	7507
200	407	661	1600
500	797	2212	39323
1000	1353	3060	75935

W najlepszym przypadku tryb prosty jest 2.7 szybszy niż tryb normalny i prawie 60 razy szybszy niż tryb wolny. Różnica jest wręcz powalająca, a wnioski nasuwają się same.

• Jeśli z góry wiemy jakie właściwości nas interesują to używajmy właściwości DirectorySearcher.PropertiesToLoad.
• Korzystajmy z danych zwróconych przez klasę DirectorySearcher w postaci obiektów SearchResult.
• Tylko jeśli to absolutnie konieczne korzystajmy z metody SearchResult.GetDirectoryEntry. Taka potrzeba zachodzi na przykład wtedy jeśli chcemy zmodyfikować dane w AD.

Na koniec jeszcze jedna uwaga. Wyniki czasu działania programu będą się różnić w zależności od tego gdzie znajduje się serwer Active Directory. W moim przypadku znajdował się on poza krajem. Na koniec zamieszczam kod programu do własnych testów:

public class ADTester
{
    public enum Mode { Fast, Normal, Slow }

    public void Run(Mode mode, int maxNumberOfObjects)
    {
        var ldapPath = "YOUR_LDAP_PATH";

        using (var root = new DirectoryEntry(ldapPath))
        {
            using (var searcher = new DirectorySearcher(root)
                    {
                        Filter = "(&(objectClass=user))", SearchScope = SearchScope.Subtree, SizeLimit = maxNumberOfObjects
                    })
            {
                if (mode == Mode.Fast)
                    searcher.PropertiesToLoad.AddRange(new[]{ "displayName","name", "pwdLastSet","userAccountControl" });

                using (SearchResultCollection searchResult = searcher.FindAll())
                {
                    foreach (SearchResult user in searchResult)
                    {
                        if (mode != Mode.Slow)
                        {
                            var displayName = user.Properties["displayName"];
                            ...
                        }
                        else
                        {
                            var entry = user.GetDirectoryEntry();
                            var displayName = entry.Properties["displayName"];
                            ...
                        }
                    }
                }
            }
        }
    }
}

Czy wyrażenie regularne może zawiesić naszą aplikację?

Home

Rozmawiałem dzisiaj z kumplem z zespołu na temat jednego z zadań i trochę od niechcenie rzuciłem, że można by zastosować tutaj wyrażenie regularne, które dodatkowo byłoby konfigurowalne. Ta z pozoru niewinna uwaga doprowadziła do ciekawej dyskusji. Otóż Tomek stwierdził, że nie jest dobrym pomysłem aby umieszczać wyrażenia regularne w konfiguracji, która może zostać zmieniona przez użytkownika. Dlaczego? W ten sposób umożliwiamy użytkownikowi zawieszenie naszej aplikacji i to nie dlatego, że wyrażenie będzie zawierało błędy składniowe. Aby zrozumieć o co chodzi przyjrzyjmy się takiemu prostemu przykładowi, w którym testuję dwa wyrażenie regularne:

private static void Main(string[] args)
{
   var input1 = "xxxxxxxxxxxxxxxxxxxxxxxxxy";
   var input2 = "xxxxxxxxxxxxxxxxxxxxxxxxx";

   var regex1 = "x+y";
   var regex2 = "(x+)+y";

   TestRegex(regex1, input1);
   TestRegex(regex2, input1);

   TestRegex(regex1, input2);
   TestRegex(regex2, input2);

   Console.WriteLine("Press any key...");
   Console.ReadLine();
}

private static void TestRegex(string r, string input)
{
   var regex = new Regex(r);
   var sw = new Stopwatch();

   sw.Start();

   regex.Match(input);

   sw.Stop();

   Console.WriteLine("{0} ms", sw.ElapsedMilliseconds);
}

Oba użyte wyrażenie są proste. Drugie jest "dziwne" bo po co stosować tutaj konstrukcję grupującą. Oczywiście nie ma to tutaj sensu, ale zrobiłem to aby pokazać ideę problemu. Teraz przejdźmy do setna. Na moim komputerze powyższy program wypisze takie czasy:

30 ticks 0 ms
13 ticks 0 ms
31 ticks 0 ms
21621843 ticks 9246 ms

Różnica jest porażająca. Z pozoru niewinne wyrażenie regularne (x+)+y w przypadku kiedy wejściowy dane do niego nie pasują (w drugim przypadku na końcu ciągu znaków brakuje litery y) jest o duże kilka rzędów wielkości wolniejsze niż wyrażenie x+y Co gorsze im więcej x'ów w danych wejściowych tym te czasy będą gorsze:

Liczba x'ów	Czas (ms)
10	0
14	4
15	9
18	71
20	291
22	1169
24	4685
26	18741
28	74078

Mamy tutaj do czynienia z złożonością wykładniczą! Problem tkwi natomiast w użyciu w drugim wyrażeniu backtracking'u, który powoduje, że silnik wyrażeń regularnych niepotrzebnie wielokrotnie (na)wraca do znalezionych wcześniej dopasowań. Do tego potrzebne są również odpowiednio dobrane dane. Można mówić, że przykład jest tendencyjny (jak to przykład), ale skoro jest to możliwe to kiedyś się zdarzy i dlatego trzeba być świadomym takich rzeczy.

Kilka uwag końcowych:

• Pewnym obejściem problemu jest wyłączenie backtracking'u dla danej grupy w taki sposób: (?>(x+)+)y
• Można również określić maksymalny dopuszczalny czas przetwarzania wyrażenia regularnego np.: new Regex(r, RegexOptions.None, new TimeSpan(0,0,0,1))
• Jeśli to możliwe to zamiast backtracking'u należy stosować tzw. lookahead/lookbehind assertions, które nie nawracają.
• Problem opisałem na przykładzie .NET, ale może od dotyczyć każdego silnika wyrażeń regularnych, który obsługuje backtracking i który domyślnie z niego korzysta.
• Jeśli chcecie pogłębić temat to polecam ten artykuł albo ten.