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

19

Wydaje się znane, że aby znaleźć odpowiedź na zapytanie w relacyjnej bazie danych , potrzebny jest czas i nie można pozbyć się wykładnika.D | D | | Q | | Q |Qre|re||Q||Q|

Ponieważ może być bardzo duży, zastanawiamy się, dlaczego bazy danych w ogóle działają w praktyce.re

Czy to tylko kwestia zwykłych zapytań, które wcale nie są duże w rzeczywistych aplikacjach? (Interesujące jest zatem, aby wiedzieć, jaki jest zwykle rozmiar zapytań stawianych systemom relacyjnych baz danych i jaki jest „maksymalny” rozmiar zapytań, na które w praktyce system DB może efektywnie odpowiedzieć ).

Uwagi na temat wykładnikanie można usunąć|Q|

Aby pokazać, że wykładniknie można go usunąć, można użyć zapytania z pytaniem, czy na wykresie podanym przez bazę danych istnieje klika o rozmiarze . Sprawdzenie, czy na wykresie jest klika, stanowi problem NP-zupełny. Co więcej, nie jest możliwy do ustalenia parametr stały, z parametrem . Szczegóły można znaleźć np. W Libkin, L .: Elementy teorii modeli skończonych. Springer (2004) lub Papadimitriou, CH, Yannakakis, M .: O złożoności zapytań do bazy danych. J. Comput. Syst. Sci. 58 (3), 407–427 (1999)n n n|Q|nnn


cc.complexity-theory time-complexity descriptive-complexity db.databases imz - Ivan Zakharyaschev
źródło
7
Zwykłe zapytania (podobne SELECT * FROM users WHERE username="abc" AND passwrod="xyz") to proste wyszukiwania, których uruchomienie wymaga O (| D |). Jeśli istnieje indeks odpowiednich pól bazy danych, zajmie O (log | D |). Nie interesuję się bazami danych, ale nie sądzę, aby bardziej skomplikowane zapytania wymagałyby wykładniczego czasu.
MS Dousti
7
O(|re|2))O(|re|k+1)
7
W najgorszym przypadku złożoność czasowa jest wykładnicza w długości zapytania . Nie przeczy to temu, że niektóre długie zapytania są szybkie. Specjaliści od baz danych wiedzą, które zapytania działają szybko w typowych silnikach baz danych, i tak nie polegają na najgorszym przypadku związanym z długością zapytania.
Tsuyoshi Ito
2
@Kaveh: „Książka opisująca złożoność Immermana miała małą dyskusję w ostatnim rozdziale”: Bardzo dobra sugestia. Nitpicking: Jest to omówione w przedostatnim rozdziale. @imz: Papier Expressive Power of SQL może również okazać się przydatny.
MS Dousti
5
@imz: „Czy ten wykres ma n-klik” nie jest tak częstym pytaniem w praktyce. Większość zapytań jest bardziej podobna do sugerowanych przez @Sadeq i ma silnie drzewiastą strukturę. Ponadto w przypadku naprawdę dużych baz danych nawet całkowicie liniowe zapytanie jest zbyt drogie i trzeba pracować ze szkicem bazy danych.
András Salamon

Odpowiedzi:

16

Istnieją duże klasy zapytań, które są „łatwe”, nawet w najgorszym przypadku. W szczególności, jeśli klasa zapytań zawiera tylko zapytania łączone, a każde zapytanie ma ograniczoną szerokość (na przykład szerokość, szerokość wykresu padania, ułamkowa szerokość hipertree lub szerokość podmodularna), wówczas na pytanie można odpowiedzieć, używając czegoś w rodzaju drzewa łączenia , wraz z wyliczaniem brutalnej siły dla lokalnych części zapytania, które odbiegają od drzewa. Wymaga to czasu wielomianu, którego stopień wielomianu jest określony przez parametr width.

Wygląda na to, że wiele zapytań napotkanych w praktyce ma charakter łączny i ma małą szerokość. Tak więc wielomianowe środowisko wykonawcze ma w tym przypadku niski stopień.

Dániel Marx przedstawił niedawno na STOC 2010 artykuł na temat szerokości podmodularnej, którego pełna wersja zawiera ładne podsumowanie różnych pojęć szerokości i tego, jak sformułowanie CSP odnosi się do formalizmu bazy danych (brakuje wersji konferencyjnej).

  • Dániel Marx, Tractable hypergraph właściwości dla ograniczenia satysfakcji i zapytań łącznych, 2010. arxiv: 0911.0801

To nie jest pełna odpowiedź, ponieważ nie zajmuje się „typową” złożonością zapytań do bazy danych, ale nawet przy najgorszym przypadku analizy są łatwe.

András Salamon
źródło
6

Można użyć zapytań Q_n, aby sprawdzić, czy wykres reprezentowany jako baza danych zawiera klikę zawierającą n elementów. Sprawdzenie, czy wykres ma klikę, stanowi problem NP-zupełny. Co więcej, nie jest możliwy do ustalenia parametr stały, z parametrem n (co oznacza D ^ n).

Mishaz
źródło
Zamieść dodatkowe wyjaśnienia dotyczące tła pytania albo jako „komentarz” (a nie „odpowiedź”) - za pomocą przycisku „Dodaj komentarz” pod pytaniem lub jako sugestię edycji - za pomocą linku „edytuj” poniżej pytanie. „Odpowiedzi” nie dotyczą dyskusji ani dodatków do pytania. (Udział tutaj powinien być wygodniejszy, jeśli zarejestrujesz się jako użytkownik
nieanonimowy
@imz: Postawił to jako odpowiedź, ponieważ nie ma przywileju komentowania. Trzeba mieć co najmniej 50 powtórzeń. aby móc komentować wszędzie.
Tomek Tarczyński
@Tomek, @imz, cóż, w tej chwili dyskutuje się na meta, czy powinniśmy pozwolić na komentowanie za pomocą odpowiedzi, czy nie.
Kaveh
5

Innym sposobem odpowiedzi na to pytanie jest „nie!”.

Jeśli podasz typowej implementacji DBMS zapytanie zawierające bardzo dużą liczbę złączeń, nie przejdzie ono nawet przez fazę planowania / optymalizacji (nie mówiąc już o ocenie), nawet jeśli zapytanie jest acykliczne lub w inny sposób ma bardzo prostą strukturę, taką jak András nawiązuje do powyższego.

Ale w przypadku „typowych” obciążeń DBMS takie zapytania wydają się nie pojawiać.

tjgreen
źródło
1
W przypadku złożonych zapytań wynikiem fazy optymalizacji jest losowo wybrany plan. Nie jest to wcale takie złe, jak się wydaje, ponieważ ścieżka wykonania może być nadal „wystarczająco dobra”, i istnieje wiele innych powodów, dla których optymalizacja jest trudniejsza niż kombinatoryka liczby złączeń.
Tegiri Nenashi,
4

Oto bardziej realistyczna wersja odpowiedzi tigreen z punktu widzenia osoby, która faktycznie intensywnie korzysta z (relacyjnych) baz danych: Cały sens i złożoność ich zastosowania polega na ich ustrukturyzowaniu w sposób, którego wymagałyby tak mało dołącza się do każdego zapytania, które jest zawsze potrzebne, dlatego właśnie wykonują pracę . Innymi słowy, nie oczekuj, że bazy danych same rozwiążą dla ciebie złożone problemy - nie zrobiłyby tego, ale jeśli są mądrze używane, są naprawdę przydatnym i przydatnym narzędziem.

ktokolwiek
źródło
0

Połączenia są kwadratowe tylko w relacjach wiele do wielu. Są to stosunkowo rzadkie: w praktyce większość relacji i złączeń ma wartość 1 do wielu, więc jeśli zostaną zdefiniowane indeksy / klucze, zajmie to czas liniowy. Zapytania z kilkoma połączeniami „wiele do wielu” stanowią poważny problem.

reinierpost
źródło