Лекция 3. Основы теории множеств
Средства работы с реляционными БД базируются на теории отношений, которая, в свою очередь, основана на теории множеств.
Таблицы, из которых состоит любая реляционная БД, представляют собой некоторые отношения, а отношения являются множествами. Под множеством принято понимать некоторую совокупность объектов, хорошо различимых нашей мыслью или интуицией. При этом не делается никаких предположений ни о природе этих объектов, ни о способе их включения в данную совокупность.
Отдельные объекты, составляющие то или иное множество, называют элементами данного множества.
Вопрос «Почему мы рассматриваем ту или иную совокупность элементов как множество?» не требует ответа, поскольку в общее определение множества не входят никакие дополнительные условия на включение отдельных элементов в множество. Если нам хочется, например, рассмотреть множество, состоящее из трех элементов: «солнце, море, апельсин», то никто не сможет запретить нам это сделать.
Множество – собрание объектов, которое рассматривается как один объект.
Множества могут быть конечными и бесконечными. Конечные множества содержат элементы, которые можно сосчитать или перечислить. Это означает, что имеется возможность сопоставить каждому элементу множества некоторое натуральное число. Количество элементов конечного множества называется мощностью и обозначается |X| = n, если множество X содержит n элементов.
В БД мы имеем дело с конечными множествами, хотя иногда очень большими.
Во множестве обычно не бывает двух или более одинаковых элементов, а порядок расположения элементов во множестве не имеет никакого значения. Множество с повторяющимися элементами называется мультимножеством. Множество может и не содержать элементов, тогда его называют пустым и обозначают как Ǿ. В явном виде пустое множество обозначается:  .
Множества будем обозначать заглавными буквами латинского алфавита; объекты, которые образуют множества, будем называть элементами множества и обозначать малыми буквами латинского алфавита:
 
иначе
Простейший способ для определения конкретного множества состоит в том, чтобы явно указать все элементы, принадлежащие этому множеству. Это экстенсиональный способ определения множества. При достаточно больших множествах этот способ не подходит. Тогда используют интенсиональный (неявный) способ определения множеств. Он основан на использовании некоторой функции (алгоритма), которая определяет для каждого элемента, принадлежит ли он данному множеству или нет. Эта функция двузначна и принимает значения ИСТИНА или ЛОЖЬ. Такая двузначная функция в математической логике называется предикатом.
Для произвольных множеств X и Y можно определить два типа отношений – отношение равенства и отношение включения.
Два множества считаются равными, если они состоят из одних и тех же элементов. Принято обозначение X = Y, если X и Y равны, и X ¹ Y — иначе.
Легко видеть, что для любых множеств X, Y, Z справедливы соотношения:
(презентация)
Следующим важным понятием, которое служит прототипом многих более конкретных терминов при моделировании сложных систем, является понятие подмножества. Если есть некоторая совокупность, рассматриваемая как множество, то любая ее часть и будет являться подмножеством.
Любую совокупность элементов, образующих множество, можно обозначить графически в виде круга. В этом случае окружность имеет содержательный смысл или, выражаясь более точным языком, семантику границы данного множества. На этом рисунке большему множеству Y соответствует внешний круг, а меньшему множеству (подмножеству) X — внутренний. Графическое представление отношений множеств в виде кругов называется диаграммой Венна.
Если в рамках некоторого рассуждения рассматриваются подмножества некоторого множества, то оно называется универсальным, или универсумом и обозначается E .
Таким образом, множество может быть задано различными способами: перечислением элементов в скобках { } (для конечных множеств) или указанием их свойств, однозначно определяющих принадлежность элементов данному множеству, при этом используется запись
Выражение в скобках читается: множество всех элементов x, которые обладают свойством P(x).
Введем понятие кортежа, используемое в БД. Под кортежем понимается просто набор или список элементов, важно только, чтобы они были упорядочены. Другими словами, если рассматривать первый элемент кортежа, то он всегда будет первым в списке элементов, второй элемент кортежа будет вторым элементом в списке и т. д.
Кортеж из двух элементов удобно обозначать как <a1, a2>, из трех элементов — и т. д. При этом отдельные элементы могут принадлежать как одному и тому же множеству, так и различным множествам. Важно иметь в виду, что порядок выбора элементов для построения кортежей строго фиксирован для конкретной задачи. Речь идет о том, что первый элемент всегда выбирается из первого множества, второй — из второго, и так далее. Кортеж в этом случае будет характеризовать способ или семантику выбора отдельных элементов из одного или нескольких множеств. Таким образом, кортеж можно еще назвать упорядоченным списком.
Операции над множествами (презентация)
Понятие универсума
Обозначим через Е множество всех элементов, которое называется универсумом. Предполагается, что любой элемент множества, с которым мы имеем дело, принадлежит универсуму. Тогда любое множество Х является подмножеством универсума:
Разность Е-Х называют дополнением множества Х до универсума (или просто дополнением) и обозначают как
В математической логике, для формального описания какой-либо предметной области используются механизм управляющих объектов-предикатов. Формально предикат представляет собой отображение из множества данных предметной области на множество логических значений «истина» и «ложь»:
Понятие «предикат» обобщает понятие «высказывание». Неформально говоря, предикат — это высказывание, в которое можно подставлять аргументы. Если аргумент один — то предикат выражает свойство аргумента, если больше — то отношение между аргументами.
П   ример предикатов. Возьмем высказывания: «Доцент — человек», «Студент — человек». Оба эти высказывания выражают свойство «быть человеком». Таким образом, мы можем рассматривать предикат «Быть человеком» , и говорить, что он выполняется
( ) для d = «Доцент» или «Студент», или не выполняется ( ) для d = «Компьютер».
В озьмем высказывание: «Расстояние от Иркутска до Москвы 5 тысяч километров». Вместо него мы можем записать предикат «Расстояние» ,означающий, что первый и второй аргумент этого предиката находятся на расстоянии, равном третьему аргументу. Для аргументов = «Иркутск», = «Москва» и = «5 тысяч километров» данный предикат выполняется.
Понятие отношения
О  тношение есть множество, элементами которого являются кортежи, которые, в свою очередь, состоят из элементов других множеств. При этом между любым кортежем отношения и самим отношением имеет место отношение принадлежности , но не включения . Кортеж представляет собой не множество, а упорядоченную последовательность элементов.
Пример:
Отношение ОТЦЫ_И_ДЕТИ(МУЖЧИНЫ,ЛЮДИ).
Результат: множество кортежей вида <x,y>, в которых через х и y обозначены люди, такие, что х является отцом для у.
В качестве имен людей следует выбрать их уникальные идентификаторы. Фамилия, имя и отчество для этой цели вряд ли подойдут. Возможно, окажется достаточным использовать дополнительные паспортные данные, отпечатки пальцев или снимок радужной оболочки глаза.
Очевидно, что множества отцов и женщин включаются в множество людей, но ни одна женщина не принадлежит множеству отцов. Поэтому в рассматриваемом отношении отцы_и_дети не будет ни одного кортежа, в котором на первом месте стояло бы имя женщины. Кроме того, ни один человек не может быть отцом для самого себя. Поэтому в отношении не будет ни одного кортежа, в котором первый и второй элемент совпадают. Эти и, возможно, другие особенности, характеризующие отношение, называются ограничениями его целостности.
Задавая отношение ОТЦЫ_И_ДЕТИ, мы можем, по крайней мере, теоретически, поступить следующим образом. Сначала возьмем множество всевозможных кортежей <x,y>, в которых x МУЖЧИНЫ и y ЛЮДИ, а затем выберем из этого множества только те кортежи, в которых x является отцом для y. Полученное множество и будет представлять собой интересующее нас отношение ОТЦЫ_И_ДЕТИ.
Декартово произведение (презентация).
Например, пусть товары на складе имеют характеристики, выбираемые из множеств НАИМЕНОВАНИЕ, КОЛИЧЕСТВО, ЦЕНА и ПОСТАВЩИК. Тогда таблица, содержащая сведения обо всех товарах на складе, представляет отношение между указанными характеристиками, а все ее строки — кортежи, принадлежащие некоторому подмножеству декартового произведения:
НАИМЕНОВАНИЕ х КОЛИЧЕСТВО х ЦЕНА х ПОСТАВЩИК.
Способы представления отношений
К представлениям отношений мы приходим, когда требуется наглядность или определенное удобство для хранения данных и манипулирования ими. Рассмотрим несколько вариантов.
В вырожденном случае унарных отношений мы имеем дело с обычными множествами, которые естественным образом представляются списком своих элементов или же одностолбцовой таблицей, в каждой строке которой указан некоторый элемент множества. При этом не следует забывать, что множество не предполагает никакого порядка элементов. Поэтому два списка, содержащие одни и те же элементы, но упорядоченные различным образом, являются эквивалентными с точки зрения теории отношений. Иначе говоря, они представляют одно и то же отношение.
Бинарные (двухместные) отношения можно представить в виде графов, матрицы, а также двухстолбцовых таблиц. В графовом представлении каждой вершине соответствует некоторый элемент одного из двух множеств. От одной вершины к другой проводится стрелка, если первый элемент находится в рассматриваемом отношении со вторым.
При табличном представлении каждому кортежу отношения взаимооднозначно соответствует строка (запись) в таблице. Но не всякая таблица представляет некоторое отношение. Таблица — это прямоугольная сетка, в ячейках которой может находиться все, что угодно. При этом различные строки этой таблицы могут содержать в соответствующих столбцах одинаковые данные. Другими словами, таблицы могут содержать идентичные строки. В этом случае совокупность всех строк таблицы не является множеством, а значит, не представляет собой отношения. Напомню, что множество — это совокупность различных элементов.
Таким образом, любое отношение (в определенном ранее смысле) можно представить в виде таблицы, но обратное утверждение, вообще говоря, не верно — не всякая таблица представляет какое-нибудь отношение.
При представлении отношения явным образом в виде таблицы, ее нельзя рассматривать просто как вместилище данных, в которое можно добавлять новые записи или удалять старые. Добавление, удаление и изменение данных в такой таблице приводит либо к другому отношению, либо к никакому отношению (если в таблице окажутся одинаковые записи).
Табличное представление отношений — это чрезвычайно плодотворный технологический прием, обеспечивший создание и широкое практическое применение баз данных. То обстоятельство, что отношения — просто множества, позволило изучать проблемы реляционных баз данных на теоретическом уровне, в мире математики (алгебра множеств и исчисление предикатов), а не только в мире технологии.
О тношение имеет имя R. Например, сведения о товарах, хранящихся на складе, образуют некоторое отношение, которому можно дать имя СКЛАД.
Множества , для которых определено отношение R, имеют различные имена, называемые атрибутами отношения. Совокупность всевозможных значений любого множества называется доменом этого атрибута. Заметим еще раз, что в отношении не может быть двух и более одинаковых атрибутов, хотя их домены могут быть и одинаковыми (в смысле равенства множеств). При табличном представлении отношения каждому атрибуту соответствует заголовок столбца, а домену — множество значений в этом столбце.
Порядок перечисления атрибутов в структуре отношения не имеет значения. Иначе говоря, перестановка атрибутов местами оставляет само отношение прежним, хотя вид таблицы, представляющей это отношение, меняется. Например, отношения СКЛАД (НАИМЕНОВАНИЕ, КОЛИЧЕСТВО, ЦЕНА, ПОСТАВЩИК) и СКЛАД (ПОСТАВЩИК, НАИМЕНОВАНИЕ, КОЛИЧЕСТВО, ЦЕНА) считаются эквивалентными.
Элементами отношения являются кортежи — последовательности значений атрибутов отношения. В отношении не может быть двух и более одинаковых кортежей, а порядок расположения кортежей не имеет значения. При этом каждому кортежу соответствует строка таблицы. Строки таблицы мы будем называть записями.
Операции над отношениями
Отношение — это множество (а именно множество кортежей или, другими словами, записей), то к ним применимы все теоретико-множественные операции, рассмотренные ранее: объединение, пересечение, вычитание и декартово произведение.
Однако в реляционной теории особую роль играют специальные операции, лежащие в основе языка SQL:
селекция;
проекция;
естественное соединение.
Эти операции выражаются некоторым образом через обычные операции над множествами. Рассмотрим их более подробно.
|
