Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
11
Добавлен:
27.03.2016
Размер:
285.06 Кб
Скачать

Кононов Василий, Сагитова Адиля и Главатских Павел

Глава 2

 

Глава 2. Реляционная алгебра.

 

 

Неделимый объект или скаляр

– это объект,

Определение.

Основные понятия.

 

представляющий собой неделимое целое, т.е. не являющийся множеством.

Определение. Домен – это именованное{ } множество скаляров{ одного типа.} Пример. Натуральные числа = 1,2,3, … . Русские имена = Иван, Пётр, … .

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

||В дальнейшем будет дано определение типа.

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

||В дальнейшем для сокращения будем называть «n-местные отношения» просто ||«отношениями».

 

Определение.

 

Отношение

 

 

это

n-арное отношение

на доменах

1 × 2 × … ×

 

– атрибут, назовём

 

 

 

отношения.

 

 

 

 

 

 

 

 

. Имя каждого домена назовём атрибутом, а выражение

вида

 

, где

 

 

1

 

2

 

 

схемой

 

 

 

 

 

 

 

//“ ” –(является1, 2, … ,подмножеством)

,

 

 

 

 

– декартово произведение.

 

 

 

Реляционная

алгебра

 

 

 

 

 

 

 

 

 

 

 

Определение.

 

×

× …× это

 

совокупность

носителя

 

и

сигнатуры , определяемых следующим образом:

 

 

, где

 

множество

 

 

 

 

 

 

отношений разной степени арности,

 

множество операций

реляционной

 

 

 

 

=

 

 

 

 

 

 

алгебры:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1)теоретико-множественные операции;

2)специальные операции.

Каждый элемент отношения называется кортежом.

Кононов Василий, Сагитова Адиля и Главатских Павел Глава 2

Элементы отношения (его атрибуты, схема, кортежи) определяют плоскую

таблицу аналогично тому, как бинарное отношение задаёт матрицу

×

. Т.е.

отношение ( 1

, 2

, … , ) будет задавать плоскую таблицу

:

 

 

 

1

 

2

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

1

 

 

1

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

2

 

 

2

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

3

 

 

3

 

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пример.

 

 

 

 

 

 

 

 

 

 

 

 

Таблица1

«Студент2 »

(№3

зачётной

книжки

,

ФИО, Группа). Здесь

Соответственно,

 

,

,

 

, …,

, где – домены.

 

 

№ зачётной книжки, ФИО и группа – это атрибуты (имена соответствующих доменов). Наборы кортежей, которые составляют конкретную таблицу,

соответствующей схеме э ого отношения, могут выглядеть следующим образом:

Студент = { 123,

ИвановИ. И. ,

К4−221

131,

ПетровП. П. ,

К4−

281

211,

КузнецовВ. И. , К4

361 }.

Степень отношения определяет количество атрибутов в схеме. Кардинальное число (или мощность) отношения определяет количество кортежей в отношении.

Соотношения между формальными и неформальными определениями:

Неформальные

Формальные

 

 

Таблица

Отношение

 

 

Строка, запись

Кортеж

 

 

Количество строк

Кардинальное число

 

 

Столбец, поле

Атрибут

 

 

Тип данных

Домен

 

 

Количество столбцов

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

 

 

Кононов Василий, Сагитова Адиля и Главатских Павел

Глава 2

Задачи, которые решаются при помощи реляционных баз данных:

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

2)Определение структуры базы данных – решается при помощи определения схемы отношений. Схема базы данных – схема (модель) некоторой предметной области (в которой мы работаем).

3)Определение ограничений целостности данных – решается с помощью формул исчисления предикатов (с формально-теоретической точки зрения). Пример ограничения целостности данных: в рассмотренной выше таблице «Студент» есть графа «№ зачётной книжки». Если в базе будет храниться

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

Пусть заданы 2 отношения: Доср_сдача (№ зачётки, ФИО, предмет) и Сдача_в_срок (№ зачётки, ФИО, предмет).

Определим, с какими данными (наборами кортежей) мы будем работать:

Сдача_в_срок = С = { < 121, Иванов, ДМ >,

<123, Петров, Теория БД >,

<124, Сидоров, Физика > }

Доср_сдача = Д = { < 121, Иванов, ДМ > }.

//Т.е. Иванов попытался сдать досрочно, но не сдал, а сдал потом, как и все, в срок.

Теоретико-множественные операции (здесь у множеств должны совпадать

 

 

 

 

( 1, 2

, … , ) = 1( 1, 2, … , ) 2( 1, 2, …,

, , )

 

количество столбцов, а также домены):

( 1, 2, … , )

 

1

2

 

 

 

:

 

 

 

 

 

;

1) Объединение

 

 

 

 

 

 

 

результат операции – это отношение

 

на столбцах

 

 

…,

 

 

 

 

 

 

 

 

 

 

 

 

{< 121, Иванов, ДМ >, < 123, Петров, Теория БД >, < 124, Сидоров, Физика >}.

Д∩ С

= { < 121,

( 1, 2

, … , ) = 1( 1, 2, … , ) 2( 1, 2, … , )

:

Д 2)С =Пересечение

 

 

 

 

 

 

 

Иванов, ДМ > }.

 

 

= { < 123, Петров, ( 1, 2

, … , )

= 1( 1, 2, … , )

( 1, 2, … , )

 

Кононов Василий, Сагитова Адиля и Главатских Павел

 

 

 

 

 

 

 

 

 

 

Глава 2

3)

Разность

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

:

 

ДекартовоС Д

 

 

 

Теория БД >, < 124, Сидоров, Физика > }.

 

 

4)

произведение –

=

 

 

, … ,

 

×

 

, … ,

:

 

 

 

= { < , … ,

,

, … ,

 

 

 

 

Д× С

 

121,( 1

Иванов

,1

ДМ, 121,)

Иванов1( 1 , ДМ )>, < 2121,( 1

Иванов) , ДМ, 123,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Петров, Теория БД >, < 121, …, 124, … >, < 123, …, 121, … >, …}.

 

 

 

 

Специальные операции:

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

атрибутов

 

1

( 1, … , )[ ] = ( )

 

 

 

 

 

 

 

 

1)

 

С (№1, …зачётки,

, ФИО, предмет) [№

зачётки] ={ {121,, … ,123,} 124}.

 

Проекция – это

 

 

 

 

 

 

 

 

 

 

; т.е. отношение

 

с набором

 

 

 

 

 

спроецировано на

 

, где

 

 

 

 

 

:

 

 

2)

Ограничение – 1( 1, … , )[БулевовыражениеподА] =

( 1

, … , ):

 

Д (№ зачётки, ФИО, предмет) [Предмет = 'ДМ'] = { 121, Иванов, ДМ }.

( ) ( )[ ] ( )

3) Соединение –

1, … , , 1, … , = 1 1, … , Булевовыражение 2 1, … , :

Д (№ зачётки, ФИО, предмет) [№зач. = №зач.] Группа (№ зач., № группы) = …

Если таблица выглядит следующим образом:

 

 

 

 

№ зачётки

 

 

 

 

 

 

 

№ группы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

121

 

 

 

 

 

 

 

 

К4-221

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

123

 

 

 

 

 

 

 

 

К6-222

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

124

 

 

 

 

 

 

 

 

К4-361

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

220

 

 

 

 

 

 

 

 

К8-331

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

то … = { 121, Иванов

ДМ, 121, К4-221}.

 

 

( 1

, … , ) ÷ 2

( 1, … , .)

 

она

 

 

 

( 1, … ,

, 1, … , ) = 1

 

Пример. Пусть даны

 

1

÷ 2

= 1

[

] ( 1[ ] × ) 1 [и]

. Задаётся

4) Деление –

 

 

 

 

 

 

1

= { , , , , , }

 

Тогда 1

÷ 2 = .

 

 

 

 

 

2

{ , }

 

следующим образом:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

наборы кортежей

 

 

 

 

 

 

 

 

 

.

Реляционная алгебра. Неформальное определение.

Глава 2

Кононов Василий, Саг това Адиля и Главатских Павел

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

Определение. База данных – это совокупность именованных таблиц. Каждая строка представляет собой запись о некотором объекте реального мира или его свойствах.

Для удобства идентификации записей вводят понятие первичного ключа.

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

В рассмотренной выше таблице «Студент» в качестве первичного ключа можно использовать № зачётной книжки# . Часто, для удобства чтения, первичный

ключ обозначают символом «диез» – “ ”: «Студент (# № зачётной книжки, ФИО, группа)». Если первичный ключСвязь– основноймежду таблицами, то д езов стоит. несколько.

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

Пример. Пусть есть 2 таблицы, в которых есть одинаковый атрибут (группа):

«Студент (# № зачётной книжки, ФИО, группа)» и

«Предмет (преподаватель, курс, группа)».

Допустим, что нам необходимо переименовать группы во всём институте. Предположим, что мы переименовали группы только в таблице «Студент», забыв это сделать во 2-й. В этом случае возникнет нарушение целостности данных. Если сделать иначе и ввести отдельную таблицу «Группа (#10, группа)», то в первых 2-х

||#10 – произвольный абстрактный номер, являющийся первичным ключом.

таблицах вместо атрибута «группа» можно писать этот уникальный идентификатор (10) в качестве ссылки. Таким образом, достаточно переименовать строковое представление имени группы только в одной таблице.

Определение. Внешний ключ – ссылка на первичный ключ другой таблицы.

Кононов Василий, Сагитова Адиля и Главатских Павел Глава 2

Введём обозначения: PK (primary key) – первичный ключ, FK (foreign key) – внешний ключ.

1)PK и FK должны быть определены на одном и том же домене.

2)В таблице с FK он не должен принимать значения, которые не принимает PK

в дрПонятиеугой таблиценормализации(т.е. нет ссылоки«вограниченияникуда»). на таблицах.

Определение. Нормализация – это приведение данных в таблице к определённому виду, заданному набором ограничений.

Про нормализованную таблицу говорят, что она находится в нормальной форме. Существуют различные нормальные формы (1NF, 2NF, 3NF, 3NF усиленная).

Набор ограничений для 1NF (1-й нормальной формы):

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

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

2)Строки не упорядочены сверху вниз.

3)Столбцы не упорядочены слева направо.

4)Все значения атрибутов атомарны.

В качестве атрибутов не могут выступать другие таблицы, линейные списки и т.д. Например, существует тип в базах данных: BLOB – Binary large object.

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

ь формулы следующего вида:

можно, ,использова, , Студент( , , )&Студент( , , ) ( = )&( = ) .

′ ′ ′ ′′ ′′ ′ ′ ′ ′ ′′ ′′ ′ ′′ ′ ′′

Что определяет эта формула? У нас есть отношение «Студент». Мы задаём предикат, структура которого соответствует схеме отношения. Т.е. у предиката такое же имя как у таблицы, количествоего аргументов совпадает с количеством доменов в таблице. 1-й аргумент – это PK (первичный ключ).

Соседние файлы в папке Lektsii_po_Diskretnoy_Matematike