Extensão da captura SQL

20

De acordo com Immerman , a classe de complexidade associada às consultas SQL é exatamente a classe de consultas seguras em (consultas de primeira ordem e operador de contagem): o SQL captura consultas seguras. (Em outras palavras, todas as consultas SQL têm uma complexidade em \ mathsf {Q (FO (COUNT))} , e todos os problemas em \ mathsf {Q (FO (COUNT))} podem ser expressos como uma consulta SQL.)Q(FO(COvocêNT))Q(FO(COvocêNT))Q(FO(COvocêNT))

Com base nesse resultado, do ponto de vista teórico, existem muitos problemas interessantes que podem ser resolvidos com eficiência, mas não são expressáveis ​​em SQL. Portanto, uma extensão do SQL ainda eficiente parece interessante. Então aqui está a minha pergunta:

Existe uma extensão do SQL (implementada e usada na indústria ) que captura P (ou seja, pode expressar todas as consultas computáveis ​​em tempo polinomial e nenhuma outra)?

Eu quero uma linguagem de consulta de banco de dados que stisfies todas as três condições. É fácil definir uma extensão que estenda o SQL e capture P . Mas minhas perguntas são: se essa linguagem faz sentido do ponto de vista prático, quero uma linguagem que esteja sendo usada na prática. Se esse não é o caso e não existe essa linguagem, eu gostaria de saber se existe uma razão que torne essa linguagem desinteressante do ponto de vista prático? Por exemplo, as consultas que surgem na prática geralmente são simples o suficiente para que não haja necessidade dessa linguagem?

Kaveh
fonte
1
@JD, desculpe, mas com base no seu comentário, acho que você não entende a pergunta. A questão está bem definida. Capturar uma classe de complexidade por um idioma é uma terminologia padrão. (o que não está bem definido é a minha preferência de que o idioma seja uma linguagem de consulta, mas isso é apenas uma preferência e eu lhe disse que ficaria bem com um que não seja se não houver um com essa preferência.)
Kaveh
1
@ Shog9, eu já respondi a isso. JD não entende a pergunta, ele nem sabia o que significa captura e não sabe que uma linguagem que captura P não pode ser Turing completa por definição. Ele espera que isso seja declarado da maneira que ele gosta, eu o declarei na terminologia usual da complexidade descritiva e na complexidade das linguagens de consulta, e até as expliquei. O que não está claro aqui?
Kaveh
1
@ Shog9, a motivação vem da Complexidade Descritiva . Estou tentando ver se existe uma linguagem que estende o SQL usada na indústria que captura P. A linguagem SQL original é bastante fraca, como mostram os resultados de Immermann, do ponto de vista teórico, muitos cálculos eficientes são impossíveis de declarar nela. Por outro lado, gostaríamos de manter a linguagem eficiente (por exemplo, ). Existe esse idioma? (Eu acho que isso provavelmente é claro para pessoas familiarizadas com a complexidade descritiva). P
Kaveh
4
@ Shog9: Não vejo por que essa pergunta precisava de intervenção do moderador e foi encerrada. Estou confortável o suficiente com a Complexidade Descritiva para dizer que esta é uma pergunta real (embora possivelmente seja mais adequada para o TCS - é uma pergunta um pouco difícil).
Alex-Brink
1
Como notei que outra pergunta também foi fechada (que também teve votos próximos), fiz uma pergunta sobre a meta sobre isso: meta.cs.stackexchange.com/questions/97/…
Alex ten Brink

Respostas:

5

Quanto à sua pergunta principal, recomendo esta breve pesquisa de Martin Grohe.


As consultas necessárias na prática geralmente são simples o suficiente para que não haja necessidade de um idioma mais forte?

Eu diria que isso acontece na maioria das vezes, dada a quantidade razoável de extensões adicionadas às linguagens de consulta comuns (fechamento transitivo, operadores aritméticos, contagem etc.). Isso vem do ponto de vista de alguém que já trabalhou como desenvolvedor freelancer de sites e aplicativos relativamente simples, por isso não tenho certeza dos usos reais do SQL em indústrias maiores / bancos de dados maiores.

Nos raros casos em que uma linguagem mais poderosa pode ser necessária, meu palpite é que os desenvolvedores de software lidam com eles usando o idioma em que escrevem o aplicativo, não as consultas (como C ++ ou java).

Janoma
fonte
3

Primeiro, o poder expressivo do SQL é menos claro do que parece. Os recursos agregados, de agrupamento e aritméticos do SQL têm efeitos bastante sutis. A priori, parece possível que, por alguma codificação de operadores algébricos usando esses recursos, alguém possa realmente expressar a acessibilidade no SQL. Acontece que esse não é realmente o caso do SQL-92 , que é "local".

Isso significa que é necessária uma extensão para o SQL-92 capturar PTIME, e uma extensão que permita que o idioma resultante seja "não local".

TC0 0NLOGSPACE

Então o cenário mudou novamente, pois o SQL: 1999 (SQL3) incluía recursão. Portanto, SQL: 1999 parece ser pelo menos tão expressivo quanto a lógica de ponto fixo com a contagem (embora eu ache que os detalhes possam ser novamente bastante complicados, incluindo a questão da ordem). Se as novas construções tornaram a lógica mais expressiva do que o necessário para capturar o PTIME, eu não sei, e algum estudo seria necessário para estabelecer isso. Enquanto isso, novas revisões foram feitas em 2003 , 2006 , 2008 e 2011(sendo documentos ISO, apenas rascunhos estão disponíveis gratuitamente). Essas revisões adicionaram uma série de novos recursos, incluindo a permissão do XQuery como "parte" das consultas SQL. Meu palpite é que "SQL" agora é mais expressivo do que o necessário para capturar PTIME, mas que a codificação necessária para isso pode exigir consultas grandes e pouco naturais que talvez não sejam suportadas em sistemas reais.

Então, acho que há evidências de que não há extensão industrial do SQL que capture precisamente o PTIME , respondendo à sua pergunta de maneira difusa. Em resumo, as extensões industriais são bastante poderosas e podem já ter superado o PTIME. Se é verdade que o SQL: 1999 já é poderoso o suficiente para capturar pelo menos PTIME, também não está claro o que "SQL" realmente significa na sua pergunta, pois seria necessário definir "SQL" para significar uma versão anterior ao SQL: 1999.

Finalmente, a pesquisa de Grohe sobre a busca de lógicas que capturam PTIME (também mencionada por Janoma) indica não apenas que capturar PTIME é complicado, a menos que tenhamos uma ordem linear como parte da linguagem, mas que uma prova de que não pode haver essa lógica também implica .PNP

András Salamon
fonte
Obrigado András, principalmente por mencionar que o SQL3 suporta "recursão", tenho que verificar e ver o que se sabe sobre isso. :)
Kaveh
ps: Suponho que você incluiu a discussão da relação com a teoria da complexidade e a captura lógica de P para os leitores, no entanto, deixe-me acrescentar como nota lateral e para esclarecimento: Estou usando SQL no sentido em que Immerman a usou no resultado e que O resultado usa uma definição precisa de SQL. Eu sei sobre relações com separações classe de complexidade e a questão de uma lógica captura P, no entanto eu não acho que eles afetam a resposta à minha pergunta,
Kaveh
a resposta para a minha pergunta pode ser positivo (ou negativo) e que seria consistente com todas as respostas possíveis a P versus NP e a existência de uma lógica de fim-invariante para P.
Kaveh
Kaveh, se você define SQL como Immerman, acho que a resposta é "provavelmente não", pois as extensões industriais existentes parecem ser muito fracas ou muito poderosas. Mas (AFAIK) não temos provas rigorosas para isso. Eventualmente, algum subconjunto das extensões precisamente captura ÓPTIMO, mas eu não tenho certeza se eu gostaria de arrasto através das especificações tentando isolá-lo ...
András Salamon
-1

PPPPP

P=NPP=NPPPNPC

PNP

P=NP

Embora provavelmente não exista para propósitos reais, certamente existe e é construtível e implementável. Você pode definir essa linguagem com algo capaz de simular uma máquina de Turing até um número unário de etapas. IE, capaz de resolver um problema de P-completo . No entanto, se você construir uma coisa dessas, ela estará quase completa em Turing, exceto pela restrição "dado um número unário de etapas", que em uma linguagem semelhante ao SQL seria uma maneira muito estranha de limitar a consulta segura. Você pode fazer isso se as etapas forem registros de alguma tabela, mas isso ainda não parece valioso para fins práticos.

Victor Stafusa
fonte
2
FOUMAC0 0
1
NPPPFO(euFP)P