Оптимизация схемы данных

Операции над таблицами.

В классической теории множеств объединение, пересечение и разность возможны для любых множеств. В реляционном исчислении операнды этих операций (то есть таблицы) должны быть совместимы: в заголовках обеих таблиц содержится один и тот же набор полей. Если две таблицы совместимы, то при обычном выполнении над ними операций объединения, пересечения и взятия разности результатом операции является таблица с корректно определенным заголовком, совпадающим с заголовком каждой из таблиц-операндов. Заметим, что включение в состав операций реляционного исчисления трех операций объединения, пересечения и взятия разности является избыточным, так как пересечение выражается через объединение и разность. Тем не менее, во все логические модели обычно включаются все три операции (исходя из интуитивных потребностей потенциального пользователя реляционых БД, далекого от математики).

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

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

По поводу теоретико-множественных операций следует еще заметить, что все четыре операции являются ассоциативными. Т.е., если обозначить через * любую из четырех операций, то (A*B)*C = A(B*C), и следовательно, корректно писать A*B*C. Также все операции, кроме взятия разности, являются коммутативными, т.е. A*B = B*A.

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

Второе требование называется требованием целостности по ссылкам и относится к связи таблиц. Если две таблицы связаны посредством двух полей, одно из которых служит в первой таблице полем первичного ключа, то любое значение связанного поля во второй таблице обязано встречаться в качестве значения первого поля в первой таблице либо быть полностью неопределенным (то есть Null). Поле такого рода во второй таблице принято называть внешним ключом. Говорят, что таблица, в которой определен внешний ключ, ссылается на соответствующую таблицу, в которой поле с тем же содержанием (но не обязательно с тем же названием) является первичным ключом.

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

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

Для изменения содержимого таблиц разрешены только следующие операции:

· добавить новую запись;

· удалить запись из таблицы;

· изменить поле таблицы.

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

В основе реляционного исчисления лежит небольшой список элементарных операторов:

· UNION - объединение таблиц с полностью одинаковым набором полей: таблица состоит из записей первой и второй таблицы. Количество строк в объединении равно сумме количества строк исходных таблиц.

· INTERSECT - пересечение таблиц с полностью одинаковым набором полей: таблица включает только одинаковые строки обеих таблиц.

· DIFFERENCE - вычитание таблиц с полностью одинаковым набором полей (как самостоятельная операция используется редко): таблица включает те строки первой таблицы, которых нет во второй таблице;

· PRODUCT - прямое (декартово) произведение двух таблиц: это таблица, столбцы которой состоят из объединения столбцов обеих таблиц, а строками служат всевозможные комбинации, состоящие из объединения одной из строк первой таблицы и одной из строк второй таблицы. Количество строк в прямом произведении равно произведению количества строк исходных таблиц.

· DIVIDE - деление двух таблиц (довольно искусственная и редко встречающаяся операция). Множество полей таблицы-делимого должно содержать множество полей таблицы-делителя. Результатом операции деления будет такая таблица, что ее прямое произведение с делителем содержится в делимом. В частности, ее поля представляют собой те поля делимого, которых нет в делителе.

· WHERE – операция ограничения: отобрать те записи исходной таблицы, которые удовлетворяют заданным условиям. Условием ограничения является логическое выражение, составленное из простых условий с использованием логических связок AND, OR и NOT и скобок. Простым условием служит сравнение значений полей или констант.

· PROJECT - проекция таблицы: оставить в таблице только заданные столбцы, отбросив все остальные.

· JOIN - соединение двух таблиц по их общим полям. Это сложная операция, которую можно представить в виде трех более простых операций. Сначала берется прямое произведение двух таблиц (операция PRODUCT). Затем производится выборка тех записей в полученной таблице, в которой значения одного или группы общих полей обеих таблиц одинаковые (операция SELECT). Теперь мы имеем таблицу, которая содержит два идентичных поля или две идентичные группы полей. Исправим это, исключив поле или целую группу из таблицы (операция PROJECT).

· GROUPE – группировка строк таблицы: группа строк с одинаковой комбинацией значений некоторого подмножества полей объединяется в одну строку, в которой эти поля принимают те же значения, а над прочими полями совершается какая-то групповая операция (сложение, среднее, минимум, максимум и т.п.).

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

· RENAME - Переименование поля таблицы.

F	G	H
	x	y
	z	w

A	B	C

Операция соединения (JOIN) требует пояснений. Пусть даны следующие две таблицы R и S, а соединение производится по совпадению полей C и F: R = S =

Тогда прямое произведение этих таблиц T = R * S представляет собой таблицу из шести строк:

A	B	C	F	G	H
1	2	3	3	X	y
1	2	3	6	Z	w
4	5	6	3	X	y
4	5	6	6	Z	W
7	8	9	3	X	Y
7	8	9	6	Z	W

После выборки строк таблицы T с одинаковым значением полей C и F получим таблицу Q с двумя строками:

A	B	C	F	G	H
1	2	3	3	X	Y
4	5	6	6	Z	W

Удалив из таблицы Q с помощью проекции повторяющееся поле F, имеем окончательный результат V = R JOIN S:

A	B	C	G	H
1	2	3	x	Y
4	5	6	z	W

Легко видеть, что операция соединения JOIN определена, когда зафиксирована связь между двумя таблицами посредством отождествления полей в обеих таблицах. Принято различать по типу связи «один-к-одному», «один-ко-многим», «многие-ко-многим». Тип связи задается семантикой отношений между группами объектов предметной области, описываемых таблицами.

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

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

При связи типа «многие-ко-многим» каждая запись в одной таблице может быть связана с несколькими записями в другой таблице и наоборот. Иллюстрацией такой связи может служить связь таблиц «Издательства» и «Авторы». С одной стороны, каждое издательство может публиковать книги разных авторов, с другой стороны - каждый автор может публиковаться в разных издательствах.

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

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

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

Более эффективной оказывается организация базы данных в форме двух таблиц. Первая, главная таблица содержит столбцы «Код устройства» и «Название устройства». Вторая, подчиненная таблица содержит список всех вхождений всех деталей в состав всех устройств. Она содержит столбцы «Код устройства», «Код детали», «Название детали» и «Количество деталей». Связь таблиц осуществляется с помощью полей «Код устройства» в обеих таблицах. При такой организации в состав устройства с кодом N входят все детали, которым в подчиненной таблице приписан код устройства N.

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

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

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

Таблицы из пары таблиц вида «Устройство – деталь» из первого примера или «Группа – студент» из второго примера называются главной и подчиненной таблицей. Возможны не только пары, но и тройки таблиц последовательного подчинения, например, для таблиц «Отделения» → «Группы» → «Студенты».

Говорят, что база данных удовлетворяет третьей нормальной форме, если невозможна ситуация, когда какое-то поле функционально зависит от группы других полей. То же самое по-другому можно выразить так: невозможна ситуация, когда для какой-то части полей в каждой группе записей с одинаковыми значениями этих полей значение проверяемого поля одинаковое. Отличие от второй нормальной формы в том, что сейчас не требуется, чтобы группа полей входила в состав первичного ключа. Например, если таблица товаров, проданных за день, содержит столбцы «Покупатель», «Код товара по каталогу», «Название товара», «Цена товара», «Количество», то поля «Название товара» и «Цена товара» определяются по полю «Код товара по каталогу» и повторяются во всех строках с одинаковым кодом товара. Данная таблица не удовлетворяет третьей нормальной форме.

Для того, чтобы нормализовать данную ситуацию, надо использовать две таблицы: таблицу проданных товаров со столбцами «Покупатель», «Код товара по каталогу», «Количество», и таблицу «Каталог товаров» со столбцами «Код товара по каталогу», «Название товара», «Цена товара». Эти таблицы надо связать по полю «Код товара по каталогу». Таблица «Каталог товаров» по отношению к полю «Код товара по каталогу» в таблице проданных товаров служит справочником, который позволяет определить название и цену товара по коду.

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

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

· Ввод пользователем большого количества повторяющейся информации неизбежно приведет к возникновению ошибок.

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

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

Для того, чтобы построить достаточно эффективную структуру данных, достаточно придерживаться нескольких простых правил:

· Определите таблицы таким образом, чтобы записи в каждой таблице описывали объекты одного и того же класса, например: товары, заказы, потребители.

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

· Не запоминайте в таблице данных, которые могут быть вычислены при помощи данных из других таблиц.

· Широко используйте справочники. Например, если в вашей таблице есть поле «Страна», то стоит ввести вспомогательную таблицу «Страны», которая будет содержать соответствующие записи (Россия, Украина, США и т.п.). Этот прием поможет уменьшить количество ошибок при вводе данных, допускаемых пользователями.

Как было отмечено выше при описании отношений между таблицами, в реляционных базах данных таблицы чаще всего связываются друг с другом посредством совпадающих значений полей, которые в одной из таблиц являются ключевыми. Ключевым полем может быть только такое поле таблицы, которое не повторяется в разных записях. Если связывающее поле в одной таблице является полем первичного (primary) ключа, то во второй таблице оно называется полем внешнего (foreign) ключа.

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

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

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

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

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

Дата добавления: 2014-10-17