cálculo relacional tupla

Question

É tupla segura relacional cálculo um turing linguagem completa?

Answer 1

Vamos esquecer a segurança. Pelo teorema , cálculo relacional do Codd é equivalente a lógica de primeira ordem. FOL é muito limitado, que não pode expressar o facto de que há um percurso a partir de um ponto A para o ponto B, em alguns gráfico (que pode expressar o facto de que há um percurso a partir de um ponto A para o ponto B de comprimento limitado, por exemplo ? x ?y ?z ?t via (a, x) e a via (x, y) e a via (Y, Z) e a via (z, t) e a via (t, b) significa que não há uma via de comprimento 4).

descritivo complexidade para uma descrição do que é a força de diferentes lógicas.

Answer 2

De acordo com a Codd do Teorema , álgebra relacional e cálculo relacional são equivalentes. é bem sabido que a álgebra relacional não é Turing completa, então, nem é cálculo relacional.

[Edit] Você não pode, por exemplo, fazer operações de agregados (como soma, max) ou fazer recursiva consultas em relacional álgebra / cálculo. Consulte aqui (perto do final) .