Extensión de SQL capturando

20

Según Immerman , la clase de complejidad asociada con las consultas SQL es exactamente la clase de consultas seguras en Q(FO(COUNT)) (consultas de primer orden más operador de conteo): SQL captura consultas seguras. (En otras palabras, todas las consultas SQL tienen una complejidad en Q(FO(COUNT)) , y todos los problemas en Q(FO(COUNT)) se puede expresar como una consulta SQL.)

En base a este resultado, desde el punto de vista teórico, existen muchos problemas interesantes que pueden resolverse eficientemente pero que no se pueden expresar en SQL. Por lo tanto, una extensión de SQL que sigue siendo eficiente parece interesante. Ésta es mi pregunta:

¿Existe una extensión de SQL (implementado y utilizado en la industria ) que captura P (es decir, puede expresar todas las consultas computables en tiempo polinómico y ninguna otra)?

Quiero un lenguaje de consulta de base de datos que cumpla con las tres condiciones. Es fácil definir una extensión que se extendería SQL y capturará P . Pero mi pregunta es si ese lenguaje tiene sentido desde la perspectiva práctica, por lo que quiero un lenguaje que se utilice en la práctica. Si este no es el caso y no existe dicho lenguaje, entonces me gustaría saber si hay una razón que hace que dicho lenguaje no sea interesante desde el punto de vista práctico. Por ejemplo, ¿las consultas que surgen en la práctica suelen ser lo suficientemente simples como para que no haya necesidad de tal lenguaje?

Kaveh
fuente
1
@JD, lo siento, pero según tu comentario, creo que no entiendes la pregunta. La pregunta está bien definida. Capturar una clase de complejidad por un idioma es una terminología estándar. (lo que no está bien definido es mi preferencia de que el idioma sea un idioma de consulta, pero eso es solo una preferencia y le he dicho que estaría bien con uno que no lo es si no hay uno con esa preferencia).
Kaveh
1
@ Shog9, ya he respondido a eso. JD no entiende la pregunta, ni siquiera sabía qué significa capturar y no es consciente de que un lenguaje que captura P no puede ser Turing completo por definición. Espera que se exprese de la forma en que le gusta, lo he dicho en la terminología de complejidad descriptiva habitual y la complejidad de los lenguajes de consulta, e incluso se lo he explicado. ¿Qué no está claro aquí?
Kaveh
1
@ Shog9, la motivación proviene de la complejidad descriptiva . Estoy tratando de ver si hay un lenguaje que extienda el SQL utilizado en la industria que capture P. El lenguaje SQL original es bastante débil, como lo muestra el resultado de Immermann, desde el punto de vista teórico es imposible establecer muchos cálculos eficientes. Por otro lado, nos gustaría mantener el lenguaje eficiente (es decir, ). ¿Existe tal lenguaje? (Creo que estos son probablemente claros para las personas familiarizadas con la complejidad descriptiva). P
Kaveh
44
@ Shog9: No veo por qué esta pregunta necesitaba la intervención del moderador y se cerró. Me siento lo suficientemente cómodo con la complejidad descriptiva como para decir que esta es una pregunta real (aunque posiblemente sea más adecuada para TCS, es una pregunta un poco difícil).
Alex ten Brink
1
Cuando noté que también se cerró otra pregunta (que también tenía votos cerrados), hice una pregunta sobre meta al respecto: meta.cs.stackexchange.com/questions/97/…
Alex ten Brink

Respuestas:

5

En cuanto a su pregunta principal, recomiendo esto breve encuesta de Martin Grohe.


¿Las consultas que se necesitan en la práctica suelen ser lo suficientemente simples como para que no sea necesario un lenguaje más fuerte?

Diría que esto es válido la mayor parte del tiempo, dada la cantidad justa de extensiones agregadas a los lenguajes de consulta comunes (cierre transitivo, operadores aritméticos, conteo, etc.). Esto proviene del punto de vista de alguien que ha trabajado un poco como desarrollador independiente de sitios web relativamente simples y otras aplicaciones, por lo que no estoy seguro acerca de los usos reales de SQL en industrias más grandes / bases de datos más grandes.

En los raros casos, podría necesitarse un lenguaje más poderoso, supongo que los desarrolladores de software los tratan utilizando el lenguaje en el que escriben la aplicación, no las consultas (como C ++ o Java).

Janoma
fuente
3

Primero, el poder expresivo de SQL es menos claro de lo que parece. Las características agregadas, de agrupación y aritméticas de SQL resultan tener efectos bastante sutiles. A priori, parece factible que mediante alguna codificación de operadores algebraicos que usen estas características, uno realmente pueda expresar accesibilidad en SQL. Resulta que este no es realmente el caso para SQL-92 , que es "local".

Esto significa que se requiere una extensión para que SQL-92 capture PTIME, y una que permita que el lenguaje resultante sea "no local".

Sin embargo, permitir estructuras ordenadas y con una aritmética limitada de manera realista, demostrar que SQL-92 no puede expresar accesibilidad implicaría que y, por lo tanto, es probable que sea bastante difícil. (Se podría argumentar que siempre existe un orden lineal natural en los tipos de datos en SQL-92, y que, por lo tanto, se podría suponer que las estructuras subyacentes están ordenadas).TC0NLOGSPACE

Luego, el panorama cambió nuevamente, ya que SQL: 1999 (SQL3) incluía recursividad. Entonces, SQL: 1999 parece ser al menos tan expresivo como la lógica de punto fijo con el conteo (aunque creo que los detalles podrían volver a ser bastante complicados, incluida la cuestión del orden). No sé si las nuevas construcciones hicieron que la lógica sea más expresiva de lo que se requiere para capturar PTIME, y sería necesario algún estudio para establecer esto. Mientras tanto, se realizaron nuevas revisiones en 2003 , 2006 , 2008 y 2011(al ser documentos ISO, solo los borradores están disponibles gratuitamente). Estas revisiones agregaron una gran cantidad de nuevas características, incluyendo permitir XQuery como "parte" de las consultas SQL. Supongo que "SQL" ahora es más expresivo de lo que se requiere para capturar PTIME, pero que la codificación requerida para hacerlo podría requerir consultas grandes y poco naturales que podrían no ser compatibles con sistemas reales.

Entonces, creo que hay evidencia de que no hay una extensión industrial de SQL que capture con precisión PTIME , respondiendo a su pregunta de manera difusa. En resumen, las extensiones industriales son bastante potentes y ya pueden haber superado PTIME. Si es cierto que SQL: 1999 ya es lo suficientemente potente como para capturar al menos PTIME, entonces tampoco está claro qué significa realmente "SQL" en su pregunta, ya que uno tendría que definir "SQL" para significar una versión anterior a SQL: 1999

Finalmente, la encuesta de Grohe sobre la búsqueda de lógicas que capturan PTIME (también mencionada por Janoma) indica que no solo capturar PTIME es complicado a menos que tengamos un orden lineal como parte del lenguaje, sino que también sería una prueba de que no podría haber tal lógica. implica .PNP

András Salamon
fuente
Gracias András, especialmente por mencionar que SQL3 admite "recursividad", tengo que verificar y ver qué se sabe al respecto. :)
Kaveh
PD: Supongo que incluyó la discusión de la relación con la teoría de la complejidad y la lógica que captura P para los lectores, sin embargo, permítanme agregar como nota al margen y para aclarar: estoy usando SQL en el sentido de que Immerman lo ha usado en el resultado y que El resultado utiliza una definición precisa de SQL. Yo sé de relaciones con separaciones de clase de la complejidad y la cuestión de la captura de una lógica P, sin embargo no creo que afectan la respuesta a mi pregunta,
Kaveh
la respuesta a mi pregunta puede ser positiva (o negativa) y serían consistentes con todas las respuestas posibles a P vs. NP y la existencia de una lógica invariante de orden para P.
Kaveh
Kaveh, si define SQL como lo hizo Immerman, entonces creo que la respuesta es "probablemente no", ya que las extensiones industriales existentes parecen ser demasiado débiles o demasiado potentes. Pero (AFAIK) no tenemos pruebas rigurosas de esto. Posiblemente, un subconjunto de las extensiones captura con precisión PTIME, pero no estoy seguro de querer analizar las especificaciones tratando de aislarlo ...
András Salamon
-1

PPPPP

P=NPP=NPPPNPC

PNP

P=NP

Aunque probablemente no exista para fines reales, seguramente existe y es constructible e implementable. Podría definir ese lenguaje con algo capaz de simular una máquina de Turing hasta un número dado de pasos. IE, capaz de resolver un problema P-completo . Sin embargo, si construye algo así, está casi completo de Turing, excepto por la restricción "dado un número unitario de pasos", que en un lenguaje similar a SQL sería una forma muy extraña de limitarlo a consultas seguras. Podría hacer esto si los pasos son registros de alguna tabla, pero esto todavía no parece nada valioso para fines prácticos.

Victor Stafusa
fuente
2
FOAC0
1
Tampoco veo la relación de vs. P con mi pregunta. Ya sabemos que hay lenguajes que capturan PNPPPFO(LFP)P