1. Inicio
  2. Pregunta y respuesta
  3. Cálculo relacional de Tuple

Cálculo relacional de Tuple

2010-01-10 15 views

Respuesta

6

Olvidémonos de la seguridad. Por Codd's theorem, el cálculo relacional es equivalente a la lógica de primer orden. FOL es muy limitado, no puede expresar el hecho de que hay una ruta desde un punto A hasta un punto B en algún gráfico (puede expresar el hecho de que hay una ruta desde un punto A a un punto B de longitud limitada, por ejemplo ∃ x ∃y ∃z ∃t ruta (a, x) y ruta (x, y) y ruta (y, z) y ruta (z, t) y ruta (t, b) significa que hay una ruta de longitud 4).

Consulte descriptive complexity para obtener una descripción de la fuerza de las diferentes lógicas.

Fuente

2010-01-10 17:32:50 sdcvvc

+1

Parece que sabe más sobre esto que yo, sin embargo, ¿por qué los siguientes no pueden expresar que hay una ruta? borde (x, y) -> ruta (x, y) borde (x, y) y borde (y, z) -> ruta (x, z) si el gráfico se representa como un conjunto de hechos sobre bordes, es decir, borde (a, b) y borde (b, c) y borde (c, d) luego el borde de la consulta (a, d) será demostrable por un teorema FOL (por ejemplo, un intérprete de prólogo)) –

+1

Usted dice que la ruta es la más mínima relación transitiva que satisface el borde (x, y) -> ruta (x, y). Esta definición requiere menos punto fijo. Para definir una nueva relación en cálculo de tuplas, puede usar intersección, unión, proyección ... pero no es posible decir "enrutar es una relación que cumple las siguientes condiciones ...". También puede cuantificar las relaciones, pero esa es una lógica de orden superior, y la cuantificación solo se permite en individuos en FOL. – sdcvvc

+0

+1 gracias por la explicación sdcwc –

1

De acuerdo con Codd's Theorem, el álgebra relacional y el cálculo relacional son equivalentes. Es bien sabido que el álgebra relacional no es Turing completa, por lo que tampoco lo es el cálculo relacional.

[Editar] No puede, por ejemplo, hacer operaciones agregadas (como suma, máximo) o realizar consultas recursivas en álgebra relacional/cálculo. Ver here (cerca del final).

Fuente

2010-01-10 17:34:15

+2

O estás equivocado o Larry Watanabe sí. No tengo idea del tema, pero ¡esto se está poniendo interesante! (va a buscar palomitas de maíz) –

+0

Ahora el álgebra relacional no es Turing Complete es más conocido :) –

+0

Sin embargo, al leer el enlace de otro póster al teorema de Codd, el álgebra relacional no es equivalente al cálculo relacional: el álgebra relacional es esencialmente equivalente a la lógica proposicional mientras que el álgebra relacional es equivalente a FOL. –

Cuestiones relacionadas

 Cuestiones relacionadas