Алгоритм декомпозиции основан на следующей теореме.
Теорема о декомпозиции . Пусть R(A, B, C) – отношение , A, B, C – атрибуты .
Если R удовлетворяет зависимости A->B , то R равно соединению его проекций A, B и A, C
R(A, B, C) = R(A, B), R(A, C)
При нормализации необходимо выбирать такие декомпозиции, которые обладают свойством соединения без потерь. В этом случае, декомпозиция должна обеспечить то, что запросы ( выборка данных по условию) к исходному отношению и отношениям, получаемым в результате декомпозиции, дадут одинаковый результат. Соответствующее условие будет выполняться, если каждый кортеж отношения R может быть представлен как естественное соединение его проекций на каждое из подмножеств. Для проверки, обладает ли декомпозиция данным свойством, используется специальные алгоритмы, описанные в литературе (в данной книге не рассматриваются).
Вторым важнейшим желательным свойством декомпозиции является свойство сохранения функциональных зависимостей. Стремление к тому, чтобы декомпозиция сохраняла зависимости, естественно. Функциональные зависимости являются некоторыми ограничениями на данные. Если декомпозиция не обладает этим свойством, то для того чтобы проверить, не нарушаются ли при вводе данных условия целостности ( функциональные зависимости ), нам приходится соединять все проекции.
Таким образом, для правильно построенного проекта базы данных необходимо, чтобы декомпозиции обладали свойством соединения без потерь, и желательно, чтобы они обладали свойством сохранения функциональных зависимостей.
Вторая нормальная форма (2НФ)
Отношение находится в 2НФ, если оно находится в 1НФ и каждый неключевой атрибут зависит от всего первичного ключа (не зависит от части ключа) .
Для перевода отношения в 2НФ необходимо, используя операцию проекции , разложить его на несколько отношений следующим образом:
Третья нормальная форма (3НФ)
Отношение находится в 3НФ, если оно находится в 2НФ и каждый ключевой атрибут нетранзитивно зависит от первичного ключа .
Отношение находится в 3НФ в том и только том случае, если все неключевые атрибуты отношения взаимно независимы и полностью зависят от первичного ключа .
Оказывается, что любая схема отношений может быть приведена к 3НФ декомпозицией, обладающей свойствами соединения без потерь и сохраняющей зависимости .
Мотивировка третьей нормальной формы
Третья нормальная форма исключает избыточность и аномалии включения и удаления .
К сожалению, 3НФ не предотвращает все возможные аномалии.
Нормальная форма Бойса-Кодда (НФБК)
Если в R для каждой зависимости X->A , где А не принадлежит X, X включает в себя некоторый ключ, то говорят, что данное отношение находится в нормальной форме Бойса-Кодда .
Детерминантом функциональной зависимости называется минимальная группа атрибутов, от которой зависит некоторый другой атрибут или группа атрибутов, причем эта зависимость нетривиальная .
Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом .
НФБК является более строгой версией 3НФ. Иными словами, любое отношение, находящееся в НФБК, находится в 3НФ. Обратное неверно .
Мотивировка нормальной формы Бойса-Кодда
В нормальной форме Бойса-Кодда не существует избыточности и аномалий включения, удаления и модификации . Оказывается, что любая схема отношения может быть приведена в нормальную форму Бойса-Кодда таким образом, чтобы декомпозиция обладала свойством соединения без потерь. Однако схема отношения может быть неприводимой в НФБК с сохранением зависимостей. В этом случае приходится довольствоваться третьей нормальной формой .
Для улучшения структуры реляционной базы данных (устранения возможных аномалий) необходимо привести все таблицы базы данных к третьей нормальной форме или в более высокой форме (если это возможно). Таким образом, задача сводится к проверке нормализации всех сущностей, отображающихся в таблицы базы данных . Если таблица , получающаяся из некоторой сущности, не является таблицей в третьей нормальной форме , то она должна быть заменена на несколько таблиц, находящихся в третьей нормальной форме .
Продолжим рассмотрение примера с отношением ЭКЗАМЕНАЦИОННАЯ ВЕДОМОСТЬ
В начале этой лекции мы привели отношение к первой нормальной форме .
| Код студента | Фамилия | Код экзамена | Предмет | Дата | Оценка |
|---|---|---|---|---|---|
| 1 | Сергеев | 1 | Математика | 5.08.03 | 4 |
| 2 | Иванов | 1 | Математика | 5.08.03 | 5 |
| 1 | Сергеев | 2 | Физика | 9.08.03 | 5 |
| 2 | Иванов | 2 | Физика | 9.08.03 | 5 |
Ключом данного отношения будет совокупность атрибутов – Код студента и Код экзамена.
Для более краткой записи процесса нормализации введем следующие обозначения:
КС – код студента, КЭ – код экзамена, Ф – фамилия, П – предмет, Д – дата, О - оценка.
Выпишем функциональные зависимости
КС, КЭ -> Ф, П, Д, О КС, КЭ -> Ф КС, КЭ -> П КС, КЭ -> Д КС, КЭ -> О КЭ -> П КЭ -> Д КС -> Ф
В соответствии с определением, отношение находится во второй нормальной форме (2НФ), если оно находясь в 1НФ и каждый неключевой атрибут зависит от первичного ключа и не зависит от части ключа. Здесь атрибуты П, Д, Ф зависят от части ключа. Чтобы избавиться от этих зависимостей необходимо произвести декомпозицию отношения. Для этого используем теорему о декомпозиции.
Имеем отношение R(КС, Ф, КЭ, П, Д, О) . Возьмем зависимость КС -> Ф в соответствии с формулировкой теоремы исходное отношение равно соединению его проекций R1(КС, Ф) и R2(КС, КЭ, П, Д, О) .
В отношении R1(КС, Ф) существует функциональная зависимость КС -> Ф , ключ КС – составной, не ключевой атрибут Ф не зависит от части ключа. Это отношение находится в 2НФ. Так как в этом отношении нет транзитивных зависимостей, отношение R(КС, Ф) находится в 3НФ, что и требовалось.
Рассмотрим отношение R2(КС, КЭ, П, Д, О) с составным ключом КС, КЭ . Здесь есть зависимость КЭ -> П, КЭ -> Д, КЭ -> П, Д . Атрибуты П,Д зависят от части ключа, следовательно
Декомпозиция схем отношений
Одним из способов приведения произвольного отношения к виду нормальных форм (кроме 1 НФ) является декомпозиция отношений.
· Декомпозицией схемы отношений R называется замена ее совокупностью схем r=(R 1 , R 2 , ... , R K), где R i Ì R и R i такие, что R 1 ÈR 2 È... ÈR K = R, при этом не требуется, чтобы R i Ç R j =Æ, хотя и допустимо.
Осуществление декомпозиции приводит к тому, что вновь получаемое отношение будет проекциями исходного отношения на новые схемы отношений из множества r.
Прежде чем выполнить декомпозицию необходимо убедиться, что соединение новых отношений даст исходное отношение.
Проектирование БД включает в себя построение концептуальной и логической схем, а также решение ряда проблем, наиболее важной из которых является проблема, связанная с отображением и корректным поддержанием семантической БД (проблема целостности).
Проблема целостности связана с обеспечением надежности данных в условиях возможных аварийных ситуаций и рационального использования вычислительных ресурсов для обеспечения высокой эффективности взаимодействия с БД.. Эффективность подразумевает обеспечение необходимого объема хранения информации и времени взаимодействия с БД.
Целостность в БД отражается путем построения логической схемы.
Логическая схема выражается в терминах объектов или сущностей и связей между ними. Связи также можно трактовать как объекты иной природы и в этом плане и сущности и связи в реляционных моделях выражаются одинаково в виде отношений. В этом случае говорят об объектах - сущностях и объектах - связей. Совокупность отношений, составляющих БД и зависящих друг от друга, отражает семантику (смысл) данных в предметной области.
· Если состояние БД не соответствует семантике связей между данными, то такое явление называют нарушением целостности данных или БД.
Для обеспечения целостности данных необходимо обеспечивать целостность объектов и целостность ссылок на эти объекты. Кроме того, объекты в БД должны быть уникальными (неповторяющимися) и распознаваемыми, а также ссылки на объекты не должны существовать без объектов.
Кроме естественных ограничений, не зависящих от конкретного приложения, целостность БД определяется ограничениями, связанными с конкретным приложением. ограничения такого рода называют ограничениями целостности приложений . Они выражаются в виде набора утверждений, фиксирующих способ использования данных в конкретной предметной области.
Ограничения приложений делятся на:
Статические ограничения и ограничения перехода;
Ограничения для кортежей и множеств;
Отложенные и безотлагательные ограничения целостности.
· Статические ограничения - те ограничения, которые выполняются независимо от состояния БД.
· Ограничения, устанавливаемые между старым и новым значением атрибута, называется ограничениями перехода.
Пример : при обновлении значения атрибута “давление” новое значение не должно отличаться от старого более чем на 20 %.
· Ограничения для кортежей - те ограничения, для которых проверку их выполнения осуществляют, используя только один кортеж отношения.
· Частным случаем такого ограничения является ограничение атрибута.
· Ограничение для множеств - если они представляют собой ограничение на некоторое итоговое значение, полученное в результате использования совокупности кортежей.
Пример : при измерении температуры очередное значение не должно отличаться от скользящего среднего Mx (текущего математического ожидания) на некоторую величину e. Все значения не попавшие в диапазон [ M x - e, M x + e] отбрасывают.
· Безотлагательными ограничениями называются те, которые допускают возможные проверки их выполнения одновременно с изменением значений данных в отношении.
· Отложенными ограничениями называют такие ограничения, для которых проверка их выполнения имеет смысл по окончании выполнения очередной совокупности операций.
Для отложенного ограничения имеет значение следующее понятие:
· Логический элемент работы - непрерывное управление данными, при котором БД из одного целостного состояния переводится в другое целостное состояние. Этот прием еще называют транзакцией.
Понятие транзакции тесно связано с надежностью данных. При выполнении транзакции могут происходить аппаратные или программные сбои. Если транзакция в результате сбоев не доведена до конца, то целостность БД нарушается. Для обеспечения целостности БД при отложенных ограничениях используют методы отката. Их суть состоит в том, что начатая, но незавершенная транзакция аннулируется, при этом БД переводится в исходное состояние, с которого начиналась транзакция (таким образом происходит откат).
Аксиома рефлективности . ЕслиY входит вX , аX входит вU , (Y X U ), тоX Y логически следует изF . Это правило дает тривиальные зависимости, так как в этих зависимостях правая часть содержится в левой части.
Аксиома пополнения . ЕслиX Y иZ есть подмножествоU , тоXZ YZ . В данном случае функциональная зависимостьX Y либо содержалась в исходном множествеF , либо может быть выведена изF с использованием описываемых аксиом.
Аксиома транзитивности. Если X Y и Y Z , то X Z .
Справедлива следующая теорема . Аксиомы Армстронга являются полными и надежными.
Это значит, что используя их, мы выведем все возможные функциональные зависимости, логически следующие из F , и не выведем никаких лишних зависимостей.
Существует несколько других правил вывода, которые следуют из
аксиом Армстронга. | |||||
Правило самоопределения. X | |||||
Правило объединения. Если X | Y и X | Z , тоX | Y Z. | ||
Правило псевдотранзитивности. Если X | Y и | Z , то |
|||
X W Z. | |||||
Правило композиции. Если X | Y и Z | W , тоX W | Y W. |
||
Правило декомпозиции. Если X | Y иZ входит вY , тоX | ||||
Надо отметить, что вычисление замыкания множества функциональных зависимостей является трудоемкой задачей при достаточно большом количестве атрибутов (за счет выписывания большого количества тривиальных зависимостей).
Последовательный переход от одной нормальной формы к другой при нормализации схем отношений осуществляется с помощью декомпозиции. Основной операцией, с помощью которой осуществляется декомпозиция, является проекция.
Декомпозицией схемы отношения R = {А 1 , А 2 ,…А n } называется замена ее совокупностью подмножествR , таких, что их объединение даетR . При этом допускается, чтобы подмножества были пересекающимися.
Декомпозиция должна обеспечить то, что запросы (выборка данных по условию) к исходному отношению и отношениям, получаемым в результате декомпозиции дадут одинаковый результат. Соот-
ветствующее условие будет выполняться, если каждый кортеж отношения R может быть представлен как естественное соединение его проекций на каждое из подмножеств. В этом случае говорят, что декомпозиция обладает свойством соединения без потерь.
Алгоритм декомпозиции основан на следующей теореме. Теорема Фейджина. ПустьR (A, B, C ) отношение,A, B, C – атри-
Если R удовлетворяет зависимостиA B , тоR равно соединению его проекцийA, B иA, C
R(A, B, C) | R(A, B) |
R(A, C) |
При нормализации необходимо выбирать такие декомпозиции, которые обладают свойством соединения без потерь. Для проверки, обладает ли декомпозиция данным свойством используется специальный алгоритм проверки . Алгоритм состоит в следующем.
Пусть есть некоторая схема отношения R = A 1 …A n , множество функциональных зависимостейF и некоторая декомпозиция(R 1 ,…R k ) исходной схемы, состоящая изk подсхем.
Необходимо построить таблицу с n столбцами иk строками. Столбецj соответствует атрибутуA j , строкаk схеме отношенияR k . На пересечении строкиi и столбцаj поместим символa j , еслиА j принадлежитR i . В противном случае поместим туда символb ij .
Рассматриваем каждую зависимость из множества F до тех пор, пока в таблице невозможно сделать какие-либо изменения. Всякий раз, рассматривая зависимостьX Y , мы ищем строки, которые совпадают по всем столбцам, соответствующим атрибутам изX . При обнаружении таких строк, отождествляем символы в столбцах, соответствующих атрибутам изY . Если при этом один из отождествляемых символов равенa j , то приравниваем и другойa j . В том случае, когда они равныb ij иb lj , делаем их оба равнымиb ij илиb lj по своему усмотрению.
После модификации строк таблицы указанным выше способом может обнаружиться, что некоторая строка стала равной a 1 …a k . Тогда декомпозиция обладает свойством соединения без потерь. Если такой строки не получается, то декомпозиция не обладает таким свойством.
Декомпозиция схемы ABCD наAB иACD .
A B ,AC D (AC – сокращенная записьА С ).
Так как одна строка состоит из всех a, то мы наша декомпозиция обладает свойством соединения без потерь.
Вторым важнейшим желательным свойством декомпозиции является свойство сохранения функциональных зависимостей.
Стремление к тому, чтобы декомпозиция сохраняла зависимости, является естественным. Функциональные зависимости являются некоторыми ограничениями на данные. Если декомпозиция не обладает данным свойством, то для того чтобы проверить, не нарушают ли введенные данные условия целостности (функциональные зависимости), нам приходится соединять все проекции.
Таким образом, для правильно построенного проекта базы данных необходимо, чтобы декомпозиции обладали свойством соединения без потерь и желательно, чтобы они обладали свойством сохранения функциональных зависимостей.
4.4.4. Выбор рационального набора схем отношений путем нормализации
Отношение находится в 2НФ, если оно находится в 1НФ и каждый неключевой атрибут зависит от первичного ключа (не зависит от части ключа).
Для перевода отношения в 2НФ необходимо, используя операцию проекции, разложить его на несколько отношений следующим образом:
1) построить проекцию без атрибутов, находящихся в частичной функциональной зависимости от первичного ключа;
2) построить проекции на части составного ключа и атрибуты, зависящие от этих частей.
Отношение находится в 3НФ если оно находится во 2НФ и каждый ключевой атрибут нетранзитивно зависит от первичного ключа.
Отношение находится в 3НФ в том и только том случае, если все неключевые атрибуты отношения взаимно независимы и полностью зависят от первичного ключа.
Оказывается, что любая схема отношений может быть приведена к 3НФ декомпозицией, обладающей свойствами соединения без потерь и сохраняющей зависимости.
Третья нормальная форма исключает избыточность и аномалии включения и удаления. К сожалению, 3НФ не предотвращает все возможные аномалии.
Если в R для каждой зависимостиX A , гдеА не принадлежитX ,X включает в себя некоторый ключ, то говорят, что данное отношение находится в нормальной форме Бойса-Кодда.
Детерминантом функциональной зависимости называется минимальная группа атрибутов, от которой зависит некоторый другой атрибут или группа атрибутов, причем эта зависимость нетривиальная.
Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом.
НФБК является более строгой версией 3НФ. Иными словами любое отношение, находящееся в НФБК, находится в 3НФ. Обратное неверно.
Пример. Расписание консультаций. Каждая группа может прийти на консультацию один раз в день. Для проведения консультации или консультаций преподавателю на определенный день предоставляется аудитория. В течение дня данная аудитория может использоваться разными преподавателями.
РАСПИСАНИЕ КОНСУЛЬТАЦИЙ (Группа, Дата, Время, Преподаватель, Аудитория)
В качестве первичного ключа выбрали «Группа, Дата». Потенциальные ключи:
«Группа, Дата». «Преподаватель, Дата, Время». «Аудитория, Дата, Время».
Преподаватель | Аудитория |
|||
Визгунов | ||||
Визгунов | ||||
Трифонов | ||||
Визгунов |
Сегодня, в эпоху быстро меняющегося цифрового мира оставаться в темпе событий сложно. Чтобы успеть все, необходимо правильно ставить задачи, цели, распределять и делегировать полномочия. Логика и анализ - лучшие помощники в решении сложных задач. Одним из инструментов логического построения является декомпозиция. Рассмотрим ее подробно.
В общем значении декомпозиция - это расчленение целого на составляющие. Это довольно простой и понятный прием, который помогает ежедневно решать сложные задачи, представляя их в виде суммы частей. В системе логических построений декомпозиция - это научный прием, решающий крупную задачу путем замены её несколькими маленькими и более простыми задачами.
Как правило, декомпозиция проводится при помощи «дерева проблем», «дерева целей», «дерева решений», «дерева работ», при построении которых образуется четкая иерархичная структура, включающая вертикальное и горизонтальное подчинения и обратные связи.
Основа любой декомпозиции - это структурное подчинение всем правилам метода. Из основополагающих и регулирующих всю систему правил можно выделить следующие:
1) Всегда должна быть соблюдена уровневая система.
Метод декомпозиции основан на подчинении более низкого уровня более высокому. Это достигается путем построения иерархической структуры с помощью так называемых «деревьев».
Первыми принято строить дерево проблем и дерево целей, чтобы четко и наглядно представлять все задачи, которые имеются на данный момент. При этом подчинение должно выглядеть таким образом, чтобы задачи более низкого уровня раскрывали суть задач более высокого уровня, а все подзадачи представляли собой проект целиком. Понимание точной и полной картины процентного выполнения декомпозиционного проекта приходит только тогда, когда дерево целей заполнено на 100 %.
Руководствуясь простой формальной алгеброй и логикой можно также строить «деревья И» и «деревья ИЛИ».
2) Расчленение целого на части должно происходить только по одному признаку.
Данный принцип подразумевает, что все подзадачи будут подчинены единой идее и цели. В качестве примера декомпозиции может выступать проект строительства. В качестве главного признака разбиения принят функциональный признак, то проект разбивается на разделы. К примеру, это могут быть следующие основные разделы: конструкции железобетонные (КЖ), архитектурные решения (АР), конструкции металлические (КМ), отопление и вентиляция (ОВ) и т.д. В свою очередь эти разделы тоже должны быть разбиты по функциональному признаку, то есть в подцелях следующего уровня должна быть представлена суть основных целей. Например, раздел отопление и вентиляция (ОВ) делится на пояснительную записку, чертежи, оформление, прохождение нормоконтроля и технического контроля, выпуск документации, авторский надзора, корректировки согласно замечаниям и пр.
В качестве признака можно использовать также временные рамки (сроки), предметные характеристики, структурные признаки, технологические характеристики и другие.
3) Все подсистемы декомпозиции должны раскрывать суть системы.
Если представить главную задачу в качестве 100 %, то все подзадачи должны составить эти же 100% в сумме. При этом, каждая подзадача первого уровня содержит свой процентаж, представляя собой сумму подзадач второго уровня.
Важно понимать, что все разделённые подзадачи одного уровня должны быть независимы друг от друга, в то время как иерархия задач по одной ветке должна основываться на принципе зависимости и обратной связи: задача более высокого уровня зависит от своей подзадачи, и наоборот.
4) Глубина декомпозиционной проработки должна быть определена на начальном этапе.
Перед тем как создавать иерархическую структуру, необходимо определиться, какой будет последний уровень подзадач. В некоторых случаях не обязательно создавать много уровней, так как целью декомпозиции является наглядность. В случае же, когда иерархия создается для точных калькуляций, число уровней должно быть таким, чтобы максимально подробно раскрыть тему.
На сегодняшний день известно несколько видов декомпозиции. Можно создавать и свои приемы для конкретного проекта. Однако в той или иной мере они будут относиться к основным видам, а именно: декомпозиция целей (первый и фундаментальный вид), систем (процесс разбивания системы на подсистемы с целью проработки и получения лучшего результата), процесса, работ (составление иерархии работ для обозначение слабых точек и выделения главного и первостепенного).
Как правило, все перечисленные процессы взаимосвязаны и в целом представляют полную декомпозиционную структуру.
Для начала работы составляется дерево проблем и дерево целей. Дерево проблем - это главное проблемы, разбитая на проблемы второго и третьего уровня. В таком виде их становится куда проще решать. После подробного анализа проблем составляется дерево целей, которое представляет собой разрешенное дерево проблем. То есть на каждую проблему предлагается решение. При этом сохраняется уже готовая структура и взаимозависимости подзадач.
Декомпозиция работ - это логическое построение, которое начинается, когда обозначены все цели и проблемы и представляет собой иерархическую структуру всех действий, которые необходимо провести для решения той или иной задачи.
Такая логическая схема позволяет выявить те этапы работ, на которых возникли проблемы. Так как подзадачи зависят от задач высокого уровня, то дерево работ позволяет увидеть, где есть проблемы и недоработки. Часто из-за слабых мест в первом уровне декомпозиции страдают работы на более низких уровнях.
Например, если закупщик не подал заявку на саморезы, то бухгалтерия не провела счета и не закупила их. На стройке все стоит, потому что монтажникам не хватает для работы саморезов.
Для проведения более подробного анализа структур, выявления их слабых мест, основных целей и направлений, задач, проектов и работ выполняется декомпозиция систем.
Система разбивается как горизонтально, так и вертикально на уровни. Они должны формировать общую картину структуры. Декомпозиция систем - это общий пример иерархии для любого вида декомпозиции.
Для описания и анализа деятельности компаний, как правило, используется декомпозиция процесса. С помощью иерархии можно определить болевые точки компании, участки, на которых происходят сбои.
Процессы сводятся в общую схему и анализируются, после чего составляется подробный отчет о деятельности компании.
В качестве примера рассмотрим проект строительства объекта капстроительства. Разработка осуществляется в 2 стадии: рабочая документация и проектная документация. Это будут подзадачи первого уровня. На работы будут представлены сметными проработками и проектами. На рабочей стадии так же. Это подзадачи второго уровня. К примеру, проект обычно представлен в виде следующих частей:
Разделы и подразделы проектной и рабочей документации - это подзадачи третьего уровня.
Каждый раздел состоит из определенных этапов и должен содержать информацию согласно государственным стандартам. Например, раздел решения обязательно включает текстовую часть с подробным описанием технологической схемы и принятого оборудования, графическую часть (планы, разрезы, схемы), ведомость оборудования, выезды на объект, прохождение нормоконтроля и технического контроля, выпуск документации.
На каждом уровне назначаются ответственные исполнители, с которых потом требуется результат. В данном примере декомпозиции исполнители первого уровня - это руководитель проектного отдела, второго - третьего - инженеры-проектировщики.
Декомпозиция - это метод формальной практической логики предполагающий качественную проработку главной задачи согласно основной Такой подход обеспечивает вовлечение персонала всех уровней для решения многоуровневых задач. Это позволяет вести проект наиболее эффективно, с наименьшими финансовыми вложениями и трудозатратами.
В нормальной форме Бойса-Кодда не существует избыточности и аномалий включения, удаления и модификации . Оказывается, что любая схема отношения может быть приведена в нормальную форму Бойса-Кодда таким образом, чтобы декомпозиция обладала свойством соединения без потерь. Однако схема отношения может быть неприводимой в НФБК с сохранением зависимостей. В этом случае приходится довольствоваться третьей нормальной формой.
8.5. Пример нормализации до 3НФ
Для улучшения структуры реляционной базы данных (устранения возможных аномалий) необходимо привести все таблицы базы данных к третьей нормальной форме или в более высокой форме (если это возможно). Таким образом, задача сводится к проверке нормализации всех сущностей, отображающихся в таблицы базы данных. Если таблица, получающаяся из некоторой сущности, не является таблицей в третьей нормальной форме, то она должна быть заменена на несколько таблиц, находящихся в третьей нормальной форме.
Продолжим рассмотрение примера с отношением ЭКЗАМЕНАЦИОННАЯ ВЕДОМОСТЬ
В начале этой лекции мы привели отношение к первой нормальной форме.
Ключом данного отношения будет совокупность атрибутов – Код студента и Код экзамена.
Для более краткой записи процесса нормальзации введем следующие обозначения:
КС – код студента, КЭ – код экзамена, Ф – фамилия, П – предмет, Д – дата, О-оценка.
Выпишем функциональные зависимости
КС, КЭ à Ф, П, Д, О
КС, КЭ à Ф
КС, КЭ à П
КС, КЭ à Д
КС, КЭ à О
В соответствии с определением, отношение находится во второй нормальной форме (2НФ), если оно находтяс в 1НФ и каждый неключевой атрибут зависит от первичного ключа и не зависит от части ключа. Здесь атрибуты П, Д, Ф зависят от части ключа. чобы избавиться от этих зависимостей необходимо произвести декомпозицию отношения. Для этого используем теорему о декомпозиции.
Имеем отношение R (КС, Ф, КЭ, П, Д, О). Возьмем зависимость КС à Ф в соответствии с формулировкой теоремы исходное отношение равно соединению его проекций R 1(КС, Ф) и R 2(КС, КЭ, П, Д, О).
В отношении R 1(КС, Ф) существует функциональная зависимость КС à Ф, ключ КС – составной не ключевой атрибут Ф не зависит от части ключа. Это отношение находтся в 2 НФ. Так как в этом отношении нет транзитивных зависимостей, отношение R (КС, Ф) находится в 3НФ, что и требовалось.
Рассмотрим отношение R 2(КС, КЭ, П, Д, О) с составным ключом КС, КЭ. Здесь есть зависимость КЭ à П, КЭ à Д, КЭ à П, Д. Атрибуты П,Д зависят от части ключа, следовательно отношение не находится в 2НФ. В соответствии с теоремой о декомпозиции исходное отношение (используем функциональную зависимость КЭ à П, Д) равно соединению проекций R 3(КЭ, П, Д), R 4(КС, КЭ, О). В отношении R 3(КЭ, П, Д) существуют функциональные зависимости КЭ à П, КЭ à Д, КЭ à П, Д. Зависимости неключевых атрибутов от части ключа нет, следовательно отношение находится в 2НФ. Транзитивных зависимостей в этом отношении так же нет, следовательно отношение находится в 3НФ.
Таким образом, исходное отношение приведено в к трем отношениям, каждое из которых находится в третьей нормальной форме R 1(КС, Ф), R 3(КЭ, П, Д), R 4(КС, КЭ, О).
Заметим, что в отношении R 4 атрибуты КС, КЭ являются внешними ключами, используемыми для установления связей с другими отношениями. Представим полученную модель в виде диаграммы объектов-связей (ER-диаграммы). Для наглядности и возможности последующего программирования перейдем к английским названиям объектов (отношений) и атрибутов.
Отношение R 1 представляет объект student с атрибутами id_st (первичный ключ), surname.
Отношение R 3 представляет объект exam_st c атрибутами id_ex (первичный ключ), subject, date.
Отношение R 4 представляет объект mark_st c атрибутами id_st (внешний ключ), id_ex (внешний ключ), mark. Первичный ключ здесь id_st, id_ex.
Соответствующая ER-диаграмма изображена на рис. 8.1.
Рис. 8.1. ER-диаграмма, представляющая рассмотренный фрагмент предметной области.
8.6. Целостная часть реляционной модели.
Реализация условия целостности данных в современных СУБД
Напомним, что под целостностью базы данных понимается то, что в ней содержится полная, непротиворечивая и адекватно отражающая предметную часть (правильная) информация. Поддержка целостности в реляционных БД основана на выполнении следующих требований.
1. Первое требование называется требованием целостности сущностей . Объекту или сущности реального мира в реляционных БД соответствуют кортежи отношений. Конкретно требование состоит в том, что любой кортеж любого отношения отличим от любого другого кортежа этого отношения, т.е., другими словами, любое отношение должно обладать определенным первичным ключом. Это требование автоматически удовлетворяется, если в системе не нарушаются базовые свойства отношений.
2. Второе требование называется требованием целостности по ссылкам . Очевидно, что при соблюдении нормализованности отношений сложные сущности реального мира представляются в реляционной БД в виде нескольких кортежей нескольких отношений. Связь между отношениями осуществляется с помощью миграции ключа.
Пример внешнего ключа.
СТУДЕНТ (Код студента, Фамилия) сдает ЭКЗАМЕН (Код студента, Предмет, Оценка).
Атрибут Код студента сущности ЭКЗАМЕН называется внешним ключом , поскольку его значения однозначно характеризуют сущности, представленные кортежами некоторого другого отношения – отношения Студент (мы предполагаем, что поле Код студента является ключом отношения Студент).
Говорят, что отношение, в котором определен внешний ключ, ссылается на соответствующее отношение, в котором такой же атрибут является первичным ключом.
Требование целостности по ссылкам или требование внешнего ключа состоит в том, что для каждого значения внешнего ключа в ссылающемся отношении в отношении, на которое ведет ссылка, должен найтись кортеж с таким же значением первичного ключа либо значение внешнего ключа должно быть неопределенным (т.е. ни на что не указывать).
Ограничения целостности сущности и по ссылкам должны поддерживаться СУБД. Для соблюдения целостности сущности достаточно гарантировать отсутствие в любом отношении кортежей с одним и тем же значением первичного ключа. (В Access для этого предназначена специальная реализация целочисленного поля – поле типа «Счетчик».) С целостностью по ссылкам дела обстоят несколько более сложно.
Понятно, что при обновлении ссылающегося отношения (вставке новых кортежей или модификации значения внешнего ключа в существующих кортежах) достаточно следить за тем, чтобы не появлялись некорректные значения внешнего ключа.
Но как быть при удалении кортежа из отношения, на которое ведет ссылка?
Здесь существуют три подхода, каждый из которых поддерживает целостность по ссылкам. Первый подход заключается в том, что запрещается производить удаление кортежа, на который существуют ссылки (т.е. сначала нужно либо удалить ссылающиеся кортежи, либо соответствующим образом изменить значения их внешнего ключа). При втором подходе при удалении кортежа, на который имеются ссылки, во всех ссылающихся кортежах значение внешнего ключа автоматически становится неопределенным. Наконец, третий подход (каскадное удаление) состоит в том, что при удалении кортежа из отношения, на которое ведет ссылка, из ссылающегося отношения автоматически удаляются все ссылающиеся кортежи.
В развитых реляционных СУБД обычно можно выбрать способ поддержания целостности по ссылкам для каждой отдельной ситуации определения внешнего ключа. Конечно, для принятия такого решения необходимо анализировать требования конкретной прикладной области.
Заметим, что все современные СУБД поддерживают и целостность сущностей, и целостность по ссылкам, но позволяют пользователям выключать данные ограничения и, таким образом, строить базы данных, не соответствующие реляционной модели. Опыт показывает, что отход от основных положений реляционной модели приводит к краткосрочному выигрышу – алгоритмы становятся проще, но впоследствии серьезно усложняют задачу, особенно ее сопровождение.
Краткие итоги: Лекция посвящена вопросам оптимизации схем отношений (структуры реляционной базы данных) на основе формальных методов теории реляционных баз данных. Здесь рассматривается ряд необходимых для этого понятий (функциональная зависимость, нормальные формы, декомпозиция схем отношений). Разбирается пример приведения таблицы к третьей нормальной форме, оптимальной по ряду показателей (исключающей избыточность, аномалии включения и удаления). Рассматриваются вопросы реализации целостности данных в реляциионных СУБД.
В лекции рассматриваются вопросы использование формального аппарата для оптимизации схем отношений. Сформулирована проблема выбора рациональных схем отношений и пути реализации такого выбора путем нормализации (последовательного преобразования схемы отношения в ряд нормальных форм). Для формального описания соответствующего процесса определены понятие функциональной зависимости (зависимости между атрибутами отношения), ключа, сформулированы правила вывода множества функциональных зависимостей, понятие декомпозиции схемы отношения. Определены первая, вторая, третья нормальные формы и нормальная форма Бойса-Кодда. Приведен пример нормализации до 3НФ. Рассмотрены вопросы реализации условий целостности данных в реляционных СУБД.
Вопросы настоящей лекции рассматриваются в .
Контрольные тесты
Задача 1. В чем состоит задача выбора рациональных схем отношений?
Вариант 1.
Какие проблемы устраняются за счет выбора рациональных схем отношений?
ð+ дублирование
ð+ потенциальная противоречивость
ð+ потенциальная возможность потери сведений
ð+ потенциальная возможность не включения информации в базу данных
ð увеличение количества схем отношений
Вариант 2.
С чем связано основное дублирование информации в реляционной базе данных?
ð с повторением одинаковых строк в одной таблице
ð с повторением одинаковых столбцов в одной таблице
ð+ с повторением одинаковых значений атрибутов в одной таблице
ð с повторением одинаковых значений атрибута в разных таблицах
Вариант 3.
Какие аномалии необходимо устранить при проектировании реляционной базы данных?
ð создания
ð+ удаления
ð+ обновления
ð+ включения
ð выключения
Задача 2. Как механизм используется для выбора рациональных схем отношений?
Вариант 1.
Как осуществляется выбор рациональных схем отношений?
ð+ путем нормализации
ð+ путем последовательного преобразования отношений к ряду нормальных форм
ð путем объединения схем отношений
ð+ путем декомпозиции схем отношений
Вариант 2.
Что такое нормализация?
ð+ последовательное преобразование отношений к ряду нормальных форм
ð определенное объединение схем отношений
ð+ определенная декомпозиция схем отношений
ð преобразование отношений с использованием операций реляционной алгебры
Вариант 3.
Что такое первая нормальная форма?
ð+ значения всех атрибутов отношения являются простыми
ð+ значения всех атрибутов отношения являются неделимыми
ð+ значения всех атрибутов отношения являются атомарными
ð значения всех атрибутов отношения являются кортежами
ð значения некоторых атрибутов отношения являются атомарными
ð значения некоторых атрибутов отношения являются кортежами
Задача 3. Дать характеристику функциональных зависимостей.
Вариант 1.
Что такое X функционально определяет Y ?
ð+ каждое значение множества X Y
ð+ X Y
ð Y является функцией X
ð Y зависит от X
ð каждое значение множества Y связано с одним значением множества X
ð если два кортежа совпадают по значениям Y , то они совпадают по значениям X
Вариант 2.
Что характеризуют функциональные зависимости?
ð схему отношения
ð+ все возможные значения отношения
ð+ все возможные значения строк отношения
ð+ отношение как переменную
Вариант 3.
Как можно использовать функциональные зависимости для защиты логической целостности базы данных?
ð+ как ограничения целостности
ð+ для проверки выполнения функциональной зависимости при обновлении данных
ð для проверки правильности работы прикладных программ
ð для автоматизированного формирования соответствующих данных
Задача 4. Как осуществляется нормализация схем отношений?
Вариант 1.
Что такое декомпозиция схемы отношения?
ð замена схемы отношения R = {А 1 , А 2 , …А n } совокупностью подмножеств R : R 1, R 2 таких, что R = R 1 Ç R 2
ð+ замена схемы отношения R = {А 1 , А 2 , …А n } совокупностью подмножеств R : R 1, R 2 таких, что R = R 1 È R 2
ð замена схемы отношения R = {А 1 , А 2 , …А n }совокупностью подмножеств R : R 1, R 2 таких, что R = R 1 ´ R 2
ð замена схемы отношения R = {А 1 , А 2 , …А n }совокупностью подмножеств R : R 1, R 2 таких, что R = R 1 + R 2
Вариант 2.
Как формулируется теорема о декомпозиции?
ð+ если R (A, B, C ) удовлетворяет зависимости A àB , то R равно соединению проекций
R (A, B ), R (A, C )
ð если R (A, B, C ) удовлетворяет зависимости A àB , то R равно соединению проекций
R (A, B ), R (B, C )
ð если R (A, B, C ) удовлетворяет зависимости A àB , то R равно соединению проекций
R (A, C ), R (B, C )
ð+ если R (A, B, C ) удовлетворяет зависимости A àB , то R равно соединению проекций
R (A, C ), R (A, B )
Вариант 3.
Какими свойствами должны обладать декомпозиции при нормализации?
ð+ сохранение функциональных зависимостей
ð+ соединения без потерь
ð разбиение без потерь
ð сохранение ключа
Задача 5. Приведение ко второй нормальной форме.
Вариант 1.
При каких условиях отношение находится во второй нормальной форме?
ð+ если оно находится в первой нормальной форме и каждый неключевой атрибут зависит от всего первичного ключа
ð если оно находится в первой нормальной форме и каждый неключевой атрибут зависит от части первичного ключа
ð если оно находится в первой нормальной форме и каждый неключевой атрибут не зависит от первичного ключа
ð+ если оно находится в первой нормальной форме и каждый неключевой атрибут не зависит от части первичного ключа
Вариант 2.
Как осуществляется приведение ко второй нормальной форме?
ð+
ð сначала схема отношения приводится к первой нормальной форме
ð производится декомпозиция с использованием функциональной зависимости, в которой неключевой атрибут зависит от всего первичного ключа
ð производится декомпозиция с использованием функциональной зависимости, в которой неключевой атрибут зависит от неключевого атрибута
Вариант 3.
Какие аномалии устраняются второй нормальной формой?
ð удаления
ð избыточность
ð обновления
ð включения
ð+ никакие
Задача 6. Приведение к третьей нормальной форме.
Вариант 1.
При каких условиях отношение находится в третьей нормальной форме?
ð если оно находится во второй нормальной форме и каждый неключевой атрибут зависит от всего первичного ключа
ð если оно находится во второй нормальной форме и каждый неключевой атрибут нетранзитивно зависит от части первичного ключа
ð+ если оно находится во второй нормальной форме и каждый неключевой атрибут нетранзитивно зависит от первичного ключа
ð если оно находится во второй нормальной форме и каждый неключевой атрибут не зависит от части первичного ключа
Вариант 2 .
Как осуществляется приведение к третьей нормальной форме?
ð производится декомпозиция с использованием функциональной зависимости, в которой неключевой атрибут зависит от части первичного ключа
ð+ сначала схема отношения приводится ко второй нормальной форме
ð+ производится декомпозиция с использованием функциональной зависимости, в которой неключевой атрибут транзитивно зависит от первичного ключа
ð производится декомпозиция с использованием функциональной зависимости, в которой неключевой атрибут нетранзитивно зависит от первичного ключ
Вариант 3.
Какие аномалии устраняются третьей нормальной формой?
ð удаления
ð+ избыточность
ð обновления
ð+ включения
ð+ никакие
Задача 7. Анализ функциональных зависимостей следующего отношения.
Вариант 1 .
Какие из перечисленных зависимостей существуют в этом отношении?
ð+ Код студента →Фамилия
ð+ Предмет→Дата
ð+ Код экзамена →Дата
ð Код студента→Оценка
Вариант 2.
Каких из перечисленных зависимостей не существует в этом отношении?
ð Код студента, Фамилия→Фамилия
ð Предмет→Дата
ð Код экзамена →Дата
ð+ Код студента→Оценка
ð Код студента, Предмет→Оценка
Вариант 3.
В какой зависимости определен первичный ключ отношения?
ð Код студента, Фамилия→Фамилия, Предмет
ð Предмет→Дата
ð Код экзамена →Дата
ð Код студента→Оценка
ð Код студента, Предмет→Оценка
ð+ Код студента, Код предмета →Дата, Оценка
Задача 8. Как осуществляется поддержка целостности данных в реляционных СУБД?
Вариант 1.
Какие требования должны выполняться для поддержки целостности данных в реляционных СУБД?
ð+ уникальность любого кортежа отношения
ð+ наличие у любого отношения первичного ключа
ð+
ð
Вариант 2 .
В чем состоят ограничения целостности сущности и по ссылкам?
ð+ для каждого значения внешнего ключа в ссылающемся отношении должен существовать кортеж с таким же значением первичного ключа в отношении, на которое ссылаются.
ð для каждого значения первичного ключа в ссылающемся отношении должен существовать кортеж с таким же значением внешнего ключа в отношении, на которое ссылаются
ð должны быть экземпляры сущностей
ð+ экземпляры сущностей должны уникально идентифицироваться
Вариант 3.
Какие варианты поддержки ограничений целостности по ссылкам используются в современных СУБД?
ð+ запрещается удалять кортеж, на который существуют ссылки.
ð+ при удалении кортежа, на который существуют ссылки, во всех ссылающихся кортежах значение внешнего ключа заменяется на неопределенное
ð+ при удалении кортежа, на который существуют ссылки, из ссылающегося отношения удаляются все ссылающиеся кортежи
ð при удалении кортежа, на который существуют ссылки, удаляется ссылающееся отношение
Литература
1. Карпова Т. Базы данных. Модели, разработка, реализация. – СПб.: Питер, 2001. – 304 с.
2. Конноли Т., Бэгг К., Страчан А. Базы данных: проектирование, реализация и сопровождение. Теория и практика. 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2000. – 1120 с.
3. Ульман Дж. Д., Уидом Дж. Введение в системы баз данных: Пер. с англ. – М.: Лори, 2000. – 374 с.
4. Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. Базы данных: Учебник для вузов. – СПб.: КОРОНА принт, 2000. – 416 с.
5. Толстобров А.П. Управление данными. Учебное пособие. Воронеж: Изд-во Воронежского ГУ, 2007 – 205 с.
6. Хансен Г., Хансен Дж. Базы данных: разработка и управление: Пер. с англ. – М.: ЗАО «Издательство «БИНОМ», 1999. – 704 с.
7. Дейт К.Дж. Введение в системы баз данных: Пер. с англ. – 6-е изд. – К.: Диалектика, 1998. – 784 с.
8. Швецов В.И., Визгунов А.Н., Мееров И.Б. Базы данных. Учебное пособие. Н.Новгород: Изд-во ННГУ, 2004. 271 с.
Лекция 9. Физические модели данных
(внутренний уровень)
Лекция посвящена вопросам физической организации данных в памяти компьютера. Здесь описывается структура памяти компьютера, и, с учетом ее особенностей представлены структуры хранения данных в оперативной и внешней памяти.
Ключевые термины: физические модели данных, структуры хранения, представление данных в памяти ЭВМ, физическая запись, последовательный файл, списковая структура, В-дерево, хэш-функция, индексирование.
Цель лекции: дать представление об основных типовых способах организации данных в памяти ЭВМ в СУБД с оценкой соответствующих моделей по времени доступа к данным в базе данных и по объему занимаемой памяти.
Как уже отмечалось, концептуальная схема, специфицированная к СУБД, автоматически отображается в структуру хранения программами СУБД. Внешний пользователь может ничего не знать о том, как его представление о данных физически организовано в памяти вычислительной системы. Тем не менее от физического размещения данных в памяти ЭВМ существенно зависит время решения прикладных задач. В связи с этим, даже на одном из начальных этапов проектирования базы данных – этапе выбора СУБД, желательно знать возможности физических структур хранения, представляемых конкретными СУБД, и оценивать временные характеристики проектируемой базы данных с учетом этих возможностей.
Способы физической организации данных в различных СУБД, как правило, различны и определяются типом используемой ЭВМ, инструментальными средствами разработки СУБД, а также критериями, которыми руководствуются разработчики СУБД при выборе методов размещения данных и способов доступа к этим данным. Заметим, что наиболее распространенным критерием служит время доступа к данным, однако в качестве критерия может выбираться, например, трудоемкость реализации соответствующих методов.
В настоящей лекции будут рассмотрены типовые физические модели организации данных в конкретных СУБД.
Физические модели данных служат для отображения моделей данных . Основными понятиями модели данных являются поле, логическая запись, логический файл. Слово «логический» введено, чтобы отличать понятия, относящиеся к логической модели данных, от понятий, относящихся к физической модели данных. Основными понятиями физической модели данных, используемыми для представления логической модели данных, являются поле, физическая запись, физический файл. В частности, логическая запись, состоящая из полей, может быть представлена в виде физической записи (из тех же полей), логический файл – в виде физического файла. Прежде чем конкретизировать понятия, относящиеся к физической модели данных, рассмотрим структуру памяти ЭВМ.
9.1. Структура памяти ЭВМ
Важнейшей особенностью памяти ЭВМ, в значительной степени определяющей методы организации данных и доступа к ним, является её неоднородность. Существуют два разных типа памяти – оперативная (ОП) и внешняя (ВП), причем процессор работает только с данными из оперативной памяти (рис. 9.1.).
Рис. 9.1. Схема работы ЭВМ
Как уже многократно отмечалось, базы данных создаются для работы с большими объемами данных, что обусловливает необходимость использования внешней памяти. Поэтому организация данных и доступа к ним должна учитывать как специфику каждого типа памяти, так и способы их взаимодействия.
Отметим основные свойства оперативной памяти:
· единицей памяти является байт;
· память прямоадресуема (каждый байт имеет адрес);
· процессор выбирает для обработки нужные данные, непосредственно адресуясь к последовательности байтов, содержащих эти данные.
Отметим основные свойства внешней памяти:
· минимальной адресуемой единицей является физическая запись;
· для последующей обработки (например, работы с полями) запись должна быть считана в оперативную память;
· время чтения записи в ОП (занесения записи из ОП в ВП) на несколько порядков выше времени обработки процессором записи из ОП;
· организация обмена осуществляется порциями, т.к. невозможно считать сразу всю базу данных.
9.2. Представление экземпляра логической записи
Логическая запись представляется в оперативной памяти следующим образом:
Прямая адресация байтов позволяет процессору выбирать для обработки нужное поле.
Заметим, что указанное представление не делает различий для записей в сетевой, иерархической и реляционных моделях. В случае сетевой и иерархической моделей некоторые поля могут являться указателями, тогда последовательность байтов, используемая для хранения этих полей, содержит адрес начала последовательности байтов, соответствующей записи – члену отношения.
В большинстве современных СУБД используется формат записей фиксированной длины. В этом случае все записи имеют одинаковую длину, определяемую суммарной длиной полей, составляющих запись. В СУБД другие форматы записей (переменной длины, неопределенной длины) встречаются гораздо реже, поэтому в данной книге эти форматы не рассматриваются. Заметим, что поля записи, принимающие значения существенно разной длины в различных экземплярах записей, в предметной области встречаются достаточно часто. Примером может служить поле резюме в записи СОТРУДНИК. Резюме может составлять полстраницы текста, страницу и т.д. Возникает проблема – как эту информацию переменной длины представить в записи фиксированной длины. Возможным вариантом является установление размера соответствующего поля по максимальному значению. В этом случае у многих экземпляров записи указанное поле будет заполнено не полностью и, таким образом, память ЭВМ будет использоваться неэффективно. Более эффективный и часто используемый в СУБД прием организации таких записей состоит в следующем. Вместо поля (полей), принимающего значение существенно разной длины, в запись включается поле-указатель на область памяти, где будет размещаться значение исходного поля. Как правило, эта область является областью внешней памяти прямого доступа. В процессе ввода соответствующего значения в выделенной области занимается столько памяти, какова длина этого значения.
На рис. 9.2 представлен пример вышеуказанного представления экземпляров записей из N полей, причем поле N принимает значения соответственно разной длины у разных экземпляров записей.
Рис. 9.2. Представление полей переменной длины
Конкретной реализацией такой схемы является поле типа МЕМО в СУБД (dBase III+, FoxPro, Access и т.д.).
9.3. Организация обмена между оперативной
и внешней памятью
Единицей обмена данными между оперативной и внешней памятью является физическая запись. Физическая запись читается (записывается) за одно обращение к внешней памяти. В частности, физическая запись может соответствовать одному экземпляру логической записи. Число обращений к внешней памяти при работе с базой данных определяет время отклика системы. В связи с этим для уменьшения числа обращений к БД при работе с ней увеличивают длину физической записи (объединяют в одну физическую запись несколько экземпляров логических записей). В этом случае физическую запись называют также блоком, число k экземпляров логических записей, составляющих физическую запись, – коэффициентом блокировки.
Ввод исходных данных в БД осуществляется следующим образом:
· в ОП последовательно вводятся k экземпляров логических записей (кортежей);
· введенные k экземпляров объединяются в физическую запись (блок);
· физическая запись заносится во внешнюю память.
Ввод k экземпляров записей исходной таблицы, составляющих i-ю физическую запись, изображен на рис. 9.3.
Рис. 9.3. Схема занесения записей во внешнюю память
Обработка данных, хранящихся во внешней памяти, осуществляется следующим образом:
· физическая запись (блок) считывается в оперативную память;
· обрабатываются экземпляры логических записей внутри блока (выбираются нужные поля, производится сравнение ключевого поля с заданным значением, осуществляется корректировка полей, выполняются операции удаления и т.п.).
В некоторых СУБД (например, MS SQL Server) единицей обмена между оперативной и внешней памятью является страница (вид физической записи, размер которой фиксирован и не зависит от длины логической записи). Организация обмена между оперативной и внешней памятью в этом случае аналогична описанной выше. Отличие здесь будет состоять в том, что экземпляры логических записей формируются в буфере, размером со страницу)если сразмер страницы не кратен длине логической записи, страница может быть заполнена неполностью, физическая запись на внешнем носителе, соответственно, будет заполнена не полностью).
9.4. Структуры хранения данных во внешней памяти ЭВМ
В современных СУБД наибольшее распространение получили табличные модели данных. В связи с этим, а также для большей определенности в настоящем разделе мы будем говорить о структурах хранения для табличной модели. Однако отметим, что некоторые из рассматриваемых ниже структур хранения могут использоваться и для представления сетевых и иерархических моделей.
В качестве внешней памяти мы рассматриваем наиболее распространенную в современных ЭВМ память прямого доступа. Память прямого доступа дает возможность обращения к любой записи, если известен её адрес. Для упрощения изложения мы не будем конкретизировать ряд служебных полей, которые содержит физическая запись, и их рассмотрение опускаем.
9.4.1. Последовательное размещение физических записей
В этой структуре хранения записи в памяти размещаются последовательно друг за другом. Как уже отмечалось, считаем, что все записи имеют равную длину. Физический адрес записи может быть легко вычислен по номеру записи (для вычисления необходимо знать формат соответствующей физической записи).
Физическая запись с номером I содержит логические записи с номерами
(I – 1) k +1
(I – 1) k +2
(I – 1) k +k
I = 1, 2, …, ;
знаком обозначим ближайшее целое, большее или равное N/k, – целое сверху.
Рассмотрим, как реализуются основные элементарные операции модели данных в этой структуре хранения, и оценим число этих операций. Напомним, что с точки зрения пользователя в табличной модели данных эти операции является операциями над строками (столбцами) таблицы.
