Реляционное исчисление кортежей

Question

Является ли безопасное реляционное исчисление кортежей полным языком по Тьюрингу?

Answer 1

Давайте забудем о безопасности.Автор: Теорема Кодда, реляционное исчисление эквивалентно логике первого порядка.FOL очень ограничен, он не может выразить тот факт, что на некотором графике существует маршрут из точки A в точку B (он может выразить тот факт, что существует маршрут из точки A в точку B ограниченной длины, например ∃x ∃y ∃ z ∃t маршрут (a,x) и маршрут (x, y) и маршрут (y, z) и маршрут (z, t) и маршрут (t, b) означают, что существует маршрут длиной 4).

Видишь описательная сложность для описания того, в чем сила различных логик.

Answer 2

Согласно Теорема Кодда, реляционная алгебра и реляционный анализ эквивалентны.Хорошо известно, что реляционная алгебра не является полной по Тьюрингу, поэтому и реляционное исчисление не является полным.

[Править] Вы не можете, например, выполнять агрегированные операции (такие как sum, max) или выполнять рекурсивные запросы в реляционной алгебре / математическом анализе.Видишь здесь (ближе к концу).