Języki zapytań do baz danych dla wydajnych zapytań

9

Wydaje się, że w popularnych językach zapytań dotyczących relacyjnych baz danych możliwe jest tworzenie zapytań, które będą wymagały dużej ilości zasobów. W praktyce administratorzy baz danych zarządzają tym, ograniczając ilość pamięci na zapytanie i sprawdzając, czy w bazie danych nie ma żadnych długotrwałych zapytań. Wydaje się to raczej ad-hoc, czy istnieje rozwiązanie TCS?

Czy istnieją języki zapytań, które mogą implementować tylko wydajne zapytania?

Jeśli nie ma takich języków, czy istnieje teoretyczny powód?

Niektóre powody, dla których mógłbym oczekiwać, że takie rzeczy istnieją lub przynajmniej mają sens:

  • mamy języki programowania, które zostały zaprojektowane specjalnie w celu implementacji tylko wydajnych obliczeń (zwykle z ograniczoną logiką w ich systemie typów)
  • popularne języki zapytań (takie jak SQL) są już inspirowane logiką, więc użytkownicy bazy danych nie wydają się zbytnio rozważać bardziej restrykcyjnej logiki.
  • niegroźny użytkownik bazy danych już próbuje przygotować zapytania, które są wykonywane szybko, więc powinniśmy oczekiwać, że te bardziej restrykcyjne języki zapytań będą utrudniać tylko szkodliwym użytkownikom.

To pytanie jest inspirowane skrzyżowaniem dwóch poprzednich pytań:

Języki programowania dla wydajnych obliczeń

Dlaczego w ogóle działają relacyjne bazy danych, biorąc pod uwagę teoretyczną wykładniczą złożoność wyszukiwania odpowiedzi (w wielkości zapytania)?

cc.complexity-theory pl.programming-languages db.databases finite-model-theory Artem Kaznatcheev
źródło
1
Czy nie jest to dokładnie temat złożoności opisowej? mają charakterystykę językową zapytań dla różnych klas złożoności.
Kaveh
Złożoność opisowa to zdecydowanie ogromna część i przewodnik po językach programowania do wydajnego obliczania. Ale nie sądzę, że jest to tak proste, jak powiedzenie „złożoność opisowa używa logiki” i „zapytania do baz danych używają logiki”. W szczególności dla DC wydaje się, że rozmiar zapytania jest stały, a „n” pochodzi od rozmiarów struktur skończonych, które te zapytania akceptują. W bazach danych tak naprawdę wielkość zapytania jest zmienna, a baza danych jest również zmienna, a może stały parametr.
Artem Kaznatcheev
3
istnieją również wyniki dla zapytań o zmienne, po prostu nie są tak zdumiewające, jak dopasowanie między sprawdzaniem modelu a znanymi klasami złożoności. Również szersze pole teorii modeli skończonych, którego częścią jest złożoność opisowa, ma wiele wyników wyrażania bezpośrednio związanych z bazami danych. Bazy danych są przecież prawie dokładnie skończonymi strukturami teoretycznymi.
Marc Hamann
1
Nie myślałem o tej korespondencji. Dodałem znacznik skończonej teorii modelu. Jeśli ty lub @Kaveh chcesz rozwinąć swoje komentarze i wiesz, jak przyjąć konkretne wyniki z opisowej złożoności teorii modeli skończonych w ogóle, aby stworzyć takie języki zapytań, to naprawdę chciałbym zobaczyć tę odpowiedź!
Artem Kaznatcheev

Odpowiedzi:

7

Jednym ze sposobów patrzenia na języki zapytań do baz danych jest spojrzenie na dedukcyjne bazy danych , w których zapytania są reprezentowane jako programy logiczne. W tym ustawieniu najbardziej istotną pracą związaną z twoim pytaniem jest McAllester's Analiza złożoności analiz statycznych , która wykazała , że możesz uzasadnić czas wykonania zapytania, uzasadniając liczbę „uruchomień prefiksów” w regułach twojego program. To, co jest „odpalaniem prefiksu”, nie jest strasznie skomplikowane, ale odsyłam cię do tego artykułu.

W świecie programowania funkcjonalnego tego rodzaju zjawisko nazywa się semantyką kosztów : nie oznacza to, że można wdrażać tylko wydajne zapytania (programy), ale oznacza, że ​​można rozsądnie uzasadnić asymptotyczną złożoność programu deklaratywnego. .

Późniejsze prace nad wdrożeniami pomysłów McAllester obejmują Od reguł danych do wydajnych programów z gwarancjami czasu i przestrzeni (Liu i Stoller) oraz Dedalus: Datalog w czasie i przestrzeni (Alvaro, Marczak, Conway, Hellerstein, Maier i Sears). Przyznaję jednak, że nie przeczytałem jeszcze tego drugiego z tych dwóch artykułów.

Rob Simmons
źródło