Пользователь
0,0
рейтинг
16 июня 2012 в 19:51

Разработка → Основы реляционной алгебры

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

Так что если вы собираетесь начать свое обучение в этой области или вам просто стало интересно, прошу под кат.


Реляционная база данных


Для начала введем понятие реляцинной базы данных, в которой будем выполнять все действия.

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

таблица PRODUCTS
ID NAME COMPANY PRICE
123 Печеньки ООО ”Темная сторона” 190
156 Чай ООО ”Темная сторона” 60
235 Ананасы ОАО ”Фрукты” 100
623 Томаты ООО ”Овощи” 130


Таблица состоит из 4х строк, строка в таблице является кортежем в реляционной теории. Множество упорядоченных кортежей называется отношением.
Перед тем как дать определение отношения, введем еще один термин — домен. Домены применительно к таблице это столбцы.

Для ясности, теперь введем строгое определение отношения.

Пусть даны N множеств D1,D2, …. Dn (домены), отношением R над этими множествами называется множество упорядоченных N-кортежей вида <d1,d1,...dn>, где d1 принадлежит D1 и тд. Множества D1,D2,..Dn называются доменами отношения R.
Каждый элемент кортежа представляет собой значение одного из атрибутов, соответствующего одному из доменов.

Ключи в отношениях

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

таблица DRIVERS

COMPANY DRIVER
ООО ”Темная сторона” Владимир
ООО ”Темная сторона” Михаил
ОАО ”Фрукты” Руслан
ООО ”Овощи” Владимир


Видно, что в организации может быть несколько водителей, и чтобы однозначно идентифицировать водителя необходимо и значение из столбца “Название организации” и из “Имя водителя”. Такой ключ называется составным.

В реляционной БД таблицы взаимосвязаны и соотносятся друг с другом как главные и подчиненные. Связь главной и подчиненнной таблицы осуществляется через первичный ключ (primary key) главной таблицы и внешний ключ ( foreign key ) подчиненной таблицы.
Внешний ключ это атрибут или набор атрибутов, который в главной таблице является первичным ключем.

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

Операции реляционной алгебры


Основные восемь операций реляционной алгебры были предложены Э.Коддом.
  • Объединение
  • Пересечение
  • Вычитание
  • Декартово произведение
  • Выборка
  • Проекция
  • Соединение
  • Деление

Первая половина операций аналогична таким же операциям над множествами. Часть операций можно выразить через другие операции. Рассмотрим большую часть операций с примерами.

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

таблица SELLERS

ID SELLER
123 OOO “Дарт”
156 ОАО ”Ведро”
235 ЗАО “Овоще База”
623 ОАО ”Фирма”

Условимся, что в этой таблице ID это внешний ключ, связанный с первичным ключом таблицы PRODUCTS.

Для начала рассмотрим самую простую операцию — имя отношения. Её результатом будет такое же отношение, то есть выполнив операцию PRODUCTS, мы получим копию отношения PRODUCTS.

Проекция

Проекция является операцией, при которой из отношения выделяются атрибуты только из указанных доменов, то есть из таблицы выбираются только нужные столбцы, при этом, если получится несколько одинаковых кортежей, то в результирующем отношении остается только по одному экземпляру подобного кортежа.
Для примера сделаем проекцию на таблице PRODUCTS выбрав из нее ID и PRICE.

Синтаксис операции:
π(ID, PRICE) PRODUCTS

В результате этой операции получим отношение:
ID PRICE
123 190
156 60
235 100
623 130


Выборка

Выборка — это операция, которая выделяет множество строк в таблице, удовлетворяющих заданным условиям. Условием может быть любое логическое выражение.
Для примера сделаем выборку из таблицы с ценой больше 90.

Синтаксис операции:
σ(PRICE>90) PRODUCTS

ID NAME COMPANY PRICE
123 Печеньки ООО ”Темная сторона” 190
235 Ананасы ОАО ”Фрукты” 100
623 Томаты ООО ”Овощи” 130


В условии выборки мы можем использовать любое логическое выражение. Сделаем еще одну выборку с ценой больше 90 и ID товара меньше 300:

σ(PRICE>90 ^ ID<300) PRODUCTS

ID NAME COMPANY PRICE
123 Печеньки ООО ”Темная сторона” 190
235 Ананасы ОАО ”Фрукты” 100


Совместим операторы проекции и выборки. Мы можем это сделать, потому что любой из операторов в результате возвращает отношение и в качестве аргументов использует также отношение.
Из таблицы с продуктами выберем все компании, продающие продуты дешевле 110.

πCOMPANYσ(PRICE<100 ) PRODUCTS

COMPANY
ООО ”Темная сторона”
ОАО ”Фрукты”


Умножение

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

Получим декартово произведения таблиц PRODUCTS и SELLERS.
Синтаксис операции:

PRODUCTS × SELLERS
Можно заметить, что у двух этих таблиц есть одинаковый домен ID. В подобной ситуации домены с одинаковыми названиями получают префикс в виде названия соответствующего отношения, как показано ниже.
Для краткости перемножим не полные отношения, а выборки с условием ID<235

(цветом выделены одни и те же кортежи)
PRODUCTS.ID NAME COMPANY PRICE SELLERS.ID SELLER
123 Печеньки ООО ”Темная сторона” 190 123 OOO “Дарт”
156 Чай ООО ”Темная сторона” 60 156 ОАО ”Ведро”
123 Печеньки ООО ”Темная сторона” 190 156 ОАО ”Ведро”
156 Чай ООО ”Темная сторона” 60 123 OOO “Дарт”


Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90. Без произведения необходимо было бы сначала получить ID продуктов из первой таблицы, потом по этим ID из второй таблицы получить нужные имена SELLER, а с использованием произведения будет такой запрос:

π(SELLER) σ(RODUCTS.ID=SELLERS.ID ^ PRICE<90) PRODUCTS × SELLERS

В результате этой операции получим отношение:

SELLER
ОАО ”Ведро”


Соединение и естественное соединение

Операция соединения обратна операции проекции и создает новое отношение из двух уже существующих. Новое отношение получается конкатенацией кортежей первого и второго отношений, при этом конкатенации подвергаются отношения, в которых совпадают значения заданных атрибутов. В частности, если соединить отношения PRODUCTS и SELLERS, этими атрибутами будут атрибуты доменов ID.

Также для понятности можно представить соеднинение как результат двух операций. Сначала берется произведение исходных таблиц, а потом из полученного отношения мы делаем выборку с условием равенства атрибутов из одинаковых доменов. В данном случае условием явлется равенство PRODUCTS.ID и SELLERS.ID.

Попробуем соединить отношения PRODUCTS и SELLERS и получим отношение.

PRODUCTS.ID NAME COMPANY PRICE SELLERS.ID SELLER
123 Печеньки ООО ”Темная сторона” 190 123 OOO “Дарт”
156 Чай ООО ”Темная сторона” 60 156 ОАО ”Ведро”
235 Ананасы ОАО ”Фрукты” 100 235 ЗАО “Овоще База”
623 Томаты ООО ”Овощи” 130 623 ОАО ”Фирма”


Натуральное соединение получает схожее отношение, но в случае, если у нас корректно настроена схема в базе ( в данном случае первичный ключ таблицы PRODUCTS ID связан с внешним ключем таблицы SELLERS ID), то в результирующем отношении остается один домен ID.

Синтаксис операции:
PRODUCTS ⋈ SELLERS;

Получится такое отношение:

PRODUCTS.ID NAME COMPANY PRICE SELLER
123 Печеньки ООО ”Темная сторона” 190 OOO “Дарт”
156 Чай ООО ”Темная сторона” 60 ОАО ”Ведро”
235 Ананасы ОАО ”Фрукты” 100 ЗАО “Овоще База”
623 Томаты ООО ”Овощи” 130 ОАО ”Фирма”


Пересечение и вычитание.

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

Источники информации

  • Основы использования и проектирования баз данных — В. М. Илюшечкин
  • курс лекций Introduction to Databases — Jennifer Widom, Stanford University


Буду благодарен за аргументированные замечания
Юрий @tsegorah
карма
29,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (42)

  • +1
    Эх… где вы были год назад, когда я только начинал изучать реляционную алгебру? Ваши примеры и доходчивое описание мне бы тогда здорово помогло…
    Вам бы еще написать на «человеческом» языке статью по построению «хорошей» схемы базы данных, чтобы те, только начинают изучать релационку в ВУЗах, смогли ее без проблем потом сдать (МГТУ привет). Тогда цены вам бы не было)
    • +2
      год назад можно было прослушать потрясающие лекции www.db-class.org/course/auth/welcome
      • 0
        Год назад я слушал лекции Григорьева Ю. А., но там в основном были только формулы и такие фразы: «замыкание множества функциональных зависимостей», «свойства соединения без потерь», «первичный и непервичный атрибут»… жуть. Поэтому было сперва сложновато вникнуть во все эти тонкости без наглядных примеров
        • 0
          Не знаю, как было год назад, но в этом году Григорьев давал подробный пример для каждой из этих фраз)
          А хорошую схему БД мы строили медленно и обстоятельно целую пару
  • +2
    >Множество упорядоченных кортежей называется отношением.

    Ну приехали. В реляционках множества принципиально неупорядоченные.
    • +5
      множество упорядоченных кортежей ≠ упорядоченное множество кортежей
      • 0
        а в чём разница?
        • 0
          Во-первых, фраза «упорядоченное множество» вообще не имеет особого смысла. Множество — штука принципиально неупорядоченная, причём не только в реляционной алгебре.

          Во-вторых, множество упорядоченных кортежей — это 1) множество, которое 2) содержит упорядоченные кортежи. С другой стороны, упорядоченное множество кортежей — это 1) упорядоченное множество (что, как я уже писал выше, штука малопонятная), которое 2) содержит кортежи.

          Надеюсь, я ответил на ваш вопрос.
          • 0
            Множество — штука принципиально неупорядоченная, причём не только в реляционной алгебре.
            вот частично упорядоченное множество. чудо природы?)
          • 0
            Ну насчет порядка в множествах вы неправы. Никто не мешает задать порядок для множества и сделать его упорядоченным.
            • 0
              Отвечаю вам и funca.

              Да, я знаю о существовании частично (и не только) упорядоченных множеств. Но дело в том, что множествами они, в строгом смысле, не являются. По определению, частично упорядоченное множество — это упорядоченная пара (которая, в свою очередь, является множеством), состоящая из неупорядоченного (обыкновенного) множества (т.е. содержимого) и бинарного отношения на нём (которое есть множество упорядоченных пар… ну вы поняли).

              Короче говоря, подобная «упорядоченность» — не более чем синтаксический сахар.
              • 0
                нет ни какого строго смысла. конкретные термины отражают конкретные понятия — воспринимаются как есть и употребляются целиком. ну нельзя их делить на слова, дабы извлечь какой-то собственный смысл. иначе можно далеко зайти рассуждая, в строгом смысле, скажем, о морских свинках)
          • 0
            Дайте определение упорядоченного кортежа
            • 0
              Для простоты рассмотрим сначала упорядоченную пару.

              Упорядоченной парой (a, b) называется множество {{b}, {a, b}}. Как легко видеть, такая структура позволяет однозначно идентифицировать как первый, так и второй элемент пары (первый встречается в подмножествах 1 раз, второй — 2).

              Упорядоченным кортежом (a1, a2, ..., an) называется множество {{an}, {a(n-1), an}, ..., {a1, a2, ..., an}}. Идея абсолютно аналогична: элемент с индексом k встречается в подмножествах ровно k раз.

              Нетрудно заметить, что никаких «упорядоченных множеств» здесь нет — присутствует исключительно синтаксический сахар :)
              • 0
                (1, 2, 1) = {{1}, {2, 1}, {1, 2, 1}} = {{1}, {2, 1}, {2, 1}} = {{1}, {2, 1}}
                (2, 1, 1) = {{1}, {1, 1}, {2, 1, 1}} = {{1}, {1, 1}, {2, 1}} = {{1}, {2, 1}}
                (1, 2, 1) == (2, 1, 1)

                в чем подвох?)

                зы: знаете, мне определенно нравится ход ваших рассуждений. «для простоты рассмотрим баланс в кассе нашей организации. вот приход, вот расход. не трудно заметить, что ни какой вашей зарплаты здесь нет — присутствует исключительно синтаксический сахар.» :)
                • 0
                  Да, согласен, написал бред. Ну что ж, тогда сделаем проще.

                  n = 2: (a, b) = {{b}, {a, b}}
                  n = 2: (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}
                  n > 2: (a1, a2, ..., an) = {(1, a1), (2, a2), ..., (n, an)}

                  Вы так говорите, как будто это что-то плохое :)
                  • 0
                    ох… неужели вас не смущает такое обилие двоек?)
                  • 0
                    (a,b,c,d) = {a,{a,b},{{a,b},c},{{{a,b},c},d}} и т.п. На элементах полученного множества проверяем отношение «один элемент является элементом другого» — оно дает орграф без циклов. В нем есть единственная цепочка, проходящая через все вершины. Из этой цепочки и вытаскиваем элементы исходного множества и их порядок.
              • 0
                Верно определить для пары так: (a, b) = { {b}, { b, {a, b} } }. Кортеж в таком случае проще определить индуктивно.
                В любом случае кортеж по определению упорядоченный набор элементов, то есть упорядоченный кортеж — масло масленное.
                Что касается реляционной теории, следует сказать, что каждое отношение состоит из заголовка и тела. Заголовок — множество атрибутов (пар тип-значение). Тело — множество кортежей, согласованных с заголовком. Это важный момент. Для самого отношения нет однозначно определенного порядка атрибутов — поэтому кортежи отношения не тождественны строкам таблицы, как это принято в SQL. Но если мы «овеществляем» отношение, скажем, рисуем его в виде таблицы, то фиксируем порядок атрибутов в заголовке, и, следовательно, определяем порядок на кортежах. При этом таблица с порядком атрибутов A, B, C и таблица с порядком атрибутов B, C, A при одинаковом соответствии элементов кортежа порядку атрибутов математически представляют одно и то же отношение.
  • 0
    Спасибо за статью, всё достаточно доходчиво разъяснили. Посоветуйте, пожалуйста, что-нибудь ещё почитать про введение в реляционную алгебру и реляционное исчисление. Заинтересовало.
    • 0
      классная книжка с картинками: К. Дж. Дейт. «Введение в системы баз данных». не смотрите, что по объему как Гарри Потер — читается так же. :)
    • 0
      citforum.ru/database/advanced_intro/
      Классика жанра от отечественных СУБДводов. Весьма хорошо написано.
  • +5
    Неплохо бы для каждой операции привести и SQL синтаксис.
    • 0
      Да, пожалуйста, с sql было бы намного нагляднее.
  • +3
    Неплохо бы уточнить, что из 8 операций только 5 являются базисными — остальные можно выразить через них.
    • 0
      уточнено в начале, но судя по вашему комментарию недостаточно ясно,
      спасибо, немного позже дополню этот кусок
  • 0
    Исправьте, пожалуйста, номера ID в некоторых таблицах, видимо опечатки, меня сначала ввели в ступор, там где 235 != 135, к примеру.
    • 0
      спасибо, поправил опечатку
  • 0
    Простите меня за глупый вопрос. Но наведите пожалуйста пример из реальной жизни, где может понадобиться умножение? (Предвидя всяческий троллинг, оговорюсь, что в контексте данной статьи :) )
  • 0
    По-моему здесь должна быть только первая строка:

    > Из таблицы с продуктами выберем все компании, продающие продуты дешевле 100.
    >
    > πCOMPANYσ(PRICE
    > COMPANY
    > ООО ”Темная сторона”
    > ОАО ”Фрукты”
    • 0
      ну да, по невнимательности ошибся, спасибо
  • 0
    выборки с условием ID<123

    Наверное, ID<235, судя по результату, или нет?
  • +1
    В частности, если объединить

    Тут лучше исправить на «соединить», чтобы соответствовало заголовку и не вводило в заблуждение, поскольку объединение на английский переводится как UNION.
  • +1
    Хорошо объяснили. Только остается главный вопрос: зачем разводить всю эту алгебру, если и без нее все очевидно и интуитивно понятно? Для чего её использование действительно важно?
    • 0
      сначала был математический алгоритм, потом уже реализация и только потом «все очевидно и интуитивно понятно» ;)
    • 0
      при разработке оптимизационных алгоритмов часто используют именно аппарат реляц. алгебры.
      оптимизатор запросов SQL преобразовывает тектовый запрос в множество логических планов запросов и выбирает лучший, обычно для представления логического плана запросов как раз и используются реляционные выражения.

      потому впринципе, если программист только пишет запросы то ему скорее всего реляц. алгебра никогда и не понадобится, а понадобится только если сам он начнет улучшать оптимизатор СУБД, к примеру, или если хочет глубже разобраться.
  • 0
    Данные операции аналогичны таким же операциям над множествам, так что, я думаю, нет необходимости подробно их расписывать.

    Самого интересного, то и нет. И жаль, что в примерах всё всегда соотносится, не рассматриваются ситуации когда в соединениях с любой из сторон присутствуют ключи, которым нет соответствия со второй.

    P.S. Оказывается я знаю реляционную алгебру :) Основы вернее, никогда бы не подумал. А что-нибудь есть в ней, чего нет в РСУБД?
  • 0
    В данном определении нам интересен термин отношение, но пока оставим его без строго определения. Лучше представим себе таблицу продуктов.

    по идее, термин «отношение» должен быть знаком со школы — например, бинарное отношение равенства (=) чисел в математике. бинарное, потому что ставит в соответствие пару — чисел (x, x). а ещё каждый программист постоянно имеет дело с булевой алегброй и логическим отрицанием not x — одинарным (унарным) отношением.

    кстати о логике. кроме всего прочего, отношение можно определять через функцию, принимающую некоторое количество параметров и возвращающую логическое True, либо False (т.е. предикат). скажем, то же равенство можно выразить предикатом двойкой аргументов вида eq (x, y), а отрицание — not (x) — с одним. можно вообразить функцию, принимающую 3-ку параметров foo(x,y,z) и т.д. «n-ка принадлежит отношению тогда и только тогда, когда предикат на ней возвращает значение True (или «истинно»)».

    допустим, нас интересуют утверждения о том, что некоторый водитель типа Driver имеет отношение к некоторой компании типа Company. функция-предикат будет иметь вид (тип):
    function Boolean company_driver (Company company, Driver driver);
    

    короче, речь идёт о 2-ках вида (company, driver). переходя на множества, на псевдо-sql-подобном языке, отношение между компаниями и водителями можно объявить как-то так:
    CREATE TABLE COMPANY_DRIVER (company Company, driver Driver);
    

    (найди отличия) а его значение — определить, например, перечислив все известные истинные факты, в отношении отношений водителей и компаний:
    INSERT INTO COMPANY_DIRVER (COMPANY, DRIVER) VALUES 
    ('ООО ”Темная сторона”', 'Владимир'),
    ('ООО ”Темная сторона”', 'Михаил'),
    ('ОАО ”Фрукты”', 'Руслан'),
    ('ООО ”Овощи”', 'Владимир');
    

    действительно, это чем-то похоже на таблицу, и отношения часто таком виде изображают. но есть ключевые отличия. например, очевидно, что порядок записи утверждений (кортежей, строк) в отношении, имеет ни какого значения. так же бессмысленно записывать одно и то же утверждение дважды. в таблицах это не так. и да — популярные реляционные базы работают-таки с таблицами.

    в общем, реляционная алгебра — это такая навороченная логика. а ценность реляционных баз состоит в том, что они с лёгкостью оперируют миллионами утверждений, касательно различных фактов, за считанные мгновения, предоставляя мощные средства для создания логической модели предметной области вашего приложения. можно использовать и для других целей, например, для хранения данных =) — но скорее будет хреново (см. NOSQL).
  • +1
    > Домены применительно к таблице это столбцы.
    Домен — это множество значений, которые может принимать заданный атрибут. Если уж применять к таблице, то столбцы — это атрибуты, а не домены.
    Разделите понятия отношения и таблицы, если уж пишите о реляционной теории, а не о SQL
    > Для однозначной идентификации кортежа существует первичный ключ
    В реляционной теории отсутствует понятие первичного ключа, есть просто понятие ключа как набора атрибутов, обладающего свойствами уникальности и неприводимости.
  • 0
    Хорошее описание, жаль в голове сразу встает образ ржавой пилы денормализации, которую мало кому удается избежать при росте проекта.
  • 0
    Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90.

    SELLER
    ОАО ”Ведро”

    а почему сюда не вошел: OOO “Дарт”?
    • 0
      OOO “Дарт” продает товар 123 с ценой больше 90,
      а из результата произведения OOO “Дарт” не попал, потому что PRODUCTS.ID и SELLERS.ID не совпадают, как было указано в условии

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