Pull to refresh

Comments 42

Эх… где вы были год назад, когда я только начинал изучать реляционную алгебру? Ваши примеры и доходчивое описание мне бы тогда здорово помогло…
Вам бы еще написать на «человеческом» языке статью по построению «хорошей» схемы базы данных, чтобы те, только начинают изучать релационку в ВУЗах, смогли ее без проблем потом сдать (МГТУ привет). Тогда цены вам бы не было)
Год назад я слушал лекции Григорьева Ю. А., но там в основном были только формулы и такие фразы: «замыкание множества функциональных зависимостей», «свойства соединения без потерь», «первичный и непервичный атрибут»… жуть. Поэтому было сперва сложновато вникнуть во все эти тонкости без наглядных примеров
Не знаю, как было год назад, но в этом году Григорьев давал подробный пример для каждой из этих фраз)
А хорошую схему БД мы строили медленно и обстоятельно целую пару
>Множество упорядоченных кортежей называется отношением.

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

Во-вторых, множество упорядоченных кортежей — это 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)

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

зы: знаете, мне определенно нравится ход ваших рассуждений. «для простоты рассмотрим баланс в кассе нашей организации. вот приход, вот расход. не трудно заметить, что ни какой вашей зарплаты здесь нет — присутствует исключительно синтаксический сахар.» :)
ох… неужели вас не смущает такое обилие двоек?)
(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 синтаксис.
Да, пожалуйста, с sql было бы намного нагляднее.
Неплохо бы уточнить, что из 8 операций только 5 являются базисными — остальные можно выразить через них.
уточнено в начале, но судя по вашему комментарию недостаточно ясно,
спасибо, немного позже дополню этот кусок
Исправьте, пожалуйста, номера ID в некоторых таблицах, видимо опечатки, меня сначала ввели в ступор, там где 235 != 135, к примеру.
спасибо, поправил опечатку
Простите меня за глупый вопрос. Но наведите пожалуйста пример из реальной жизни, где может понадобиться умножение? (Предвидя всяческий троллинг, оговорюсь, что в контексте данной статьи :) )
По-моему здесь должна быть только первая строка:

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

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

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

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

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

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
> Для однозначной идентификации кортежа существует первичный ключ
В реляционной теории отсутствует понятие первичного ключа, есть просто понятие ключа как набора атрибутов, обладающего свойствами уникальности и неприводимости.
Хорошее описание, жаль в голове сразу встает образ ржавой пилы денормализации, которую мало кому удается избежать при росте проекта.
Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90.

SELLER
ОАО ”Ведро”

а почему сюда не вошел: OOO “Дарт”?
OOO “Дарт” продает товар 123 с ценой больше 90,
а из результата произведения OOO “Дарт” не попал, потому что PRODUCTS.ID и SELLERS.ID не совпадают, как было указано в условии
Only those users with full accounts are able to leave comments. Log in, please.