Теорема Коддса - Codds theorem - Wikipedia

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

Теорема названа в честь Эдгар Ф. Кодд, отец реляционная модель для управления базой данных.

Независимая от домена реляционное исчисление запросы - это именно те запросы реляционного исчисления, которые инвариантны при выборе доменов значений помимо тех, которые появляются в самой базе данных. То есть исключаются запросы, которые могут возвращать разные результаты для разных доменов. Примером такого запрещенного запроса является запрос «выбрать все кортежи, кроме тех, которые встречаются в отношении R», где R - отношение в базе данных. Предполагая разные домены, то есть наборы элементарных элементов данных, из которых могут быть построены кортежи, этот запрос возвращает разные результаты и, таким образом, явно не зависит от домена.

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

Реляционное исчисление по сути эквивалентно логике первого порядка,[1] и действительно, теорема Кодда была известна логикам с конца 1940-х годов.[2][3]

Языки запросов, эквивалентные по выразительной способности реляционной алгебре, были названы относительно полный пользователя Codd. По теореме Кодда сюда входит реляционное исчисление. Ясно, что реляционная полнота не означает, что любой интересный запрос к базе данных может быть выражен на реляционно полных языках. Известные примеры невыразимых запросов включают простые скопления (подсчет кортежей или суммирование значений, встречающихся в кортежах, которые являются операциями, выражаемыми в SQL, но не в реляционной алгебре) и вычисление переходное закрытие графа, заданного его бинарным отношением ребер (см. также выразительная сила ). Теорема Кодда также не учитывает Пустые значения SQL и трехзначная логика они влекут за собой; логическая трактовка нулей по-прежнему вызывает споры.[4] Кроме того, в SQL есть мультимножество семантика и позволяет дублировать строки. Тем не менее реляционная полнота представляет собой важный критерий, по которому можно сравнивать выразительную силу языков запросов.

Примечания

  1. ^ Абитебул, Серж; Халл, Ричард Б.; Виану, Виктор (1995). Основы баз данных. Эддисон-Уэсли. ISBN  0-201-53771-0.
  2. ^ Chin, L.H .; Тарский, А. (1948). «Замечания о проективных алгебрах». Бюллетень Американского математического общества. 54 (1): 80–81. Дои:10.1090 / S0002-9904-1948-08948-0.
  3. ^ Тарский, А .; Томпсон, Ф. Б. (1952). «Некоторые общие свойства цилиндрических алгебр». Бюллетень Американского математического общества. 58 (1): 65. Дои:10.1090 / S0002-9904-1952-09549-5.
  4. ^ Последние работы, расширяющие теорему Кодда в этом направлении, см. Франкони, Энрико; Тессарис, Серджио (2012). "О логике пустых значений SQL" (PDF). Материалы 6-го Международного семинара Альберто Мендельзона по основам управления данными, Ору-Прету, Бразилия, 27–30 июня 2012 г.: 114–128.

Рекомендации

внешняя ссылка