Mi comprensión sobre el concepto de Codd de "consulta segura" fue creado para asegurar que una consulta siempre terminaría. Una capacidad clave de una máquina de Turing es que puede trabajar en cálculos infinitos (y así no está garantizado para terminar). ¿Si se elimina la restricción de la consulta segura, cálculo relacional sería Turing-completo ya que eso significa que no tiene que terminar?
Respuesta
¿Demasiados anuncios?
solarce
Puntos
483
No sé si esto es correcto, pero tengo una hipótesis. Si hemos permitido que la libre de las variables de la fórmula, entonces podríamos pensar en las consultas como las funciones. Por ejemplo, considere la siguiente consulta:
{ <A, B, C> | <A, B, C> \in R and A = x}
Si la consulta anterior ha resultado M, se puede considerar que para ser una función de la forma lambda x.M. Si permitimos que las relaciones sean variables libres, podemos definir una función de la forma lambda R.R. Ahora, si nos permiten "de orden superior consultas", es decir, las consultas que puede realizar consultas consultas, se puede representar a la Iglesia números (con q de ser una consulta):
0 = lambda qR.R
1 = lambda qR.q R
2 = lambda qR.q (q R)
3 = lambda qR.q (q (q R))
Por lo tanto, creo que el cálculo relacional también puede ser un cálculo lambda, y por lo tanto se Turing-completo. ¿Alguien puede decirme si estoy en el camino correcto?
