Planowane badania mają za podstawowy cel stworzenie teoretycznego modelu zdalnego dostępu do baz danych, w tym do wyszukiwarek internetowych (search engines), za pomocą ciągów zapytań. W szczególny sposób uwzględnienione będzie modelowanie kosztu komunikacyjnego tego dostępu.
Zastosowany będzie zmodyfikowany model złożoności komunikacyjnej w sensie Yao. W modyfikacji tej jedynymi dopuszczalnymi komunikatami będą zapytania w języku L oraz wyniki ich ewaluacji w danej bazie danych. W efekcie strona używająca zapytań jest modelowana za pomocą maszyn relacyjnych używających zapytań z danego języka L do bazy danych. Umożliwia to obliczanie zapytań nie dających się wyrazić w języku L, za pomocą ciągów zapytań języka L.
Planuję zbadać dolne ograniczenia na ilość komunikacji w tym modelu obliczeń, traktując jej koszt jako dominujący w całym procesie dostępu do bazy danych.
Badane będą na poziomie modelu matematycznego różne strategie zadawania zapytań (w istocie: protokoły komunikacji z bazą danych), zarówno pomiędzy sobą, jak też z nieprzekraczalnym, teorety\-cznie wyznaczonym minimalnym kosztem tej komunikacji.
Badania będą prowadzone w kontekście różnych języków zapytań --- od prostych modeli automatowych, zbliżonych do przeglądania wyników z wyszukiwarki internetowej, po złożone języki dedukcyjne. }
Użytkownik telefonu komórkowego korzystając z bazy danych (za pomoca protokołu WAP) drogo płaci za każdą minutę pracy, zarówno w pieniądzu, jak i zużyciem baterii swojego aparatu, które rozładowują się podczas trwania połączenia wielokrotnie szybciej. Podobnie oczekiwanie na realizację zapytania w wyszukiwarce jest istotnym czynnikiem spowalniającycm pracę. Użytkownik jest więc żywotnie zainteresowany tym, aby w jak najkrótszym czasie uzyskać interesującą go informację, co w praktyce oznacza transfer jak najmniejszej ilości danych, które będzie musiał przejrzeć ręcznie, a także uniknięcie konieczności ponowienia zapytania z doprecyzowanymi kryteriami wyszukiwania.
Co dziwne, ten tak naturalny i szeroko spotykany model obliczeń przez ciągi zapytań umknął trochę uwadze teorii. Liczba prac, które na ten temat powstały, jest bardzo niewielka. Nie ma prawie żadnych wyników badających moc wyrażania ciągów zapytań, ani też ich złożoność. W dodatku, o ile klasyczne podejście do złożoności obliczeniowej stawia na pierwszym miejscu czas i przestrzeń, o tyle w tym modelu, zwłaszcza w czasach Internetu, na pierwszym planie powinna się znaleźć ilość komunikacji.
Wedle naszej najlepszej wiedzy, problem komunikacyjnego kosztu zdalnego dostępu do baz danych nie był dotychczas badany jako taki w całej swojej ogólności. Znana jest mi tylko jedna praca [B. Xu, O. Wolfson, S. Chamberlain, "Cost based data dissemination in broadcast networks", Proceedings of 8th International Conference on Database Theory(ICDT01), London, UK, 4-6 January, 2001q] analizująca koszt komunikacyjny utrzymania spójności bazy danych w bardzo specyficznym rozproszonym i zdecentralizowanym modelu, spotykanym w zastosowaniach militarnych. Zatem równolegle do opisu narzędzi matematycznych, których planuję użyć, omówię aktualny stan wiedzy o problemie kosztu komunikacyjnego obliczeń w ogóle, a zarazem wskażę, dlaczego żaden z tam rozpatrywanych modeli nie odpowiada w zadowalający sposób zdalnemu dostępowi do baz danych.
Jeśli chodzi o model dostępu zdalnego do bazy danych, to planuję oprzeć go na dwóch, istniejących dotychczas oddzielnie, narzędziach matematycznego opisu obliczeń.
Jest to model nazbyt uproszczony dla naszego celu, gdyż zakłada nieograniczoną moc obliczeniową obu partnerów, jak też ich symetryczną rolę w obliczeniu. W modelowaniu zdalnego dostępu do bazy danych, jeden z partnerów (serwer) ma zwykle nieporównanie większą moc obliczeniową niż drugi (klient), ale jest całowicie pasywny, bo oblicza tylko zapytania otrzymane od klienta. Ponadto oba obliczenia muszą być o złożoności wielomianowej (przy czym złożoność wielomianowa oznacza dla obu partnerów co innego, bo rozmiar ich danych jest inny). Ważnym zagadnieniem, w klasycznym modelu złożoności komunikacyjnej nieobecnym, jest zmienność bazy danych w czasie. Wyglądałoby to tak, jakby dane jednego z partnerów zmieniały się w trakcie obliczenia, a końcowy wynik miał być zgodny z ostatnią wersją danych wejściowych.
Ich rozwinięcie, reflektywne maszyny relacyjne, zdefiniowane przez Abiteboula, Papadimitriou i Vianu [Verso Report #155 Information and Computation, 143(2), pp. 110-136, 1998] , nie są ograniczone do z góry ustalonego, skończonego zestawu zapytań, tylko mogą je aktywnie tworzyć w czasie obliczenia. Trochę w tym przypominają zachowanie człowieka, który przeszukuje Internet, a jego kolejne zapytania są tworzone w oparciu o wyniki poprzednich.
W swoich pracach kierownik projektu rozważał reflektywne maszyny relacyjne jako model zdalnego dostępu do baz danych, jednak z naciskiem na koszt obliczeniowy takiego dostępu, lub na koszt zastąpienia w takim modelu silniejszego języka zapytań innym, słabszym, zaś miarą kosztu był nie wolumen komunikacji, a ilość zapytań. Dodatkowym ograniczeniem było założenie, że klient może używać tylko zapytań booleowskich, czego nie można zakładać w zastosowaniach, które mam na myśli w tym projekcie.
W tej sytuacji, pierwszy partner jest w istocie reflektywną maszyną relacyjną, używającą języka L, a drugie serwerem tej bazy danych.