Математическое моделирование баз данных

Первая нормальная форма файла. Записью называется конечная последовательность x= (x₁, ×××, x_n) элементов x_iÎA_i, 1 £ i £ n. Число n называется длиной записи. Для каждого i множество A_i называется доменом i-го атрибута, элемент x_i называется i -м атрибутом или i -й компонентой записи x.

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

Определение 1. (1NF) Файл находится в первой нормальной форме, если для него задано некоторое положительное целое число n и последовательность множеств

(A₁, ×××, A_n) таких, что

· файл состоит из записей (x₁, ×××, x_n)Î A₁´ ×××´A_n,

· среди этих записей (x₁, ×××, x_n)Î A₁´ ×××´A_n нет одинаковых.

Пример 1. Записи файла расположим в таблице 1.2. В первой строке этой таблицы будут выписаны имена, обозначающие домены атрибутов. Эти имена мы будем называть атрибутами.

Таблица 1.2.

Пример набора записей

ВУЗ	Номер зачетки	ФИО	Год поступления
АмГПГУ		Иванов Павел Сергеевич
КнАГТУ		Петрова Галина Сергеевна

 

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

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

Вторая нормальная форма. Рассмотрим файл, находящейся в первой нормальной форме. Его записи x=(x₁, ×××, x_n) Î A₁ ´A₂ ´ ××× ´A_n будут составлять некоторое отношение R Í A₁ ´A₂ ´ ××× ´A_n. Файл будет состоять из всех элементов множества R.

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

· Атрибут A_k функционально зависит от множества атрибутов , еслидля любых элементов x, y ÎR Í A₁ ´ A₂ ´ ××× ´ A_n из равенства их компонент следует равенство .

· Если атрибут A_k функционально зависит от множества атрибутов , но не зависит функционально ни от какого строго содержащегося в нем подмножества , то A_k называется функционально полно зависящим от множества атрибутов .

· Множество атрибутов называется ключом записи файла, если во-первых для всех k Î{ 1, 2, ×××, n } атрибуты A_k функционально зависят от , и во-вторых это множество атрибутов удовлетворяет условию минимальности, в том смысле, что для любого подмножества множества некоторый атрибут A_k не зависит функционально от атрибутов этого подмножества. Во множестве всех ключей можно отметить некоторые ключи. Эти ключи называются выделенными. Остальные – не выделенными.

· Первичным ключом называется произвольный выделенный ключ. Ключ, не являющийся первичным, называется возможным.

Определение 3. (2NF) Файл с первичным ключом находится во второй нормальной форме, если он находится в первой нормальной форме, и для любого атрибут A_k функционально полно зависит от атрибутов .

Поскольку множество записей для файла в первой нормальной форме совпадает с отношением, определенном этим файлом, то можно говорить о второй нормальной форме отношения.

Пример 2. В приведенной выше таблице 1.2 определим первичный ключ как множество атрибутов {ВУЗ, Номер зачетки}. Год поступления зависит от номера зачетки. Поэтому зависимость года поступления от первичного ключа не является функционально полной. Стало быть, файл не находится во второй нормальной форме. Разобьем этот файл на два файла (таблицы 1.3 и 1.4), находящиеся во второй нормальной форме. Первый файл (таблица 1.3) не будет содержать года поступления.

Таблица 1.3.

Первый файл разбиения

ВУЗ	Номер зачетки	ФИО
АмГПГУ		Иванов Павел Сергеевич
КнАГТУ		Петрова Галина Сергеевна

Второй (таблица 1.4) содержит номер зачетки и год поступления. Он состоит из одной записи.

Таблица 1.4.

Второй файл разбиения

Номер зачетки	Год поступления

Третья нормальная форма

Определение 4. Атрибут A_k транзитивно зависит от множества атрибутов , если существует множество, состоящее из атрибутов , каждый из которых функционально зависит от , такое, что A_k функционально зависит от .

Определение 5. (3NF) Файл с первичным ключом находится в третьей нормальной форме, если он находится в первой нормальной форме, и для любого функциональная зависимость атрибута A_k от атрибутов не является транзитивной.

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

Упражнения

1. Задано подмножество AÍU. Найти все подмножества XÍU, для которых

A ÇX= Æ.

2. Решить систему уравнений

3. Решить уравнения

(1) .

(2) .

(3) .

(4) .

4. Пусть - множество всех функций B ® A. Установить биекции между множествами

(1) A ´ B и B ´ A;

(2) (A ´ B)^С и A^C ´ B^C;

(3) (A^B)^C и A^B´C;

(4) A^BÈC и A^B ´ A^C, если B Ç C = Æ.

5. Построить бинарное отношение

(1) рефлексивное, симметричное, не транзитивное,

(2) рефлексивное, антисимметричное, не транзитивное,

(3) рефлексивное, транзитивное, не симметричное,

(4) антисимметричное, транзитивное, не рефлексивное.

6. Доказать, что пересечение семейства отношений эквивалентности на заданном множестве является отношением эквивалентности.

7. Построить пример частично упорядоченного множества, имеющего ровно один минимальный элемент, но не имеющего наименьшего элемента.

8. Доказать, что если R – отношение порядка, то R^-1 – отношение порядка.

9. Доказать, что пересечение отношений порядка является отношением порядка. Всегда ли объединение отношений порядка является отношением порядка?

10. Найти число рефлексивных отношений на множестве из n элементов.

11. Найти число симметричных отношений на множестве из n элементов.

12. Будет ли множество функций X ® R решеткой относительно отношения порядка

f£g Û f(a) £g(a)?

13. Сколько подмножеств множества A={1,2,∙∙∙,300} содержат по крайней мере одно число кратное 5, и ни одного – кратного 10.

14. Сколько подмножеств множества A={1,2,∙∙∙,300} не содержат ни чисел кратных 4, ни чисел кратных 6?

15. Сколько подмножеств множества A={1,2,∙∙∙,300} состоят из чисел кратных 4, но не содержат чисел кратных 6?

16. Сколько подмножеств множества A={1,2,∙∙∙,300} состоят из чисел кратных 4 и, сверх того, содержат по крайней мере одно число кратное 6?

 

КОМБИНАТОРИКА

Комбинаторикой называется раздел дискретной математики, который занимается следующими вопросами:

1. Задача перечисления: найти количество элементов заданной математической модели.

2. Задача перебора: построить алгоритм перебора этих элементов.

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

Конечная математическая модель в комбинаторике называется конфигурацией. Мы изучим следующие конфигурации: размещения, сочетания, разбиения и их обобщения. Для дальнейшего изучения рекомендуем [14], [15], [21].

Размещения

Постановка задачи. Дано m предметов и n ящиков, в которые размещаются предметы. Сколько существует размещений, удовлетворяющих некоторым заданным условиям?

Определение 1. Размещением с повторениями называется функция

f:{ x₁, x₂, ×××, x_m } ®{ y₁, y₂, ×××, y_n }.

Элементы x_i называются предметами, а y_j - ящиками.

Полагая a_i = f(x_i), легко убедиться в том, чточисло всех размещений с повторениями равно количеству последовательностей { a₁, a₂, ×××, a_m } чисел 1£ a_i £ n и значит оно равно n^m.

Определение 2. Рассмотрим некоторое конечное множество равновероятных элементарных событий, которые мы будем иногда назвать исходами. Событием называется подмножество множества всех исходов. Его элементы называются благоприятными исходами. Вероятность события определяется как отношение количества благоприятных исходов к количеству всех исходов.

Например, если мы бросаем монету, то возможны два исхода. Число исходов выпадения «орла» равно 1. Значит, вероятность выпадения орла равно 0.5.