Комментарии 42
Эх… где вы были год назад, когда я только начинал изучать реляционную алгебру? Ваши примеры и доходчивое описание мне бы тогда здорово помогло…
Вам бы еще написать на «человеческом» языке статью по построению «хорошей» схемы базы данных, чтобы те, только начинают изучать релационку в ВУЗах, смогли ее без проблем потом сдать (МГТУ привет). Тогда цены вам бы не было)
Вам бы еще написать на «человеческом» языке статью по построению «хорошей» схемы базы данных, чтобы те, только начинают изучать релационку в ВУЗах, смогли ее без проблем потом сдать (МГТУ привет). Тогда цены вам бы не было)
год назад можно было прослушать потрясающие лекции www.db-class.org/course/auth/welcome
Год назад я слушал лекции Григорьева Ю. А., но там в основном были только формулы и такие фразы: «замыкание множества функциональных зависимостей», «свойства соединения без потерь», «первичный и непервичный атрибут»… жуть. Поэтому было сперва сложновато вникнуть во все эти тонкости без наглядных примеров
>Множество упорядоченных кортежей называется отношением.
Ну приехали. В реляционках множества принципиально неупорядоченные.
Ну приехали. В реляционках множества принципиально неупорядоченные.
множество упорядоченных кортежей ≠ упорядоченное множество кортежей
а в чём разница?
Во-первых, фраза «упорядоченное множество» вообще не имеет особого смысла. Множество — штука принципиально неупорядоченная, причём не только в реляционной алгебре.
Во-вторых, множество упорядоченных кортежей — это 1) множество, которое 2) содержит упорядоченные кортежи. С другой стороны, упорядоченное множество кортежей — это 1) упорядоченное множество (что, как я уже писал выше, штука малопонятная), которое 2) содержит кортежи.
Надеюсь, я ответил на ваш вопрос.
Во-вторых, множество упорядоченных кортежей — это 1) множество, которое 2) содержит упорядоченные кортежи. С другой стороны, упорядоченное множество кортежей — это 1) упорядоченное множество (что, как я уже писал выше, штука малопонятная), которое 2) содержит кортежи.
Надеюсь, я ответил на ваш вопрос.
Множество — штука принципиально неупорядоченная, причём не только в реляционной алгебре.вот частично упорядоченное множество. чудо природы?)
Ну насчет порядка в множествах вы неправы. Никто не мешает задать порядок для множества и сделать его упорядоченным.
Отвечаю вам и funca.
Да, я знаю о существовании частично (и не только) упорядоченных множеств. Но дело в том, что множествами они, в строгом смысле, не являются. По определению, частично упорядоченное множество — это упорядоченная пара (которая, в свою очередь, является множеством), состоящая из неупорядоченного (обыкновенного) множества (т.е. содержимого) и бинарного отношения на нём (которое есть множество упорядоченных пар… ну вы поняли).
Короче говоря, подобная «упорядоченность» — не более чем синтаксический сахар.
Да, я знаю о существовании частично (и не только) упорядоченных множеств. Но дело в том, что множествами они, в строгом смысле, не являются. По определению, частично упорядоченное множество — это упорядоченная пара (которая, в свою очередь, является множеством), состоящая из неупорядоченного (обыкновенного) множества (т.е. содержимого) и бинарного отношения на нём (которое есть множество упорядоченных пар… ну вы поняли).
Короче говоря, подобная «упорядоченность» — не более чем синтаксический сахар.
Дайте определение упорядоченного кортежа
Для простоты рассмотрим сначала упорядоченную пару.
Упорядоченной парой
Упорядоченным кортежом
Нетрудно заметить, что никаких «упорядоченных множеств» здесь нет — присутствует исключительно синтаксический сахар :)
Упорядоченной парой
(a, b) называется множество {{b}, {a, b}}. Как легко видеть, такая структура позволяет однозначно идентифицировать как первый, так и второй элемент пары (первый встречается в подмножествах 1 раз, второй — 2).Упорядоченным кортежом
(a1, a2, ..., an) называется множество {{an}, {a(n-1), an}, ..., {a1, a2, ..., an}}. Идея абсолютно аналогична: элемент с индексом k встречается в подмножествах ровно k раз.Нетрудно заметить, что никаких «упорядоченных множеств» здесь нет — присутствует исключительно синтаксический сахар :)
(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)
в чем подвох?)
зы: знаете, мне определенно нравится ход ваших рассуждений. «для простоты рассмотрим баланс в кассе нашей организации. вот приход, вот расход. не трудно заметить, что ни какой вашей зарплаты здесь нет — присутствует исключительно синтаксический сахар.» :)
(2, 1, 1) = {{1}, {1, 1}, {2, 1, 1}} = {{1}, {1, 1}, {2, 1}} = {{1}, {2, 1}}
(1, 2, 1) == (2, 1, 1)
в чем подвох?)
зы: знаете, мне определенно нравится ход ваших рассуждений. «для простоты рассмотрим баланс в кассе нашей организации. вот приход, вот расход. не трудно заметить, что ни какой вашей зарплаты здесь нет — присутствует исключительно синтаксический сахар.» :)
Да, согласен, написал бред. Ну что ж, тогда сделаем проще.
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)}
Вы так говорите, как будто это что-то плохое :)
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)}
Вы так говорите, как будто это что-то плохое :)
ох… неужели вас не смущает такое обилие двоек?)
(a,b,c,d) = {a,{a,b},{{a,b},c},{{{a,b},c},d}} и т.п. На элементах полученного множества проверяем отношение «один элемент является элементом другого» — оно дает орграф без циклов. В нем есть единственная цепочка, проходящая через все вершины. Из этой цепочки и вытаскиваем элементы исходного множества и их порядок.
Верно определить для пары так: (a, b) = { {b}, { b, {a, b} } }. Кортеж в таком случае проще определить индуктивно.
В любом случае кортеж по определению упорядоченный набор элементов, то есть упорядоченный кортеж — масло масленное.
Что касается реляционной теории, следует сказать, что каждое отношение состоит из заголовка и тела. Заголовок — множество атрибутов (пар тип-значение). Тело — множество кортежей, согласованных с заголовком. Это важный момент. Для самого отношения нет однозначно определенного порядка атрибутов — поэтому кортежи отношения не тождественны строкам таблицы, как это принято в SQL. Но если мы «овеществляем» отношение, скажем, рисуем его в виде таблицы, то фиксируем порядок атрибутов в заголовке, и, следовательно, определяем порядок на кортежах. При этом таблица с порядком атрибутов A, B, C и таблица с порядком атрибутов B, C, A при одинаковом соответствии элементов кортежа порядку атрибутов математически представляют одно и то же отношение.
В любом случае кортеж по определению упорядоченный набор элементов, то есть упорядоченный кортеж — масло масленное.
Что касается реляционной теории, следует сказать, что каждое отношение состоит из заголовка и тела. Заголовок — множество атрибутов (пар тип-значение). Тело — множество кортежей, согласованных с заголовком. Это важный момент. Для самого отношения нет однозначно определенного порядка атрибутов — поэтому кортежи отношения не тождественны строкам таблицы, как это принято в SQL. Но если мы «овеществляем» отношение, скажем, рисуем его в виде таблицы, то фиксируем порядок атрибутов в заголовке, и, следовательно, определяем порядок на кортежах. При этом таблица с порядком атрибутов A, B, C и таблица с порядком атрибутов B, C, A при одинаковом соответствии элементов кортежа порядку атрибутов математически представляют одно и то же отношение.
Спасибо за статью, всё достаточно доходчиво разъяснили. Посоветуйте, пожалуйста, что-нибудь ещё почитать про введение в реляционную алгебру и реляционное исчисление. Заинтересовало.
классная книжка с картинками: К. Дж. Дейт. «Введение в системы баз данных». не смотрите, что по объему как Гарри Потер — читается так же. :)
citforum.ru/database/advanced_intro/
Классика жанра от отечественных СУБДводов. Весьма хорошо написано.
Классика жанра от отечественных СУБДводов. Весьма хорошо написано.
Неплохо бы для каждой операции привести и SQL синтаксис.
Неплохо бы уточнить, что из 8 операций только 5 являются базисными — остальные можно выразить через них.
Исправьте, пожалуйста, номера ID в некоторых таблицах, видимо опечатки, меня сначала ввели в ступор, там где 235 != 135, к примеру.
Простите меня за глупый вопрос. Но наведите пожалуйста пример из реальной жизни, где может понадобиться умножение? (Предвидя всяческий троллинг, оговорюсь, что в контексте данной статьи :) )
По-моему здесь должна быть только первая строка:
> Из таблицы с продуктами выберем все компании, продающие продуты дешевле 100.
>
> πCOMPANYσ(PRICE
> COMPANY
> ООО ”Темная сторона”
> ОАО ”Фрукты”
> Из таблицы с продуктами выберем все компании, продающие продуты дешевле 100.
>
> πCOMPANYσ(PRICE
> COMPANY
> ООО ”Темная сторона”
> ОАО ”Фрукты”
выборки с условием ID<123
Наверное,
ID<235, судя по результату, или нет?В частности, если объединить
Тут лучше исправить на «соединить», чтобы соответствовало заголовку и не вводило в заблуждение, поскольку объединение на английский переводится как UNION.
Хорошо объяснили. Только остается главный вопрос: зачем разводить всю эту алгебру, если и без нее все очевидно и интуитивно понятно? Для чего её использование действительно важно?
сначала был математический алгоритм, потом уже реализация и только потом «все очевидно и интуитивно понятно» ;)
при разработке оптимизационных алгоритмов часто используют именно аппарат реляц. алгебры.
оптимизатор запросов SQL преобразовывает тектовый запрос в множество логических планов запросов и выбирает лучший, обычно для представления логического плана запросов как раз и используются реляционные выражения.
потому впринципе, если программист только пишет запросы то ему скорее всего реляц. алгебра никогда и не понадобится, а понадобится только если сам он начнет улучшать оптимизатор СУБД, к примеру, или если хочет глубже разобраться.
оптимизатор запросов SQL преобразовывает тектовый запрос в множество логических планов запросов и выбирает лучший, обычно для представления логического плана запросов как раз и используются реляционные выражения.
потому впринципе, если программист только пишет запросы то ему скорее всего реляц. алгебра никогда и не понадобится, а понадобится только если сам он начнет улучшать оптимизатор СУБД, к примеру, или если хочет глубже разобраться.
Данные операции аналогичны таким же операциям над множествам, так что, я думаю, нет необходимости подробно их расписывать.
Самого интересного, то и нет. И жаль, что в примерах всё всегда соотносится, не рассматриваются ситуации когда в соединениях с любой из сторон присутствуют ключи, которым нет соответствия со второй.
P.S. Оказывается я знаю реляционную алгебру :) Основы вернее, никогда бы не подумал. А что-нибудь есть в ней, чего нет в РСУБД?
Самого интересного, то и нет. И жаль, что в примерах всё всегда соотносится, не рассматриваются ситуации когда в соединениях с любой из сторон присутствуют ключи, которым нет соответствия со второй.
P.S. Оказывается я знаю реляционную алгебру :) Основы вернее, никогда бы не подумал. А что-нибудь есть в ней, чего нет в РСУБД?
В данном определении нам интересен термин отношение, но пока оставим его без строго определения. Лучше представим себе таблицу продуктов.
по идее, термин «отношение» должен быть знаком со школы — например, бинарное отношение равенства (=) чисел в математике. бинарное, потому что ставит в соответствие пару — чисел (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).
> Домены применительно к таблице это столбцы.
Домен — это множество значений, которые может принимать заданный атрибут. Если уж применять к таблице, то столбцы — это атрибуты, а не домены.
Разделите понятия отношения и таблицы, если уж пишите о реляционной теории, а не о SQL
> Для однозначной идентификации кортежа существует первичный ключ
В реляционной теории отсутствует понятие первичного ключа, есть просто понятие ключа как набора атрибутов, обладающего свойствами уникальности и неприводимости.
Домен — это множество значений, которые может принимать заданный атрибут. Если уж применять к таблице, то столбцы — это атрибуты, а не домены.
Разделите понятия отношения и таблицы, если уж пишите о реляционной теории, а не о SQL
> Для однозначной идентификации кортежа существует первичный ключ
В реляционной теории отсутствует понятие первичного ключа, есть просто понятие ключа как набора атрибутов, обладающего свойствами уникальности и неприводимости.
Хорошее описание, жаль в голове сразу встает образ ржавой пилы денормализации, которую мало кому удается избежать при росте проекта.
Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90.
SELLER
ОАО ”Ведро”
а почему сюда не вошел: OOO “Дарт”?
SELLER
ОАО ”Ведро”
а почему сюда не вошел: OOO “Дарт”?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Основы реляционной алгебры