Phép tính quan hệ Tuple

Question

Tính toán quan hệ tuple an toàn có phải là một ngôn ngữ hoàn chỉnh không?

Answer 1

Hãy quên đi sự an toàn. Bằng cách Codd's theorem, phép tính quan hệ tương đương với logic đơn hàng đầu tiên. FOL là rất hạn chế, nó không thể diễn tả thực tế rằng có một tuyến đường từ điểm A đến điểm B trong một số đồ thị (nó có thể thể hiện thực tế rằng có một tuyến đường từ điểm A đến điểm B trong chiều dài giới hạn, ví dụ ∃ x ∃y ∃z ∃t tuyến đường (a, x) và tuyến đường (x, y) và tuyến đường (y, z) và tuyến đường (z, t) và tuyến đường (t, b) có nghĩa là có tuyến đường có chiều dài 4).

Xem descriptive complexity để biết mô tả về độ mạnh của các lôgic khác nhau.

Answer 2

Theo Codd's Theorem, đại số quan hệ và phép tính quan hệ tương đương. Nó là nổi tiếng rằng đại số quan hệ không phải là Turing Complete, vì vậy không phải là tính toán quan hệ.

[Chỉnh sửa] Bạn không thể, ví dụ: thực hiện các phép toán tổng hợp (chẳng hạn như tổng, tối đa) hoặc thực hiện truy vấn đệ quy trong đại số/tính toán quan hệ. Xem here (gần cuối).