imported>Naut-rena: удаление ссылки на википедию в качестве источника

2026-03-12T22:26:50Z

удаление ссылки на википедию в качестве источника

Новая страница

'''Реляционная [[алгебра]]''' — замкнутая система [[Операция (математика)|операций]] над [[Отношение (реляционная модель)|отношениями]] в [[Реляционная модель данных|реляционной модели данных]]. Операции реляционной алгебры также называют ''реляционными операциями''.

Первоначальный набор из 8 операций был предложен [[Кодд, Эдгар|Э. Коддом]] в 1970-е годы и включал как операции, которые до сих пор используются ([[Реляционная алгебра#Проекция|проекция]], [[Реляционная алгебра#Соединение|соединение]] и т. д.), так и операции, которые не вошли в употребление (например, [[Реляционная алгебра#Деление|деление]] отношений).

В процессе развития реляционной теории и практики было предложено несколько новых реляционных операций, например полусоединение (''SEMI-JOIN'') и полуразность, или анти-полусоединение (''ANTI-SEMI-JOIN'')<ref>{{Cite web |url=http://blogs.msdn.com/b/craigfr/archive/2006/07/19/671712.aspx |title=Introduction to Joins |access-date=2011-11-14 |archive-date=2011-11-26 |archive-url=https://web.archive.org/web/20111126073325/http://blogs.msdn.com/b/craigfr/archive/2006/07/19/671712.aspx |url-status=live }}</ref><ref>Дейт, Кристофер. SQL и реляционная теория. Как грамотно писать код на SQL. — Символ-Плюс, 2010</ref>, ''CROSS APPLY'' и ''OUTER APPLY'', [[транзитивное замыкание]] (''TCLOSE'') и др.

Поскольку многие операции выразимы друг через друга, в составе реляционной алгебры можно выделить несколько вариантов базиса (набора операций, через который выразимы все остальные). Наиболее известный и строго определённый базис ([[алгебра А]]) предложен [[Дейт, Кристофер|Кристофером Дейтом]] и [[Дарвен, Хью|Хью Дарвеном]]<ref>К. Дейт, Хью Дарвен. Основы будущих систем баз данных. Третий манифест. М: Янус-К, 2004.</ref>.

Реляционная алгебра и [[реляционное исчисление]] эквивалентны по своей выразительной силе{{sfn|Грей|1989|с=188}}. Существуют правила преобразования запросов между ними.

Основное применение реляционной алгебры — предоставить теоретическую основу для [[Реляционная база данных|реляционных баз данных]], особенно [[Язык запросов|языков запросов]] для таких баз данных, главным из которых является [[SQL]].

== Замкнутость реляционной алгебры ==
Реляционная алгебра представляет собой набор таких операций над отношениями, что результат каждой из операций также является отношением. Это свойство алгебры называется ''замкнутостью''.

Операции над одним отношением называются ''унарными'', над двумя отношениями — ''бинарными'', над тремя — ''тернарными'' (таковые практически неизвестны).

Пример унарной операции — проекция, пример [[Бинарная операция|бинарной операции]] — объединение.

''N''-арную реляционную операцию ''f'' можно представить функцией, возвращающей отношение и имеющей ''n'' отношений в качестве аргументов:

: <math>R = f(R_1, R_2,\dots, R_n)</math>

Поскольку реляционная алгебра является замкнутой, в качестве операндов в реляционные операции можно подставлять другие выражения реляционной алгебры (подходящие по типу):

: <math>R = f(f_1(R_{11},R_{12},\dots),f_2(R_{21},R_{22},\dots),\dots)</math>

В реляционных выражениях можно использовать вложенные выражения сколь угодно сложной структуры.

== Ограничения на операции ==
Некоторые реляционные операции, в частности, операции ''объединения'', ''пересечения'' и ''вычитания'', требуют, чтобы отношения имели совпадающие (одинаковые) заголовки (схемы). Это означает, что совпадают количество атрибутов, названия атрибутов и тип ([[Домен (базы данных)|домен]]) одноимённых атрибутов.

Некоторые отношения формально не являются совместимыми из-за различия в названиях атрибутов, но становятся таковыми после применения операции переименования атрибутов.

Операция декартова произведения требует, чтобы отношения-операнды не обладали одноимёнными атрибутами. Отношения называются совместимыми по взятию расширенного декартова произведения, если [[пересечение множеств]] имён атрибутов, взятых из их схем отношений, пусто.

== Операции реляционной алгебры ==
Далее перечислены некоторые операции реляционной алгебры, которые представляют либо исторический, либо практический интерес. Все операции перечислить невозможно, поскольку любая операция, удовлетворяющая определению реляционной, является частью реляционной алгебры.

=== Переименование ===
Результатом применения операции переименования атрибутов является отношение с изменёнными именами атрибутов.

[[Синтаксис]]:

: ''R'' RENAME ''Atr1, Atr2, '' … AS ''NewAtr1, NewAtr2, '' …
где 
: ''R'' — отношение
: ''Atr1, Atr2, '' … — исходные имена атрибутов
: ''NewAtr1, NewAtr2, '' … — новые имена атрибутов.

=== Объединение ===
[[Файл:Venn0111.svg|thumb|[[Диаграмма Венна]] для <math>A \cup B</math> (объединение).]]

Отношение с тем же заголовком, что и у совместимых по типу отношений ''A'' и ''B'', и телом, состоящим из [[Кортеж (информатика)|кортежей]], принадлежащих или ''A'', или ''B'', или обоим отношениям. 
Синтаксис: 
: ''A'' UNION ''B''

=== Пересечение ===
[[Файл:Venn0001.svg|thumb|[[Диаграмма Венна]] для <math>A \cap B</math> (пересечение).]]

Отношение с тем же заголовком, что и у отношений ''A'' и ''B'', и телом, состоящим из кортежей, принадлежащих одновременно обоим отношениям ''A'' и ''B''. 
Синтаксис: 
: ''A'' INTERSECT ''B''

=== Вычитание ===
[[Файл:Venn0100.svg|thumb|[[Диаграмма Венна]] для <math>A \setminus B</math> (вычитание).]]

Отношение с тем же заголовком, что и у совместимых по типу отношений ''A'' и ''B'', и телом, состоящим из кортежей, принадлежащих отношению ''A'' и не принадлежащих отношению ''B''. 
Синтаксис: 
: ''A'' MINUS ''B''

=== Операция присваивания ===
Операция присваивания (:=) позволяет сохранить результат вычисления реляционного выражения в существующем отношении.

=== [[Декартово произведение]] ===
Отношение, заголовок (''A''1, ''A''2, …, ''A''''n'', ''B''1, ''B''2, …, ''B''''m'') которого является сцеплением заголовков отношений ''A''(''A''1, ''A''2, …, ''A''''n'') и ''B''(''B''1, ''B''2, …, ''B''''m''), а тело состоит из кортежей, являющихся всеми вариантами сцеплений кортежей отношений ''A'' и ''B'': (''a''1, ''a''2, …, ''a''''n'', ''b''1, ''b''2, …,''b''''m''),

таких, что
: (''a''1, ''a''2, …, ''a''''n'') ∈ ''A'',
: (''b''1, ''b''2, …, ''b''''m'') ∈ ''B''.

Синтаксис:
: ''A'' TIMES ''B''

=== Выборка (ограничение) ===
Отношение с тем же заголовком, что и у отношения ''A'', и телом, состоящим из кортежей, значения атрибутов которых при подстановке в условие ''c'' дают значение ИСТИНА. ''c'' представляет собой [[логическое выражение]], в которое могут входить атрибуты отношения ''A'' и/или скалярные выражения. 
Синтаксис: 
: ''A'' WHERE ''c''

[[Выборка]] записывается как <math>\sigma_{a \theta b}( R )</math> или <math>\sigma_{a \theta v}( R )</math> где:
* {{mvar|a}} и {{mvar|b}} — имена атрибутов
* {{mvar|θ}} — одна из бинарных операций <math>\{\;<, \le, =, \ne, \ge, \;>\}</math>
* {{mvar|v}} — постоянная величина
* {{mvar|R}} отношение

=== Проекция ===
Проекцией кортежа <math>t = {\{(a, v) \ | \ a \in A, v \in D\}}</math>, отвечающего множеству атрибутов <math>A = \{A_1,\ A_2, \ ..., \ A_n \}</math>, на подмножество <math>A' = \{A_{i_1},\;A_{i_2},\;\ldots,\;A_{i_k}\}</math> множества атрибутов исходного кортежа называется кортеж

<math>t[A'] = {\{(a, v) \ | \ (a, v) \in t, a \in A'\}}</math>,

полученный из исходного кортежа удалением пар, содержащих атрибуты, не входящие в множество атрибутов <math>A'</math>.

Проекция — [[унарная операция]], которая позволяет получить «вертикальное» [[подмножество]] данного [[Отношение (реляционная модель)|отношения]], то есть такое подмножество, которое получается выбором специфицированных [[атрибут]]ов с последующим исключением, если это необходимо, избыточных [[дубликат]]ов [[Кортеж (информатика)|кортежей]].
Пусть дано отношение <math>A</math> с именами атрибутов <math>A_1,\;A_2,\;\ldots,\;A_n</math>, то есть <math>A(A_1,\;A_2,\;\ldots,\;A_n)</math> и некоторое подмножество <math>\{A_{i_1},\;A_{i_2},\;\ldots,\;A_{i_k}\}</math> множества имён атрибутов. Результатом проекции отношения по выбранным именам атрибутов называется новое отношение <math>A(A_{i_1},\;A_{i_2},\;\ldots,\;A_{i_k})</math> с телом, состоящим из проекций кортежей исходного отношения <math>A</math> на множество имен атрибутов <math>\{A_{i_1},\;A_{i_2},\;\ldots,\;A_{i_k}\}</math>. Другими словами, новое отношение получается из исходного вычёркиванием атрибутов, не входящих в выбранное множество, с последующим возможным удалением избыточных дубликатов кортежей.

При осуществлении проекции необходимо задать проецируемое отношение и некий набор его атрибутов, который станет заголовком результирующего.

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

Синтаксис: 
: A[X, Y, …, Z]
или 
: PROJECT ''A {x, y, …, z}''

=== Соединение ===
{{main|Операция соединения (реляционная алгебра)}}
Операция соединения отношений ''A'' и ''B'' по [[Предикат|предикату]] ''P'' логически эквивалентна [[Композиция функций|последовательному применению]] операций декартова произведения ''A'' и ''B'' и выборки по предикату ''P''. Если в отношениях имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать.

Синтаксис:
: (''A'' TIMES ''B'') WHERE ''P''

=== Деление ===
Отношение с заголовком ''(X1, X2, …, Xn)'' и телом, содержащим множество кортежей ''(x1, x2, …, xn)'', таких, что для всех кортежей ''(y1, y2, …, ym) ∈ B'' в отношении ''A(X1, X2, …, Xn, Y1, Y2, …, Ym)'' найдётся кортеж ''(x1, x2, …, xn, y1, y2, …, ym)''.

Синтаксис:
: ''A'' DIVIDEBY ''B''

== Выразимость одних операций через другие ==
Некоторые из реляционных операций могут быть выражены через другие реляционные операторы.
; Оператор соединения
Оператор соединения определяется через операторы декартова произведения и выборки следующим образом:
: (A TIMES B) WHERE X=Y
: где X и Y атрибуты соответственно отношений A и B с первоначально равными именами.
; Оператор пересечения
Оператор пересечения выражается через [[вычитание]] следующим образом:
: A INTERSECT B = A MINUS (A MINUS B)
; Оператор деления
Оператор деления выражается через операторы вычитания, декартова произведения и проекции следующим образом:
: A DIVIDEBY B = A[X] MINUS ((A[X] TIMES B) MINUS A)[X]

== Реализации ==
Первым языком запросов, основанным на алгебре Кодда, был Alpha, разработанный самим Коддом. Впоследствии был создан ISBL, и эта новаторская работа была оценена многими авторитетными специалистами<ref>{{cite web |title = Edgar F. Codd - A.M. Turing Award Laureate |url = https://amturing.acm.org/award_winners/codd_1000892.cfm |author = C. J. Date |website = amturing.acm.org |access-date = 2020-12-27 |archive-date = 2017-12-23 |archive-url = https://web.archive.org/web/20171223141345/http://amturing.acm.org/award_winners/codd_1000892.cfm |url-status = live }}</ref> как показывающая способ превратить идею Кодда в полезный язык. Business System 12 была недолговечной [[Реляционная СУБД|реляционной СУБД]], которая последовала примеру ISBL.

В 1998 году [[Дейт, Кристофер|Кристофер Дэйт]] и Хью Дарвен предложили язык под названием [[Tutorial D]], предназначенный для использования в преподавании теории реляционных баз данных, этот язык запросов также был основан на идеях ISBL. Rel — это реализация Tutorial D.

Даже язык запросов [[SQL]] слабо основан на реляционной алгебре, хотя операнды в SQL ([[Таблица (база данных)|таблицы]]) это не совсем [[Отношение (реляционная модель)|отношения]], и несколько полезных теорем реляционной алгебры не выполняются в SQL (возможно, в ущерб оптимизаторам и/или пользователям). Модель таблицы SQL — это [[мультимножество]], а не [[множество]]. Например, выражение <math>(R \cup S) \setminus T = (R \setminus T) \cup (S \setminus T)</math> — это теорема реляционной алгебры на множествах, но не реляционной алгебры на мультимножествах; для изучения реляционной алгебры на мультимножествах см. главу 5 «Полного» учебника [[Гарсия-Молина, Гектор|Гарсиа-Молины]], [[Ульман, Джеффри Дэвид|Ульмана]] и Видома<ref name="Garcia-MolinaUllman2009">{{cite book |author1 = [[Гарсия-Молина, Гектор|Hector Garcia-Molina]] |author2 = [[Ульман, Джеффри Дэвид|Jeffrey D. Ullman]] |author3 = Jennifer Widom |title = Database systems: the complete book |ссылка = https://archive.org/details/databasesystemsc0000_2ndedgarc|year = 2009 |publisher = Pearson Prentice Hall |isbn = 978-0-13-187325-4 |edition = 2nd }}</ref>.

== Примечания ==
{{Примечания}}

== Литература ==
* {{книга
|автор=Грей П.
|заглавие=Логика, алгебра и базы данных
|original=Logic, algebra and databases
|место=М.
|издательство=Машиностроение
|год=1989
|страниц=368
|страницы=188—213
|ref=Грей
}}
* {{книга
|автор = [[Дейт, Кристофер|Дейт К. Дж.]]
|заглавие = [[Введение в системы баз данных]]
|оригинал = Introduction to Database Systems
|ссылка =
|издание = 8-е изд
|место = М.
|издательство = [[Вильямс (издательство)|Вильямс]]
|год = 2005
|страниц = 1328
|isbn = 5-8459-0788-8 (рус.) 0-321-19784-4 (англ.)
|ref=Дейт К. Дж.
}}

== Ссылки ==
* http://www.citforum.ru/database/dblearn/

{{databases}}

[[Категория:Реляционная алгебра|*]]

Реляционная алгебра - История изменений

imported>Naut-rena: удаление ссылки на википедию в качестве источника