«Отношение. Основное свойство отношения» - страница №1/1

Тема урока: «Отношение. Основное свойство отношения».

Цели:

1. 
   Создать условия для осознания и осмысления нового математического понятия «отношение», основное свойство отношения; показать правила записи и прочтения отношений;
2. 
   Развивать познавательный интерес, умение сравнивать, обобщать; развивать внимание, воображение учащихся;
3. 
   Воспитывать социальную компетентность

Ход урока.

1. Организационный момент.

Чтобы спорилось нужное дело,

Чтобы в жизни не знать неудач,

В математики мир отправимся смело,

В мир примеров и разных задач.

А девизом нашего урока буду такие слова:

Думать - коллективно!

Решать - оперативно!

Отвечать - доказательно!

Бороться - старательно!

И открытия нас ждут обязательно!

2. Мотивация урока.

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

Например, скорость – это отношение пройденного пути к времени.

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

Отношение длины отрезка на карте к длине соответствующего отрезка на местности называется масштабом.

И сегодня на уроке мы поговорим об отношении двух чисел.

3. Актуализация опорных знаний.

Устный счет:

4. Изучение нового материала.

Для того, чтобы объяснить смысл отношения дать условие задачи «В классе 25 учеников. Из них 15 мальчиков и 10 девочек» и вместе с учениками ответить на следующие вопросы:

• 
  Какую часть класса составляют девочки?
• 
  Какую часть класса составляют мальчики?
• 
  Какую часть количество девочек составляет от числа мальчиков?
• 
  Во сколько раз мальчиков больше девочек?

Открыли тетради и посчитали, сколько листов исписано, а сколько чистых

Представьте в виде частного отношение пустых листов к чистым.

Какие получились у вас дроби?

Частное двух чисел а и в, отличных от нуля, называют отношением этих чисел или отношением числа а к числу в. Отношение показывает, во сколько раз первое число больше второго или какую часть первое число составляет от второго.

Основное свойство отношения: Отношение не изменится, если его члены умножить или разделить на одно и то же число, отличное от нуля.

Решить №597, 598.

5.Закрепление нового материала.

Решить № 604, 599, 601.

6. Историческая справка.

В древности и почти на всём протяжении средних веков под числом понималось только натуральное число, собрание единиц, полученное в результате счета. Отношение же будучи результатом деления одного числа на другое, не считалось числом.

Но уже в трудах среднеазиатских математиков Омара Хайяма (1048- 1131), Насирэддина ат – Туси (101 – 1274) выск5азана мысль о том, что отношение есть число и что над отношениями можно производить все действия, которые производятся над целыми числами.

Явно новое определение числа было дано впервые в 17 веке гениальным английским ученым Исааком Ньютоном. В своей « Всеобщей арифметике он писал: « Под числом мы понимаем не столько множество единиц, сколько отвлеченное отношение какой – нибудь величины к другой величине того же рода, принятой нами за единицу»

7. Итоги урока. Д/з.

Что называют отношением двух чисел?

Что показывает отношение двух чисел?

Как узнать какую часть число а составляет от числа b? Приведи пример.

Прочти вслух разными способами 35: 27.

Лекция 21. Свойства отношений

1. Свойство рефлексивености

2. Свойство симметричности

3. Свойство транзитивности

Мы установили, что бинарное отношение на множестве X пред­ставляет собой множество упорядоченных пар элементов, принад­лежащих декартову произведению X х Х. Это математическая сущ­ность всякого отношения. Но, как и любые другие понятия, отноше­ния обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые.

Рассмотрим на множестве отрезков, представ­ленных на рис. 98, отношения перпендикулярно­сти, равенства и «длиннее». Построим графы этих отношений (рис. 99) и будем их сравнивать. Ви­дим, что граф отношения равенства отличается от двух других наличием петель в каждой его вершине. Эти петли - результат того, что отно­шение равенства отрезков обладает свойством: любой отрезок равен самому себе. Говорят, что отношение равенства обладает свойством рефлек­сивности или просто, что оно рефлексивно.

Определение. Отношение R на множестве X называется рефлексив­ным, если о каждом элементе множества X можно сказать, что он находится в отношении R с самим собой.

R рефлексивно на Х ↔ х R х для любого х € X.

опр.

Если отношение R рефлексивно на множестве X, то в каждой вер­шине графа данного отношения имеется петля. Справедливо и обрат­ное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности.

Примеры рефлексивных отношений:

Отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе);

Отношение подобия треугольников (каждый треугольник подо­бен самому себе).

Существуют отношения, которые свойством рефлексивности не обладают. Таким, например, является отношение перпендикулярности на множестве отрезков: нет ни одного отрезка, о котором можно ска­зать, что он перпендикулярен самому себе. Поэтому на графе отноше­ния перпендикулярности (рис. 99) нет ни одной петли. Не обладает свойством рефлексивности и отношение «длиннее» для отрезков.

Обратим теперь внимание на графы отношений перпендикулярно­сти и равенства отрезков. Они «похожи» тем, что если есть одна стрелка, соединяющая пару элементов, то обязательно есть и другая, соединяющая те же элементы, но идущая в противоположном направ­лении. Эта особенность графа отражает те свойства, которыми обла­дают отношения параллельности и равенства отрезков:

Если один отрезок перпендикулярен другому отрезку, то этот «другой» перпендикулярен первому;

Если один отрезок равен другому отрезку, то этот «другой» равен первому.

Про отношения перпендикулярности и равенства отрезков гово­рят, что они обладают свойством симметричности или просто сим­метричны.

Определение. Отношение R на множестве X называется симмет­ричным, если выполняется условие: из того, что элемент х находит­ся в отношении R с элементом у, следует, что и элементу находит­ся в отношении R с элементом х.

Используя символы, это отношение можно записать в таком виде:

R симметрично на Х ↔ (х R y →yRx).

опр.

Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к x . Справедливо и обратноеутверждение. Граф, содержащий вместе с каждой стрелкой, идущей от x к у, и стрелку, идущую от у к x , является графом симметричного отношения.

В дополнение к рассмотренным двум примерам симметричных от­ношений присоединим еще такие:

Отношениепараллельности на множестве прямых (если прямая x параллельна прямой у, то и прямая у параллельна прямой х)

Отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).

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

Определение. Отношение R на множестве X называется анти­симметричным, если для различных элементов х и у из множества X выполнено условие: из того, что х находится в отношении R с элементом у, следует, что элемент у в отношении R с элементом х не находится.

R симметрично на Х ↔ (х R y ^ x≠y →yRx).

опр.

Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливо и обратное утверждение: граф, вершины которого со­единены только одной стрелкой, есть граф антисимметричного отношения.

Кроме отношения «длиннее» на множестве отрезков свойством ан­тисимметричности, например, обладают:

Отношение «больше» для чисел (если х больше у, то у не может
быть больше х);

Отношение «больше на 2» для чисел (если х боль­ше у на 2, то у не может быть больше на 2 числа х),

Существуют отношения, не обладающие ни свой­ством симметричности, ни свойством антисиммет­ричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф отношения «быть сестрой» будет таким, как на рисунке 100. Он показывает, что данное отношение не обладает ни свой­ством симметричности, ни свойством антисимметричности.

Обратим внимание еще раз на одну особенность графа отноше­ния «длиннее» (рис. 99). На нем можно заметить: если стрелки про­ведены от е к а и от а к с, то есть стрелка от е к с ; если стрелки приведены от е к b и от b к с, то есть стрелка и от е к с и т.д. Эта особенность графа отражает важное свойство отношения «длиннее»: если первый отрезок длиннее второго, а второй - длиннее третьего, то первый - длиннее третьего. Говорят, что это отношение обладает свойством транзитивности или просто транзитивно.

Определение. Отношение R на множестве X называется транзи­тивным, если выполняется условие; из того, что элемент х нахо­дится в отношении R с элементом у и элемент у находится в от­ношении R с элементом z, следует, что элемент х находится в от­ношении К с элементом z .

Используя символы, это определение можно записать в таком виде:

R транзитивно на X ↔ (х R y ^ yRz → xRz).

опр.

Граф транзитивного отношения с каждой парой стрелок, идущих от x к у и у к z , содержит стрелку, идущую от х к z. Справедливо и обратное утверждение.

Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку z, то отрезок х равен отрезку z, Это свойство отражено и на графе отношения равенства (рис. 99)

Существуют отношения, которые свойством транзитивности не об­ладают. Таким отношением является, например, отношение перпенди­кулярности: если отрезок а перпендикулярен отрезку d , а отрезок d перпендикулярен отрезку b, то отрезки а и b не перпендикулярны!

Рассмотрим еще одно свойство отношений, которое называют свой­ством связанности, а отношение, обладающее им, называют связанным.

Определение. Отношение R на множестве X называется связан­ным, если для любых элементов х и у из множества X выполняется условие: из того, что х и у различны, следует, что либо х находит­ся в отношении R с элементом у, либо элемент у находится в от­ношении R с элементом х.

Используя символы, это определение можно записать в таком виде:

R связано на множестве X ↔ (х ≠ у => хRу v уRх).

опр.

Например, свойством связанности обладают отношения «больше» длянатуральных чисел: для любых различных чисел х и у можно ут­верждать, что либо х > у, либо у > х.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

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

Выделенные свойства позволяют анализировать различные отно­шения с общих позиций - наличия (или отсутствия) у них тех или иных свойств.

Так, если суммировать все сказанное об отношении равенства, за­данном на множестве отрезков (рис. 99), то получается, что оно реф­лексивно, симметрично и транзитивно. Отношение «длиннее» на том же множестве отрезков антисимметрично и транзитивно, а отношение перпендикулярности - симметрично, но оно не обладает свойствами рефлексивности и транзитивности. Все эти отношения на заданном множестве отрезков связанными не являются.

Задача 1. Сформулировать свойства отноше­ния R, заданного при помощи графа (рис. 101).

Решение. Отношение R -антисимметрично, так как вершины графа соединяются только одной стрелкой.

Отношение R - транзитивно, так как с парой стрелок, идущих от b к а и от а к с, на графе есть стрелка, идущая от b к с.

Отношение R - связанно, так как любые две вер­шины соединены стрелкой.

Отношение R свойством рефлексивности не обла­дает, так как на графе есть вершины, в которых петли нет.

Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.

Решение. «Больше в 2 раза» - это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число y не больше числа x 2 раза.

Данное отношение не обладает свойством рефлексивности, пото­му что ни про одно число нельзя сказать, что оно больше самого себя в 2 раза.

Заданное отношение не транзитивно, так как из того, что число x больше числа у на 2, а число у больше числа z на 2, следует, что число х не может быть больше числа z на 2.

Это отношение на множестве натуральных чисел свойством связан­ности не обладает, так как существуют пары таких чисел х и у, что ни число х не больше числа у в два раза, ни число у не больше х в 2 раза. Например, это числа 7 и 3, 5 и 8 и др.

История

Реляционная модель данных (РМД) относится к теоретико-множест­венным моделям данных. Появление теоретико-множественных моделей в системах баз данных (БД) было предопределено настоятельной потребностью пользователей в переходе от работы с элементами данных, как это делается в теоретико-графовых моделях , к работе с некоторыми макрообъектами.

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

Теоретической основной РМД стала теория отношений. Основу теории отношений заложили двое ученых – американец Чарльз Содерс Пирс (1839-1914) и немец Эрнст Шредер (1841-1902). В руководствах по теории отношений было показано, что множество отношений замкнуто относительно некоторых специальных операций, т.е. образует вместе с этими операциями абстрактную алгебру. Американский математик Э.Ф.Кодд заложил принципы РМД. В конце 1968 года он впервые осознал, что математические дисциплины можно использовать, чтобы привнести в область управления базами данных строгие принципы и точность. Именно таких принципов недоставало этой области в то время. Кодд впервые сформулировал понятия и ограничения реляционной модели, определив набор из
семи основных и одной дополнительной операций.

Предложения Кодда для систем баз данных оказались чрезвычайно эффективными и оказали весьма существенное влияние на все аспекты технологии построения баз данных.

Основные понятия и определения

Реляционная модель данных (РМД) – это способ рассмотрения данных, при котором данные воспринимаются пользователем как таблицы и в распоряжении пользователя имеются некоторые операторы, которые генерируют новые таблицы из старых.

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

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

Основной структурой данных в РМД является отношение (от англ. relation – отношение). Отсюда возникло название модели, основанной на отношениях: такую модель стали называть реляционной моделью данных.

Введем некоторые определения.

N -арным отношением R называют подмножество декартова произведения множеств .

Исходные множества называют доменами.

где - полное декартово произведение множеств.

Полное декартово произведение множеств – набор всевозможных сочетаний из n элементов, где каждый элемент берется из своего домена.

Например, пусть имеются три домена (три некоторых множества):

Содержит наименования складов торговой фирмы;

Содержит наименования групп товаров;

Содержит наименования товаров, которыми торгует фирма.

Предположим, что содержимое доменов следующее:

= {Склад №1, Склад №2};

= {Стройматериалы, Бытовая химия};

= {Кирпич, Шифер, Мыло, Порошок}.

Тогда полное декартово произведение содержит набор из 16 троек (2x2x4), где первый элемент – один из складов фирмы, второй – название группы товаров, третий – наименование товара:

Таким образом, получаем набор всевозможных сочетаний значений доменов в одном n -арном отношении.

Учитывая, что отношение R только подмножество полного декартова произведения доменов, то в общем случае оно всегда меньше, чем полное декартово произведение множеств. Так отношение R может содержать только 5 строк.

R = {<Склад №1, Стройматериалы, Кирпич>,
<Склад №1, Стройматериалы, Шифер>,
<Склад №2, Стройматериалы, Шифер>,
<Склад №2, Бытовая химия, Мыло>,
<Склад №2, Бытовая химия, Порошок>}.

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

Наборы из n значений называют n -ками.

Представленная таблица (отношение в виде таблицы) обладает рядом свойств:

1. Таблица имеет столбцы, соответствующие доменам.

2. Каждый столбец имеет уникальное имя.

3. В таблице нет двух одинаковых строк.

4. Порядок строк и столбцов в таблице произвольный.

Домен – множество всех допустимых значений какого-либо свойства или признака объекта (рис.1.1). При этом значения признака соответствуют определенному типу данных. Примерами элементарных доменов являются целые числа, дробные числа, строки и т.д. Одному домену может соответствовать несколько атрибутов, а одному атрибуту – несколько доменов. Например, домен «Текстовая строка» определяет множество допустимых значений для таких атрибутов как «Наименование склада», «Наименование товара», «Единица измерения» и пр. В то же время атрибут «Наименование склада» может быть определен доменом «Наименование объектов», как текстовой строки размером 50 знаков.

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

Кортеж – это конкретный набор значений доменов (n -ка), составляющих строку отношения.

Степень отношения – это количество атрибутов в отношении.

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

Следует отметить, что в отношении не может быть одинаковых кортежей, это следует из математической модели: отношение – подмножество декартова произведения множеств, а в декартовом произведении множеств все n -ки различны.

Любое отношение является динамической моделью некоторого реального объекта внешнего мира. Для любой динамической модели необходимо знать ее состояние в какой-либо момент времени, необходимо также знать структуру отношения.

Рис.1.1. Пример отношения «Остатки товаров на складах»

Поэтому вводится понятие экземпляра отношения , которое отражает состояние данного объекта в текущий момент времени, и понятие схемы отношения , которое определяет структуру отношения.

Схемой отношения R называют перечень имен атрибутов данного отношения с указанием домена, к которому они относятся:

Если атрибуты принимают значения из одного и того же домена, то они называются q-сравнимыми, где q - множество допустимых операций сравнения, заданных для данного домена. Например, если домен содержит числовые данные, то для него допустимы все операции сравнения, тогда

q = {=, <>, >=, <=, <, >}.

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

- схема отношения R1

- схема отношения R2 после упорядочивания имен атрибутов.

Тогда,

Фундаментальные свойства отношений

Остановимся теперь на некоторых важных свойствах отношений , которые следуют из приведенных ранее определений.

Остановимся теперь на некоторых важных свойствах отношений, которые следуют из приведенных ранее определений:

Отсутствие кортежей-дубликатов

То свойство, что отношения не содержат кортежей-дубликатов, следует из определения отношения как множества кортежей. В классической теории множеств по определению каждое множество состоит из различных элементов.

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

Потенциальные ключи

Пусть R – отношение с атрибутами A1, A2, ..., An. Говорят, что множество атрибутов K=(Ai, Aj, ..., Ak) отношения R является возможным (потенциальным) ключом R тогда и только тогда, когда удовлетворяются два независимых от времени условия:

1. Уникальность: в произвольный заданный момент времени никакие два различных кортежа R не имеют одного и того же значения для Ai, Aj, ..., Ak.

2. Минимальность: ни один из атрибутов Ai, Aj, ..., Ak не может быть исключен из K без нарушения уникальности. Т.е. в набор атрибутов первичного ключа не должны входить такие атрибуты, которые можно отбросить без ущерба для основного свойства - однозначно определять кортеж.

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

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

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

Отсутствие упорядоченности кортежей

Свойство отсутствия упорядоченности кортежей отношения также является следствием определения отношения-экземпляра как множества кортежей. Отсутствие требования к поддержанию порядка на множестве кортежей отношения дает дополнительную гибкость СУБД при хранении баз данных во внешней памяти и при выполнении запросов к базе данных. Это не противоречит тому, что при формулировании запроса к БД, например, на языке SQL можно потребовать сортировки результирующей таблицы в соответствии со значениями некоторых столбцов. Такой результат, вообще говоря, не отношение, а некоторый упорядоченный список кортежей.

Отсутствие упорядоченности атрибутов

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

Атомарность значений атрибутов

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

Можно сказать, что здесь мы имеем бинарное отношение, значениями атрибута ОТДЕЛЫ которого являются отношения. Заметим, что исходное отношение СОТРУДНИКИ является нормализованным вариантом отношения ОТДЕЛЫ:

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

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

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

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

Целостность сущности и ссылок

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

Второе требование называется требованием целостности по ссылкам и является несколько более сложным. Очевидно, что при соблюдении нормализованности отношений сложные сущности реального мира представляются в реляционной БД в виде нескольких кортежей нескольких отношений. Например, представим, что нам требуется представить в реляционной базе данных сущность ОТДЕЛ с атрибутами ОТД_НОМЕР (номер отдела), ОТД_КОЛ (количество сотрудников) и ОТД_СОТР (набор сотрудников отдела). Для каждого сотрудника нужно хранить СОТР_НОМЕР (номер сотрудника), СОТР_ИМЯ (имя сотрудника) и СОТР_ЗАРП (заработная плата сотрудника). Как мы вскоре увидим, при правильном проектировании соответствующей БД в ней появятся два отношения: ОТДЕЛЫ (ОТД_НОМЕР, ОТД_КОЛ) (первичный ключ - ОТД_НОМЕР) и СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРП, СОТР_ОТД_НОМ) (первичный ключ - СОТР_НОМЕР).

Как видно, атрибут СОТР_ОТД_НОМ появляется в отношении СОТРУДНИКИ не потому, что номер отдела является собственным свойством сотрудника, а лишь для того, чтобы иметь возможность восстановить при необходимости полную сущность ОТДЕЛ. Значение атрибута СОТР_ОТД_НОМ в любом кортеже отношения СОТРУДНИКИ должно соответствовать значению атрибута ОТД_НОМ в некотором кортеже отношения ОТДЕЛЫ. Атрибут такого рода называется внешним ключом , поскольку его значения однозначно характеризуют сущности, представленные кортежами некоторого другого отношения (т.е. задают значения их первичного ключа). Говорят, что отношение, в котором определен внешний ключ, ссылается на соответствующее отношение, в котором такой же атрибут является первичным ключом.

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

Основные свойства реляционной БД.

1. Каждая таблица состоит из однотипных строк и имеет уникальное имя.

2. Строки имеют фиксированное число полей (столбцов) и значений (множественные поля и повторяющиеся группы недопустимы). Иначе говоря, в каждой позиции таблицы на пересечении строки и столбца всегда имеется в точности одно значение или ничего.

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

4. Столбцам таблицы однозначно присваиваются имена, и в каждом из них размещаются однородные значения данных (даты, фамилии, целые числа или денежные суммы).

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

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

Cтремление к минимизации числа таблиц для хранения данных может привести к возникновению различных проблем при их обновлении и будут даны рекомендации по разбиению некоторых больших таблиц на несколько маленьких.

Но как сформировать требуемый ответ, если нужные для него данные хранятся в разных таблицах?

Предложив реляционную модель данных, Э.Ф.Кодд создал и инструмент для удобной работы с отношениями – реляционную алгебру. Каждая операция этой алгебры использует одну или несколько таблиц (отношений) в качестве ее операндов и продуцирует в результате новую таблицу, т.е. позволяет "разрезать" или "склеивать" таблицы (рис. 3.3).

Произведение отношений

	A X A Y B X B Y C X C Y

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

Рис. Некоторые операции реляционной алгебры

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

С помощью единственного запроса на любом из этих языков можно соединить несколько таблиц во временную таблицу и вырезать из нее требуемые строки и столбцы (селекция и проекция).

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

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

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

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

Контрольные вопросы.

1. Перечислите свойства отношений.

2. Дайте определение потенциального (возможного) ключа отношения.

3. Перечислите свойства потенциального ключа, дайте определение первичного ключа.

4. Перечислите три части реляционной модели.

Отношение, заданное на множестве, может обладать рядом свойств, а именно:

2. Рефлексивность

Определение. Отношение R намножестве Х называется рефлексивным, если каждый элемент х множества Х находится в отношении R с самим собой.

Используя символы, это отношение можно записать в таком виде:

R рефлексивно на Х Û("х Î Х ) х R х

Пример. Отношение равенства на множестве отрезков рефлексивно, т.к. каждый отрезок равен себе самому.

Граф рефлексивного отношения во всех вершинах имеет петли.

2. Антирефлексивность

Определение. Отношение R намножестве Х называется антирефлексивным, если ни один элемент х множества Х не находится в отношении R с самим собой.

R антирефлексивно на Х Û("х Î Х )

Пример. Отношение «прямая х перпендикулярна прямой у » на множестве прямых плоскости антирефлексивно, т.к. ни одна прямая плоскости не перпендикулярна самой себе.

Граф антирефлексивного отношения не содержит ни одной петли.

Заметим, что существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Например, рассмотрим отношение «точка х симметрична точке у » на множестве точек плоскости.

l

Точка х симметрична точке х – истинно; точка у симметрична точке у – ложно, следовательно, мы не можем утверждать, что все точки плоскости симметричны сами себе, также мы не можем и утверждать, что ни одна точка плоскости не симметрична сама себе.

3. Симметричность

Определение . Отношение R намножестве Х называется симметричным, если из того, что элемент х находится в отношении R с элементом у , следует, что и элемент у находится в отношении R с элементом х .

R симметричнона Х Û("х , у Î Х ) х R у Þ у R х

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

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

4. Асимметричность

Определение . Отношение R намножестве Х называется асимметричным, если ни для каких элементов х , у из множества Х не может случиться, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом х .

R асимметричнона Х Û("х , у Î Х ) х R у Þ

Пример. Отношение «х < у » асимметрично, т.к. ни для какой пары элементов х , у нельзя сказать, что одновременно х < у и у < х .

Граф асимметричного отношения не имеет петель и если две вершины графа соединены стрелкой, то эта стрелка только одна.

5. Антисимметричность

Определение . Отношение R намножестве Х называется антисимметричным, если из того что х находится в отношении с у , а у находится в отношении с х следует, что х = у.

R антисимметричнона Х Û("х , у Î Х ) х R у Ù у R х Þ х = у

Пример. Отношение «х £ у » антисимметрично, т.к. условия х £ у и у £ х одновременно выполняются только тогда, когда х = у.

Граф антисимметричного отношения имеет петли и если две вершины графа соединены стрелкой, то эта стрелка только одна.

6. Транзитивность

Определение . Отношение R намножестве Х называется транзитивным, если для любых элементов х , у , z из множества Х из того, что х находится в отношении с у , а у находится в отношении с z следует, что х находится в отношении с z.

R транзитивнона Х Û("х , у , z Î Х ) х R у Ù у R z Þ х R z

Пример. Отношение «х кратно у » транзитивно, т.к. если первое число кратно второму, а второе кратно третьему, то первое число будет кратно третьему.

Граф транзитивного отношения с каждой парой стрелок от х к у и от у к z содержит стрелку, идущую от х к z.

7. Связность

Определение . Отношение R намножестве Х называется связным, если для любых элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .

R связнона Х Û("х , у , z Î Х ) х R у Ú у R z Ú х = у

Другими словами: отношение R намножестве Х называется связным, если для любых различных элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .

Пример. Отношение «х < у » связно, т.к. какие бы мы действительные числа не взяли, обязательно одно из них будет больше другого или они равны.

На графе связного отношения все вершины соединены между собой стрелками.

Пример. Проверить, какими свойствами обладает

отношение «х – делитель у », заданное на множестве

Х = {2; 3; 4; 6; 8}.

1) данное отношение рефлексивно, т.к. каждое число из данного множества является делителем самого себя;

2) свойством антирефлексивности данное отношение не обладает;

3) свойство симметричности не выполняется, т.к. например, 2 является делителем числа 4, но 4 делителем числа 2 не является;

4) данное отношение антисимметрично: два числа могут быть одновременно делителями друг друга только в том случае, если эти числа равны;

5) отношение транзитивно, т.к. если одно число является делителем второго, а второе – делителем третьего, то первое число обязательно будет делителем третьего;

6) отношение свойством связности не обладает, т.к. например, числа 2 и 3 на графе стрелкой не соединены, т.к. два различных числа 2 и 3 делителями друг друга не являются.

Таким образом, данное отношение обладает свойствами рефлексивности, асимметричности и транзитивности.

§ 3. Отношение эквивалентности.
Связь отношения эквивалентности с разбиением множества на классы

Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пример. Рассмотрим отношение «х однокурсник у » на множестве студентов педфака. Оно обладает свойствами:

1) рефлексивности, т.к. каждый студент является однокурсником самому себе;

2) симметричности, т.к. если студент х у , то и студент у является однокурсником студента х ;

3) транзитивности, т.к. если студент х - однокурсник у , а студент у – однокурсник z , то студент х будет однокурсником студента z .

Таким образом, данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, а значит, является отношением эквивалентности. При этом множество студентов педфака можно разбить на подмножества, состоящие из студентов, обучающихся на одном курсе. Получаем 5 подмножеств.

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

Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).

Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х , порождает разбиение этого множества на классы, то оно является отношением эквивалентности.

Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?

Построим граф данного отношения:

Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х 1 = {3; 6}, Х 2 = {1; 4; 7}, Х 3 = {2; 5; 8}.

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

В начальном курсе математики также встречаются отношения эквивалентности, например, «выражения х и у имеют одинаковые числовые значения», «фигура х равна фигуре у ».