Корреляционное исчисление кортежей
Является ли безопасное корреляционное исчисление кортежей полным языком?
2 ответа
Давайте забудем о безопасности. По теореме Кодда, реляционное исчисление эквивалентно логике первого порядка. FOL очень ограничен, он не может выразить тот факт, что существует маршрут от точки A до точки B на некотором графике (он может выразить тот факт, что существует маршрут от точки A до точки B ограниченной длины, например, ∃x ∃y ∃z ∃t маршрут (a, x) и маршрут (x, y), а также маршрут (y,z), маршрут (z,t) и маршрут (t,b) означают, что существует маршрут длиной 4).
См. Описательную сложность для описания того, в чем сила различных логик.
Согласно теореме Кодда, реляционная алгебра и реляционное исчисление эквивалентны. Хорошо известно, что реляционная алгебра не является полной по Тьюрингу, как и реляционное исчисление.
[Править] Вы не можете, например, выполнять агрегатные операции (например, sum, max) или делать рекурсивные запросы в реляционной алгебре / исчислении. Смотрите здесь (ближе к концу).