Rozszerzenie przechwytywania SQL

Według Immermana klasa złożoności powiązana z zapytaniami SQL jest dokładnie klasą bezpiecznych zapytań w (zapytania pierwszego rzędu plus operator zliczania): SQL przechwytuje bezpieczne zapytania. (Innymi słowy, wszystkie zapytania SQL mają złożoność w , a wszystkie problemy w mogą być wyrażone jako zapytanie SQL).Q ( F O ( C O U N T ) ) Q ( F O ( C O U N T ) $\mathsf{Q(FO(COUNT))}$$\mathsf{Q(FO(COUNT))}$$\mathsf{Q(FO(COUNT))}$

Na podstawie tego wyniku, z teoretycznego punktu widzenia, istnieje wiele interesujących problemów, które można skutecznie rozwiązać, ale których nie można wyrazić w języku SQL. Dlatego interesujące wydaje się rozszerzenie SQL, które jest nadal wydajne. Oto moje pytanie:

Czy istnieje rozszerzenie SQL (zaimplementowane i używane w branży ), które przechwytuje$\mathsf{P}$ (tzn. Może wyrażać wszystkie zapytania obliczalne w czasie wielomianowym i żadnych innych)?

Chcę język zapytań do bazy danych, który spełnia wszystkie trzy warunki. Łatwo jest zdefiniować rozszerzenie, które rozszerzyłoby SQL i przechwytuje . Ale moje pytania brzmią, czy taki język ma sens z praktycznego punktu widzenia, więc chcę, aby język był używany w praktyce. Jeśli tak nie jest i nie ma takiego języka, to chciałbym wiedzieć, czy istnieje powód, który sprawia, że ​​taki język jest nieciekawy z praktycznego punktu widzenia? Na przykład, czy zapytania, które pojawiają się w praktyce, są zwykle wystarczająco proste, aby taki język nie był potrzebny?$\mathsf{P}$

Jeśli chodzi o twoje główne pytanie, polecam tę krótką ankietę Martina Grohe.

Czy zapytania, które są potrzebne w praktyce, są zwykle na tyle proste, że nie ma potrzeby używania mocniejszego języka?

Powiedziałbym, że dzieje się tak przez większość czasu, biorąc pod uwagę sporą liczbę rozszerzeń dodanych do popularnych języków zapytań (zamykanie przechodnie, operatory arytmetyczne, liczenie itp.). Wynika to z punktu widzenia kogoś, kto wykonał pracę jako niezależny programista stosunkowo prostych stron internetowych i innych aplikacji, więc nie jestem pewien co do prawdziwego zastosowania SQL w większych branżach / większych bazach danych.

W rzadkich przypadkach może być potrzebny bardziej zaawansowany język. Sądzę, że programiści radzą sobie z nimi, używając języka, w którym piszą aplikację, a nie zapytań (takich jak C ++ lub java).

Po pierwsze, ekspresyjna moc SQL jest mniej wyraźna niż się wydaje. Okazało się, że funkcje agregujące, grupujące i arytmetyczne SQL mają dość subtelne efekty. A priori wydaje się wykonalne, że przez pewne kodowanie operatorów algebraicznych korzystających z tych funkcji można faktycznie wyrazić osiągalność w SQL. Okazuje się, że tak nie jest w przypadku SQL-92 , który jest „lokalny”.

• Leonid Libkin. Ekspresyjna moc SQL , TCS 296 (3), 379–404. doi: 10.1016 / S0304-3975 (02) 00736-3 ( przedruk )

Oznacza to, że do przechwytywania PTIME wymagane jest rozszerzenie SQL-92 oraz takie, które pozwalają, aby język wynikowy był „nielokalny”.

Jednak zezwolenie na uporządkowane struktury i realistycznie ograniczoną arytmetykę, dowodzenie, że SQL-92 nie może wyrazić osiągalności, oznaczałoby, że jednolity a zatem może być dość trudny. (Można argumentować, że zawsze istnieje naturalne uporządkowanie liniowe dla typów danych w SQL-92 i dlatego można założyć, że struktury leżące u podstaw są uporządkowane.)$\text{TC}^0 \subsetneq \text{NLOGSPACE}$

Potem krajobraz zmienił się ponownie, ponieważ SQL: 1999 (SQL3) zawierał rekurencję. Tak więc SQL: 1999 wydaje się być co najmniej tak wyrazisty jak logika stałoprzecinkowa z liczeniem (choć myślę, że szczegóły mogą być znowu dość trudne, w tym kwestia kolejności). Nie wiem, czy nowe konstrukcje uczyniły logikę bardziej wyrazistą, niż jest wymagana do przechwytywania PTIME, i aby to ustalić, potrzebne byłyby jakieś badania. W międzyczasie dokonano dalszych zmian w 2003 , 2006 , 2008 i 2011 r(będąc dokumentami ISO, tylko wersje robocze są swobodnie dostępne). Te zmiany dodały całą masę nowych funkcji, w tym umożliwienie XQuery jako „części” zapytań SQL. Domyślam się, że „SQL” jest teraz bardziej wyrazisty niż jest wymagany do przechwytywania PTIME, ale że wymagane do tego kodowanie może wymagać dużych i raczej nienaturalnych zapytań, które mogą nie być obsługiwane w prawdziwych systemach.

Myślę więc, że istnieją dowody na to, że nie ma przemysłowego rozszerzenia SQL, które precyzyjnie przechwytuje PTIME , odpowiadając na twoje pytanie w niewyraźny sposób. Krótko mówiąc, rozszerzenia przemysłowe są dość potężne i mogą już mieć przekroczony czas PTIME. Jeśli prawdą jest, że SQL: 1999 jest już wystarczająco potężny, aby przechwycić przynajmniej PTIME, to nie jest również jasne, co tak naprawdę oznacza „SQL” w twoim pytaniu, ponieważ należałoby zdefiniować „SQL”, aby oznaczać wersję wcześniejszą niż SQL: 1999.

Wreszcie badanie Grohe dotyczące poszukiwania logiki przechwytującej PTIME (wspomniane również przez Janomę) wskazuje nie tylko, że przechwytywanie PTIME jest trudne, chyba że mamy liniowy porządek jako część języka, ale że dowód, że taka logika nie istniałaby, również implikuje .$\text{P} \ne \text{NP}$

• Martin Grohe, Poszukiwanie logiki przechwytującej PTIME , LICS 2008, 267–271. doi: 10.1109 / LICS.2008.11 ( preprint )

Twoje pytanie nie jest wystarczająco jasne, jeśli chcesz rozszerzenie, które przechwytuje i tylko , czy też oddaje i ewentualnie rzeczy poza . Wygląda na to, że interesuje Cię tylko dokładna klasa , ponieważ chcesz bezpiecznych zapytań, a jeśli tak nie jest, wystarczyłoby każde rozszerzenie SQL Turinga.$P$$P$$P$$P$$P$

Nie wiemy, czy . Jeśli , rozszerzenie SQL zdolne do przechwytywania i tylko powinno być w stanie obliczyć, czy formuła boolowska jest zadowalająca w czasie wielomianowym lub rozwiązać inny problem w czasie wielomianowym.$P = NP$$P = NP$$P$$P$$NPC$

Ale jeśli , twój język rozszerzony SQL nie będzie w stanie obliczyć, jeśli dana formuła boolowska jest zadowalająca.$P \ne NP$

Mamy więc pytanie: czy istnieje algorytm (lub zapytanie lub cokolwiek innego) napisany w takim języku, który jest w stanie zdecydować, czy formuła boolowska jest zadowalająca? Nie mogę na to odpowiedzieć (i prawdopodobnie nikt tutaj nie może, ponieważ odpowiedź na to pytanie odpowiada, jeśli ). To pytanie pozwala mi wierzyć, że jest bardzo mało prawdopodobne, aby ten język istniał w prawdziwych celach.$P = NP$

Chociaż prawdopodobnie nie istnieje do prawdziwych celów, z pewnością istnieje i jest konstruowalny i możliwy do wdrożenia. Możesz zdefiniować ten język za pomocą czegoś, co może symulować maszynę Turinga do określonej liczby kroków. IE, zdolny do rozwiązania problemu P-complete . Jeśli jednak skonstruujesz coś takiego, jest on prawie ukończony przez Turinga, z wyjątkiem ograniczenia „dającego nieograniczoną liczbę kroków”, co w języku podobnym do SQL byłoby bardzo dziwnym sposobem ograniczenia go tylko do bezpiecznych zapytań. Możesz to zrobić, jeśli kroki są zapisami tabeli, ale nadal nie wygląda to nic cennego ze względów praktycznych.