Файл: Дискретная_мат._пос.pdf

 21

1.2.8. Контрольные вопросы и упражнения 
 
1.

Вставьте пропущенный знак “=” или “

≠”: 

{3,5} _____ {5,3}; 

         (3,5) _____ (5,3). 

2.

Нарисуйте  график  декартова  произведения 

Y

X

×

,  где 

}

5

,

1

{

=

X

, 

}

3

,

2

{

=

Y

. Совпадает ли он с графиком 

X

Y

×

? 

3.

Дайте определение бинарного отношения на множестве 

Х

. 

4.

Обведите кружком номер правильного ответа: 
Областью  определения  бинарного отношения 

R

  называется  множе-

ство 

1) 

;

}

,

)

,

{(

R

y

x

y

x

∈

                                                 2)

;

}

,

{

R

y

x

x

∈

                                                 3)

.

}

,

{

R

y

x

y

∈

5.

Найдите  область  определения  и  область  значений  отношения 

Q

  из 

примера 2 (п.п 1.2.2). 

6.

Какими способами можно задать бинарное отношение? 

7.

Нарисуйте график и схему отношения 

Р

 из примера 2 (см. 1.2.2). 

8.

Какое отношение является рефлексивным? 

9.

Какой  особенностью  обладает  матрица  рефлексивного  отношения? 
А матрица симметричного отношения? 

10.

Вставьте пропущенное слово: 
Отношение,  обладающее  свойствами  рефлексивности,  симметрич-
ности, транзитивности, называется отношением ________________ . 

11.

Запись 

]

[x

используется для обозначения ________ _____________ . 

12.

Какое отношение называется отношением порядка? 

 22

1.3. Реляционная алгебра 

1.3.1. Применение отношений для обработки данных 
 
Отношение может быть не только бинарным, в общем случае отношени-

ем называется подмножество 

n

X

X

X

R

×

×

×

⊆

…

2

1

, т.е. элементом отноше-

ния 

является 

упорядоченный 

набор 

)

,

,

,

(

2

1

n

x

x

x

…

, 

где 

n

i

X

x

i

i

,

,

2

,

1

,

…

=

∈

. При обработке данных наборы из 

n

 элементов называ-

ют  записями, 

i

-му  элементу  набора  соответствует 

i

-ое  поле  записи.  Записи 

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

Любая  ли  таблица  может  задавать  отношение?  Очевидными  являются 

следующие требования: 

1)

порядок столбцов таблицы фиксирован; 

2)

каждый столбец имеет название; 

3)

порядок строк таблицы произволен; 

4)

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

Число 

n

  столбцов  таблицы  называется  степенью  отношения  (говорят, 

что задано 

n

-арное отношение). Число строк в таблице – количество элементов 

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

 
1.3.2. Теоретико-множественные операции реляционной алгебры 
 
Так  как  отношения  являются множествами,  к  ним  применимы  обычные 

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

Пересечением двух отношений 

R

 и 

S

 называется множество 

S

R

∩

 всех 

записей, каждая из которых принадлежит как 

R

, так и 

S

 (рис. 1.12, а, б). 

Объединением двух отношений 

R

 и  

S

 называется множество 

S

R

∪

 за-

писей, которые принадлежат хотя бы одному из отношений 

R

 или 

S

 (рис.1.12, 

а, в). 

 23

Разностью двух отношений 

R

 и 

S

 называется множество 

S

R \

 всех за-

писей,  каждая  из  которых  принадлежит  отношению 

R

,  но  не  принадлежит 

отношению   

S

 (рис.1.12, а,г). 

В реляционной алгебре вводится операция расширенного декартова про-

изведения.  Пусть 

)

,

,

,

(

2

1

n

r

r

r

r

…

=

 – элемент 

n

-арного  отношения 

R

,  а               

)

,

,

,

(

2

1

m

s

s

s

s

…

=

  –  элемент 

m

-арного  отношения 

S

.  Конкатенацией  запи-

сей  r  и  s  назовем  запись 

)

,

,

,

,

,

,

,

(

)

,

(

2

1

2

1

m

n

s

s

s

r

r

r

s

r

…

…

=

,  полученную 

приписыванием записи 

s

 к концу записи 

r

. 

Расширенным декартовым произведением отношений 

R

 и  

S

 называет-

ся  множество 

}

,

)

,

{(

S

s

R

r

s

r

S

R

∈

∈

=

×

,  элементами  которого  являются 

все  возможные  конкатенации  записей 

R

r

∈

  и

S

s

∈

.  Отметим,  что 

полученное  отношение  имеет  степень 

m

n

+

  и  важен  порядок  выполнения 

операции:  

R

S

S

R

×

≠

×

. 

В  качестве  упражнения  запишите  расширенное  декартово  произведение 

R

S

×

 для отношений 

R

 и 

S

 (рис. 1.13) и сравните с отношением 

S

R

×

. 

 24

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

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

Пусть задано отношение R и список 

)

,

,

,

(

2

1

k

i

i

i

c

…

=

  –  упорядоченное 

подмножество номеров  столбцов. Проекцией отношения R на список c назы-
вается  отношение 

}

]

[

{

R

r

c

r

R

c

∈

=

π

,  записи  которого  содержат  только  те 

поля, которые указаны в списке 

с

.  Таким  образом,  операция проекции  позво-

ляет  получить “ вертикальное ” подмножество  отношения 

R

  (рис. 1.14, а). 

Операция проекции  выполняется в два  этапа: 1) выписываем записи отноше-
ния 

R

, включая только те поля, которые указаны в списке 

с

; 2) вычеркиваем в 

полученной таблице повторяющиеся строки (рис. 1.14, б, в). 

 
 
 
 Операция  селекции  (выбора)  дает  возможность  построения    “горизон-

тального” подмножества отношения, т.е. подмножества записей, обладающих 
заданным  свойством.  Обозначим 

F 

–  логическое  условие,  которому  должны 

удовлетворять  искомые  записи.  Селекцией  отношения 

R

  по  условию 

F

называется отношение 

R

F

σ

, содержащее те и только те записи отношения 

R

, 

для которых условие 

F

 истинно (рис. 1.15). 

 25

 
Соединение отношений по условию 

F

  обозначается 

S

R

F

и представ-

ляет собой отношение, записями которого являются конкатенации 

)

,

(

s

r

, удо-

влетворяющие условию 

F

. Таким образом, соединение можно выполнить в два 

этапа: 1) выполнить операцию расширенного декартова произведения 

S

R

×

; 

2) выполнить селекцию полученного отношения по условию 

F

. 

)

(

S

R

S

R

F

F

×

=

σ

На рис. 1.16. приведен пример соединения отношений 

R

 и 

S

 по условию  

F  - 

"

"

1

1

B

A

<

,  где  знак “ < ” означает  лексикографический  (алфавитный)  по-

рядок. 

 
1.3.4. Решение задачи 5 контрольной работы № 1 
 
Задача. Отношения 

R

 и 

S

 заданы в виде таблиц (рис. 1.17, а). Совмести-

мы ли эти отношения? Записать обозначение проекции 

R

 на список 

)

2

,

3

(

=

c

и выполнить эту операцию. Записать обозначение соединения отношений 

R

 и 

S

 по условию 

F 

– “A

2

≥

B

1

”  и выполнить эту операцию. 

Решение. Степень отношения 

R

 равна 3 (три столбца в таблице), степень 

отношения 

S

 равна 2 (два столбца), значит, отношения 

R

 и 

S

 несовместимы и 

над ними нельзя выполнять операции пересечения, объединения, разности.