Відношення. Властивості бінарних відношень. Реляційна модель даних

Відношення реалізують у математичних термінах на абстрактних множинах реальні зв’язки між реальними об’єктами. Відношення застосовуються під час побудови комп’ютерних баз даних, які організовані у вигляді таблиць даних. Зв¢язки між групами даних у таблицях описуються мовою відношень. Самі дані обробляються й перетворюються за допомогою операцій, математично точно визначених для відношень. Такі бази даних називаються реляційними й широко використовуються для збереження й обробки найрізноманітнішої інформації: виробничої, комерційної, статистичної тощо. Відношення також часто застосовують у програмуванні.

õ Приклади задач

1. Нехай маємо відношення A Ì X ´ Y. Визначити переріз по кожному елементу із X та по підмножині {x_2, x₃}.

Розглянемо відношення AÌX´Y; якщо x_iÎX, то переріз по x_i відношення А, позначений А(x_i), є множина yÎY таких, що (x_i, y ) ÎА.

Множина всіх перерізів відношення А називається фактор-множиною Y по відношенню А і позначається Y/A. Вона повністю визначає відношення А.

Приклад:

X={ x₁, x₂, x₃, x₄, x₅};

Y= { y₁, y₂, y₃, y₄};

A= {( x₁, y₁), (x₁, y₃), ( x₂, y₁), ( x₂, y₃), ( x₂, y₄), ( x₃, y₁), ( x₃, y₂), ( x₃, y₄),

( x₄, y₃), ( x₅, y₂), ( x₅, y₄)}.

Запишемо під кожним елементом із множини X відповідний переріз відношення А, тоді елементи другого рядка утворять фактор-множину Y/A:

x₁ x₂ x₃ x₄ x₅

{y₁,y₃} { y₁,y_3, y₄} { y₁,y_2, y₄} {y₃} { y_2, y₄}.

Об’єднанням перерізів по елементах деякої підмножини B Ì X є переріз A(B) цієї підмножини, тобто A(B)= . Так,

A(x_2, x₃) = A(x₂) È A(x₃) = { y₁, y_2, y_3, y₄}.

õ Завдання

1. Побудуйте матрицю й граф для таких відношень, визначених на множині

А = {1, 2, 3}:

а) {(1, 1), (1, 2), (1, 3)};

б) {(1, 1), (2, 1), (2, 2), (2, 3)};

в) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)};

г) {(1, 3), (3, 1)}.

2. Запишіть список елементів для тернарного відношення R, що задане на множині натуральних чисел таким чином: (a, b, c)ÎR, якщо

0 < a < b < c < 5.

3. Дано дві множини X= {x₁, x₂, x₃, x₄, x₅, x₆}, Y = {y₁, y₂, y₃, y₄}. Бінарне відношення A = {(x₁,y₂ ), (x₂, y₁ ), (x₂, y₂), (x₄, y₂), (x₄, y₃), (x₅, y₁), (x₅, y₃)}. Необхідно:

а) записати область визначення й область значень;

б) визначити переріз по кожному елементу із X;

в) визначити переріз по підмножинах X^¢ = {x₁, x₄}; X^¢¢ = {x₂, x₃, x₅};

г) записати матрицю й накреслити граф;

д) визначити симетричне відношення A^-1.

4. Представте бінарне відношення, задане графом (рис. 7), як множину впорядкованих пар і запишіть його матрицю. Якими властивостями характеризується даний граф?

Рис. 7. Граф бінарного відношення

5. Нехай відношення А задане на множині дійсних чисел R. Тоді на площині кожній упорядкованій парі відповідатиме точка з координатами x та y, якщо (x, y) Î A. Відношення А буде зображатися графіком, що представляє собою підмножину точок площини (області, лінії або окремої точки). При цьому відношення записується як

A = {(x, y) Î R´R| P(x, y)},

що визначає властивість відношення А, яке виражається зазвичай алгебраїчними рівняннями й нерівностями.

6. Побудувати графіки для таких відношень (у тих випадках, коли графік є частиною площини, ця область штрихується):

а) {(x, y) Î R´R| x = y};

б) {(x, y) Î R´R| y ³ x};

в) {(x, y) Î R´R| x ³ 0; y £ x та x + y £ 1}.

7. Запишіть відношення, графіки яких показані на рис. 8.

Рис. 8. Графіки відношень

8. Визначте, які властивості має кожне з наведених відношень. Відношення задані на множині A = {1, 2, 3, 4}:

а) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3,4)};

б) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)};

в) {(2,4), (4,2)};

г) {(1, 2), (2, 3), (3, 4)};

д) {(1, 1), (2, 2), (3, 3), (4, 4)};

e) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}.

9. Для деякої дизайнерської фірми у м. Харкові було складене відношення ¢¢Фірма-продукція 1¢¢.

Фірма-продукція 1

Назва	Місто	Продукція
ЧПП ¢¢Оріон¢¢	Одеса	Меблі
ТОВ ¢¢День¢¢	Харків	Світильники
ЧКП ¢¢Sit¢¢	Одеса	Меблі
ЧКП ¢¢Sit¢¢	Одеса	Світильники
ТОВ ¢¢House¢¢	Харків	Світильники
ТОВ ¢¢House¢¢	Харків	Матеріали для ремонту

Припустимо, існує ще одне відношення, складене деякою фірмою у м. Києві.

Фірма-продукція 2

Назва	Місто	Продукція
ТОВ ¢¢Днепр¢¢	Київ	Матеріали для ремонту
ЧКП ¢¢Virta¢¢	Київ	Сантехніка
ЧКП ¢¢Virta¢¢	Київ	Кахлі
ЧПП ¢¢Оріон¢¢	Одеса	Меблі
ЧКП ¢¢Софія¢¢	Київ	Сантехніка
ЧКП ¢¢Софія¢¢	Київ	Кахлі
ТОВ ¢¢День¢¢	Харків	Світильники

Виконайте операції об’єднання, перетину й різниці над відношеннями ¢¢Фірма-продукція 1¢¢ і ¢¢Фірма-продукція 2¢¢. Назвіть таблицю, одержану в результаті виконання операції об¢єднання ¢¢Фірма-продукція 3¢¢.

õ Завдання для самостійної роботи

1. Доведіть наступні властивості семитризації та композиції відношень:

а) (AB)^-1 = B^-1A^-1;

б) (A È B)^-1 = A^-1 È B^-1;

в) (A Ç B)^-1 = A^-1 Ç B^-1;

г) (A^-1)^-1 = A.

2. Доведіть наступні твердження:

а) якщо відношення A та B рефлексивні, то рефлексивні й відношення

A È B, A Ç B, AB;

б) якщо відношення A та B антирефлексивні, то антирефлексивні й відношення A È B, A Ç B;

в) якщо відношення A та B симетричні, то симетричні й відношення

A È B, A Ç B;

г) якщо відношення A та B транзитивні, то транзитивне й відношення

A Ç B.

3. Побудувати графіки для наступних відношень (у тих випадках, коли графік є частиною площини, ця область штрихується):

а) {(x, y) Î R´R| y ³ x та x ³ 0};

б) {(x, y) Î R´R| x² + y² =1}.

5. Виконайте з’єднання відношень ¢¢Фірма-продукція 3¢¢ і ¢¢Фірма-телефон¢¢. Відношення ¢¢Фірма-телефон¢¢ таке:

Фірма-телефон

Назва	Телефон
ЧПП ¢¢Оріон¢¢	784-556
ТОВ ¢¢День¢¢	145-134
ЧКП ¢¢Sit¢¢	356-777
ТОВ ¢¢House¢¢	122-890
ТОВ ¢¢Днепр¢¢	555-78-12
ЧКП ¢¢Virta¢¢	233-77-77
ЧКП ¢¢Софія¢¢	550-09-09

Запишіть відношення, одержане в результаті операції з’єднання, як ¢¢Фірма-продукція-телефон¢¢.

5. Виконайте обмеження відношення ¢¢Фірма-продукція-телефон¢¢ за умови:

а) продукція = меблі;

б) продукція = матеріали для ремонту, місто = Харків;

в) місто = Одеса.

Лабораторна робота № 8

Алгоритми

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

Рис. 9. Загальна схема алгоритму

Для візуалізації роботи алгоритму можна використовувати блок-схеми. Елементи блок-схеми:

Рис. 10. Елементи блок-схеми

õ Приклади задач

1. Відсортувати у порядку зростання задану послідовність чисел

3, –1, 0, 1, 8, 6, 5, -5.

Розв’язок

Ідея алгоритму:

1) беремо перше число;

2) порівнюємо його за величиною з наступним числом;

3) якщо перше число більше наступного, то переставляємо ці числа місцями;

4) збільшимо лічильник i на одиницю та переходимо до наступного числа;

кроки 2-4 повторюємо, доки і не стане рівним n.

Цикл повинен повторюватися n´n разів (n — кількість елементів у масиві).

Рис. 11. Робота процедури сортування

Крім масиву будемо використовувати додаткову змінну k для перестановки чисел. Перестановку чисел здійснювати маємо таким чином:

k = A[i],

A[i] = A[i+1],

A[i+1] = k,

Рис. 12. Схема здійснення перестановки чисел

Вхідний масив A[1] …A[n] — послідовність довжини n, що підлягає сортуванню. Блок-схема алгоритму має такий вигляд:

Рис. 13. Блок-схема сортування послідовності чисел

õ Завдання

1. Скласти алгоритм і зобразити за допомогою блок-схеми розв’язання квадратного рівняння .

2. Скласти алгоритм і зобразити за допомогою блок-схеми знаходження максимального числа в послідовності чисел.

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

4. Скласти алгоритм і зобразити за допомогою блок-схеми процедуру знаходження в матриці m*n max і min числа. Видати на екран матрицю, max і min числа.

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

6. У матриці m*n поміняти місцями перший стовпець і другий рядок. Видати на екран обидві матриці. Скласти алгоритм та зобразити за допомогою блок-схеми.

õ Завдання для самостійної роботи

1. Дано три числа a, b, c. Знайти максимальне число серед цих чисел. Скласти алгоритм та зобразити за допомогою блок-схеми.

2. Скласти алгоритм та відтворити за допомогою блок-схеми розв’язання рівняння ax + b = 0.

3. Скласти алгоритм і зобразити за допомогою блок-схеми знаходження мінімального числа в послідовності чисел.

4. Зчитати в масив дійсні числа, доки наступне введене число не стане більшим за попереднє. Після цього на екран видати кількість парних та непарних чисел, середньоарифметичне послідовності, що введена. Скласти алгоритм і зобразити за допомогою блок-схеми.

5. Помножити матрицю m*n на число. Видати на екран обидві матриці. Скласти алгоритм та зобразити за допомогою блок-схеми.

6. Програма повинна зчитувати в масив дійсні числа, доки не буде введено 1. Після цього треба знайти максимальне число послідовності й сформувати новий масив за принципом: якщо різниця між максимальним числом та елементом масиву менша за 5 — записувати 1, якщо більша за 5 — записувати 0. На екран видати послідовність, що введена, максимальне число й послідовність, яка утворилася і містить 0 та 1. Скласти алгоритм та зобразити за допомогою блок-схеми.

Лабораторна робота № 9