Введение в предмет «Базы данных»

С. В. Зыкин

БАЗЫ ДАННЫХ

Конспект лекций

 

Омск – 2006

УДК 004.6

ББК 32.973

З 96

 

 

Рецензенты:

С.М. Добровольский, канд. физ.-мат. наук, доцент ОмГУ;

А.И. Задорин, д-р. физ.-мат. наук, проф. Института Математики СО РАН

 

Зыкин С.В.

З 96 Базы данных: Конспект лекций. – Омск: ОмГТУ, 2006. – 20 с.

 

 

Содержит краткое описание лекционного курса «Базы данных». Предназначено для подготовки к экзаменам студентов высших учебных заведений.

 

 

Печатается по решению редакционно-издательского Совета Омского государственного технического университета.

 

УДК 004.6

ББК 32.973

 

© С.В. Зыкин, 2006

© Омский государственный

технический университет, 2006

 

Введение в предмет «Базы данных»

 

1.1. Основные определения и категории БД

Определение. Базой данных называется совокупность специальным образом организованных данных, которые: 1) подлежат долговременному хранению в памяти ЭВМ; 2) являются носителем информации о сравнительно небольшом количестве классов объектов, однако количество экземпляров объектов в классе может быть огромным (все классы объектов относятся к одной прикладной области); 3) используются в одном или нескольких приложениях, относящихся к одной прикладной области.

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

 

При описании БД на физическом уровне используются следующие понятия:

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

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

3. Файл – совокупность однотипных физических записей.

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

5. Индексные файлы – содержат структурированные данные для быстрого поиска физических записей в файлах.

 

На логическом (внешнем) уровне описания данных используются следующие понятия:

1. Элемент данных (атрибут) – минимальная единица информации идентифицируемая СУБД. Соответствует полю на физическом уровне, которому присваивается имя и определяется тип.

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

3. Отношение (таблица) – совокупность однотипных логических записей (кортежей). Содержит данные о каком-либо классе объектов.

4. Схема отношения – совокупность имен элементов данных (заголовок таблицы), на которой определено отношение.

5. Схема БД – совокупность схем отношений с установленными связями и ограничениями целостности на данные.

Пример схемы БД: Рассмотрим БД о сотрудниках, оборудовании и их рабочих местах.

 

 

Требования к БД и методы их реализации

 

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

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

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

 

2. Защита от программных и аппаратных сбоев должна обеспечиваться средствами СУБД. Типы сбоев:

а) Логический сбой: 1) Пользователь вводит информацию об объекте, но эта информация уже есть в БД. СУБД по значению ключевых полей должна определить дублированные данные и отвергнуть операцию (ошибка первого рода). 2) Пользователь удаляет запись об объекте, но на нее есть ссылка из других объектов (записей). СУБД должна отвергнуть операцию (ссылочная целостность данных или ошибка второго рода).

б) Физический сбой происходит в результате прекращения работы СУБД (ошибка системного программного обеспечения, отключение электропитания). В результате может быть нарушена структура БД. Для решения проблемы используются: 1) локальность модифицирующих воздействий – это структурное свойство организации данных (связный список не обладает этим свойством); 2) архивация данных; 3) СУБД ведет журнал модификаций в служебном файле. Перед началом очередной модификации в системный журнал помещается информация, достаточная для завершения операции после повторного старта СУБД.

 

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

Реализация принципа независимости данных достигается трехуровневым описанием представления данных:

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

2) Глобальное логическое описание – логическое описание БД как единого целого (схема БД).

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

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

а) Пароль при входе в систему. То есть внешние схемы снабжены паролем доступа к секретным данным.

б) Защита файловой системы средствами операционной системы.

в) Шифрование данных на физическом уровне.

 

Элементы данных и связи

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

Ошибки в определении элемента данных:

1) «Цех» – этот элемент данных может содержать в себе другие элементы: начальник цеха, выпускаемая продукция и др., то есть отсутствует семантическая однозначная интерпретация этого элемента (наверно, имелось в виду название цеха или номер цеха).

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

3) «Возраст сотрудника» – этот элемент имеет изменяемое значение (в системе отсутствует событие, приводящее к необходимости изменения этого значения), нужно использовать элемент «Дата рождения», а возраст вычислять в приложении. Элемент данных «Номер курса студента» не является изменяемым, поскольку для изменения его значения в системе должно произойти событие: приказ по деканату.

 

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

На начальном этапе проектирования связи могут устанавливаться между элементами данных.

Типы связей:

1) 1:1 – "один к одному". Одному значению первого объекта соответствует не более одного значения второго объекта (номер студента à номер читательского билета);

2) М:1 – "многие к одному". Множеству значений первого объекта соответствует не более одного значения второго объекта (табельный номер сотрудника à должность сотрудника);

3) 1:М – "один ко многим". Одному значению первого объекта соответствует множество значений второго объекта, где МÎ{0,1,2...} (должность сотрудника ®® табельный номер сотрудника);

4) М:М – "многие ко многим". Множеству значений первого объекта соответствует множество значений второго объекта (должность сотрудника ®® разряд ЕТС сотрудника).

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

 

Правило склейки записей. Если между элементами данных A и B установлена связь типа 1:1 или М:1, то элемент данных B присоединяется к элементу данных A, образуя логическую запись (тип записи). Элемент данных A в этом типе записи будет ключевым.

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

 

Древовидные модели данных

 

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

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

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

В древовидной схеме данных предполагается, что между узлом (схемой отношения) предком и узлом потомком установлена связь типа 1:М и каждый узел имеет не более одного предка.

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

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

Примечание. Малое количество информации может быть записано сбалансированным и бинарным деревьями. Например: родословная собаки – сбалансированное бинарное дерево, а потомки собаки – несбалансированное и не бинарное дерево. Особое значение сбалансированные и бинарные деревья имеют для представления информации на физическом уровне (организация индексных файлов). Записи во всех узлах однотипны, а связи-ссылки не имеют содержательного смысла. Используются только для представления лексикографического порядка узлов. Такие деревья называют иерархическими файлами.

Зависимость данных от структуры. Если в структурированном представлении данных для получения каких-либо сведений требуется воспользоваться связями, то такое представление называется зависимым от структуры.

 

Сетевые модели данных

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

Свойство. Если схема данных содержит связь типа М:М, то она является сетевой.

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

Правило преобразования сложной сетевой схемы к простой сетевой. Допустим, что схема данных содержит две схемы отношений (типов записей) со связью М:М. A и B ‑ ключи этих записей. Создается новое отношение с ключом A+B. Со схемы удаляется связь типа М:М, а от нового отношения устанавливается связь М:1 к исходным отношениям.

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

 

Общие данные, данные пересечения, изолированные данные:

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

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

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

 

Реляционная модель данных

Определение. Табличное представление данных называется реляционным, если выполнены следующие требования:

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

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

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

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

5. Каждый элемент таблицы должен быть элементом данных.

6. Связи между таблицами на схеме БД устанавливается по одноименным атрибутам данных.

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

 

Операции реляционной алгебры

 

Теоретической основой языков запросов к реляционным БД является реляционная алгебра. Операндами в реляционной алгебре являются отношения R_i и их реализации – таблицы r_i, k_i – арность отношения R_i (количество столбцов); n_i – количество строк в R_i.

Базисный набор операций:

1. Объединение: R=R₁ È R₂. Результат операции R содержит кортежи из R₁ и R₂. Ограничения на операнды: а) k₁=k₂; б) схемы R₁ и R₂ также должны совпадать; в) дублирующие кортежи в результат включаются только один раз. Пример:

 

R1

=

A

B

C

R2

=

A

B

C

R

=

A

B

C

a1

b1

c1

a2

b1

c2

a1

b1

c1

a2

b1

c2

a3

b2

c2

a2

b1

c2

a3

b2

c1

a3

b2

c1

a3

b2

c2

 

SQL: R₁ UNION R₂;

2. Разность: R=R₁ \ R₂. Результат операции R включает в себя кортежи из R₁, которых нет в R₂. Ограничения на операнды: а) k₁=k₂; б) схемы R₁ и R₂ также должны совпадать. Пример:

 

R	=	A	B	C
		a1	b1	c1
		a3	b2	c1

 

SQL: к сожалению в стандарте SQL нет соответствующего оператора, например, как в ORACLE: R₁ MINUS R₂;, поэтому можно воспользоваться другими конструкциями, например: DELETE * FROM R₁ WHERE ID IN (SELECT ID FROM R₂);, где ID – одиночное значение некоторого выражения, например первичного ключа в R₁ и R₂.

3. Декартово произведение. R=R₁ ´ R₂. Результат операции R: каждый кортеж из R₁ дополняется кортежем из R₂; арность результата – k = k₁+k₂; n = n₁*n₂. Результат декартова произведения не может содержать дублирующие кортежи.

Пример: пусть

 

R2	=	B	C	D
		b1	c1	d1
		b2	c2	d1

 

тогда

 

R	=	A	R1.B	R1.C	R2.B	R2.C	D
		a1	b1	c1	b1	c1	d1
		a2	b1	c2	b2	c2	d1
		a3	b2	c1	b1	c1	d1
		a1	b1	c1	b2	c2	d1
		a2	b1	c2	b1	c1	d1
		a3	b2	c1	b2	c2	d1

 

SQL: SELECT * FROM R₁, R₂;

4. Селекция: R = s_F(R_i), где F - логическая формула над атрибутами из R_i. Результатом операции является таблица R, содержащая те же столбцы, что и R_i и строки из R_i, подстановка которых в F дает значение "истина". Пример: R = s_C=c1 (R₁):

 

R	=	A	B	C
		a1	b1	c1
		a3	b2	c1

 

SQL: S ELECT * FROM R₁ WHERE F;

5. Проекция: R = p_X(R_i), где X - подмножество атрибутов их схемы R_i. Результат операции - таблица со схемой (заголовком) X; строки таблицы формируются из таблицы R_i, но только для атрибутов из X (вырезка по столбцам); дублирующие кортежи из результата удаляются. Пример: R = p_BC(R₁)

 

R1	=	B	C
		b1	c1
		b1	c2
		b2	c1

 

SQL: S ELECT DISTINCTROW B,C FROM R₁;

 

Дополнительные операции реляционной алгебры:

1. Пересечение: R=R₁ Ç R₂. Выражение через базисный набор: R=R₁ \ (R₁ \ R₂).

2. Соединение: R=R₁ ^►_F^◄ R₂, где F - логическое выражение над атрибутами из R₁ и R₂. Выражение через базисный набор: R=s_F(R₁ ´ R₂)

3. Эквисоединение. Частный случай соединения, когда F≡R₁.A_i=R₂.A_j.

4. Естественное соединение: R=R₁ ►◄ R₂. Каждый кортеж из R₁ сопоставляется с каждым кортежем из R₂. Два кортежа соединяются, если все одноименные атрибуты в них имеют одинаковое значение, результат соединения помещаются в R. Столбцы для одноименных атрибутов не дублируются, так как значение в этих столбцах совпадают. Пример:

 

R1	=	A	B	C		R2	=	B	C	D
		a1	b1	c1				b1	c1	d1
		a2	b1	c2				b2	c2	d1
		a3	b2	c2

 

Результат:

 

R	=	A	B	C	D
		a1	b1	c1	d1
		a3	b2	c2	d1

 

Выражение через базисный набор: R=p_X(s_F(R₁ ´ R₂)), где F=Ù_i=1,…,k(R₁.A_i=R₂.A_i) – конъюнкция по всем одноименным атрибутам, X= R₁ È R₂ – объединение атрибутов из R₁ и R₂.

 

Функциональные зависимости

Определение. Пусть задана схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, (возможно R – тип записи для структурированной модели данных). Пусть X и Y – некоторые подмножества из множества атрибутов U. Будем говорить, что X функционально определяет Y(X ® Y), если в любой реализации r схемы R не могут присутствовать два кортежа t,u Î r, такие что t[X]=u[X] и t[Y]¹u[Y].

Свойства функциональных зависимостей.

Дано: схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, F – множество функциональных зависимостей в R:

Рефлексивность. Если Y Í X Í U, то X ® Y.

Пополнение. Если X ® Y и Z Í U, то XZ ® YZ.

Транзитивность. Если X ® Y и Y ® Z, то X ® Z.

 

Определение. Пусть F – множество функциональных зависимостей, определенных на множестве атрибутов U = {A₁, A₂,..., An}. Тогда через F⁺ обозначим замыкание множества F, полученное из F за счет применения правила логического следствия.

 

Формальное определение первичного ключа

Дано: схема отношения R на совокупности атрибутов U = {A₁, A₂,..., An}, F – множество функциональных зависимостей в R. Множество X Í U, является первичным ключом для R, если выполнено:

1. X ® A₁,A₂,...,An Î F⁺;

2. Для любого Y Ì X (Y -истинное подмножество X) выполнено Y ® A₁,A₂,...,An Ï F⁺.

Замечание. Отношение R может содержать несколько первичных ключей.

 

Этапы построения схемы БД

 

Дано: схема отношения R, определенная на совокупности атрибутов U = {A₁, A₂,..., A_n}, F – минимальное покрытие множества функциональных зависимостей в R.

Шаг 1. Функциональные зависимости X ® A_i Î F, X ® A_j Î F …, имеющие одинаковые левые части и совпадающие области определения, объединяются в одну зависимость X ® A_iA_j … (по правилу объединения).

Шаг 2. Строим декомпозицию r(R₁, R₂,..,R_k), где R_i состоит из атрибутов зависимости F_i Î F.

Шаг 3. Для атрибутов, которые не входят ни в одну функциональную зависимость, строятся отдельные отношения, состоящее из одного атрибута.

Примечание 1. Изолированный атрибут является признаком неполноты множества функциональных зависимостей F и/или множества атрибутов U.

Примечание 2. Из способа построения R_i очевидно, что декомпозиция r сохраняет функциональные зависимости.

Примечание 3. Не гарантируется выполнение свойства соединения без потерь информации. Осуществляется проверка этого свойства по алгоритму. Если свойство выполнено - конец построения, если нет, то выполняем шаг 4.

Шаг 4. Строится обобщенный ключ W (первичный ключ для отношения R) и декомпозия r дополняется еще одним отношением X: r₁=rÈ{W}. Если отношение, соответствующее обобщенному ключу, является интерпретируемым и технологичным, то r₁ результат построения. В противном случае выполняется шаг 5.

Шаг 5. В обобщенном ключе W определяется многозначная зависимость X ®® Y(Z) (возможно их несколько), причем атрибуты X могут полностью или частично отсутствовать в W, и выполняется декомпозиция отношения W на отношения XY и XZ: r₂=rÈ{XY}È{XZ}. Чаще всего отношения {XY} и {XZ} уже содержатся в декомпозиции r, либо представимы через отношения в ней (тогда r₂=r), и r₂ обладает свойством соединения без потерь информации в рамках четвертой нормальной формы.

 

Многозначные зависимости. Дано: схема отношения R, определенная на совокупности атрибутов U = {A₁, A₂,..., A_n}, пусть X Í U, Y Í U и X Ç Y =Æ, Z=R \(X È Y).

Определение. Множество X мультиопределяет множество Y в контексте Z: X ®® Y(Z) (многозначная зависимость), если для произвольной реализации r схемы R существует два кортежа t₁,t₂ Î r таких, что t₁ [ X ] =t₂ [ X ], то существует кортеж t₃, для которого выполнено:

t₃ [ X ] =t₁ [ X ], t₃ [ Y ] =t₁ [ Y ], t₃ [ Z ] =t₂ [ Z ],

в силу симметрии существует кортеж t₄:

t₄ [ X ] =t₁ [ X ], t₄ [ Y ] =t₂ [ Y ], t₄ [ Z ] =t₁ [ Z ]

 

Обобщенный ключ: W – первичный ключ для отношения R, сформированного по всему множеству атрибутов U = {A₁, A₂,..., A_n}.

Введение дополнительного отношения (обобщенного ключа) может привести к следующим проблемам:

Совокупность атрибутов в W не обладает свойством однозначной семантической интерпретации: этому отношению нельзя присвоить однозначное имя. Решения:

а) выявляются потерянные функциональные зависимости на атрибутах W.

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

в) выявляется многозначная зависимость на атрибутах W и осуществляется декомпозиция отношения W.

Если отношение W оказалось интерпретируемым, то оно может быть не технологичным: на предприятии отсутствует служба, которая отвечала бы за сопровождение данных в этом отношении. Решение:

а) сформировать новую схему документооборота на предприятии;

б) придется признать, что на самом деле существует не одна, а несколько БД, они не могут быть интегрированы.

 

Физическая организация БД

 

Методы хеширования

 

Исходные данные для построения функции хеширования: интервал изменения ключа и приблизительное количество записей в основном файле. A=F(K), K – значение ключа, A – адрес записи. Основное требование к функции хеширования: квазиравномерное распределение значений величины A.

Определение. Два ключа K1 и K2 называются синонимами относительно функции хеширования F, если F(K1)=F(K2).

Второе требование к функции хеширования: как можно меньше синонимов.

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

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

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

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

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

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

 

Библиографический список

 

1. Мартин Дж. Организация баз данных в вычислительных системах. - М.: Мир, 1980. - 662 с.

2. Ульман Дж. Основы систем баз данных. - М.: Финансы и статистика, 1983. - 334 с.

3. Мейер Д. Теория реляционных баз данных. - М.: Мир, 1987. - 608 с.

4. Вейнеров О.М., Самохвалов Э.Н. Разработка САПР: В 10 кн. Кн. 4. Проектирование баз данных САПР. - М.: Высш. шк., 1990. - 144 с.

5. Дейт К. Введение в системы баз данных. - М.: Диалектика, 1998. - 782 с.

6. Солтон Дж. Динамические информационно-справочные системы. - М: Мир, 1979. - 557 с.

7. Тиори Т., Фрай Дж. Проектирование структур баз данных. - М.: Мир, 1985. Т 2. - 320 с.

8. Когаловский М.Р. Энциклопедия технологий баз данных. – М.: Финансы и статистика, 2002. – 800 с.

9. Кузин А.В. Базы данных: Учебное пособие. – М.: Academia, 2005. – 320 с.

10. Советов Б.Я., Цехановский В.В., Чертовской В.Д. Базы данных: теория и практика. – М.: Высшая школа, 2005. – 463 с.

11. Мирошниченко Г.А. Реляционные базы данных. Практические приемы оптимальных решений. – СПб.: BHV, 2005. – 400 с.

12. Диго С.М. Базы данных: проектирование и использование. – М.: Финансы и статистика, 2005. – 592 с.

13. Кузнецов С.Д. Основы баз данных. - М.: Интуит.ру, 2005. - 488 с.

14. Уидом Д., Ульман Дж.Д. Основы реляционных баз данных. – М.: Лори, 2006. – 374 с.

15. Мальцев М.Г., Хомоненко А.Д., Цыганков В.М. Базы данных. Учебник для вузов. – М.: КОРОНА, 2006. – 736 с.

Содержание

1. Введение в предмет «Базы данных»............................................................... 3

1.1. Основные определения и категории БД.................................................... 3

1.2. Требования к БД и методы их реализации............................................... 4

1.3. Принципы функционирования СУБД....................................................... 6

1.4. Языковые средства для работы с БД........................................................ 7

2. Логическое описание и проектирование БД................................................... 8

2.1. Элементы данных и связи.......................................................................... 8