Шпаргалка по "Программированию"

Билет №8

1. Проектирование методом «сущность-связь». Нормализация отношений.

Основные  понятия ER-диаграмм

Сущность-это класс однотипных объектов, информация о которых должна быть учтена в модели.

Каждая  сущность должна иметь наименование, выраженное существительным в единственном числе.

Примерами сущностей могут быть такие классы объектов как "Поставщик", "Сотрудник", "Накладная".

Каждая  сущность в модели изображается в  виде прямоугольника с наименованием:

Экземпляр сущности - это конкретный представитель данной сущности.

Например, представителем сущности "Сотрудник" может быть "Сотрудник Иванов".

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

Атрибут сущности-это именованная характеристика, являющаяся некоторым свойством сущности.  

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

Примерами атрибутов сущности "Сотрудник" могут быть такие атрибуты как "Табельный номер", "Фамилия", "Имя", "Отчество", "Должность", "Зарплата" и т.п.

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

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

Ключевые  атрибуты изображаются на диаграмме  подчеркиванием:

Связь-это некоторая ассоциация между двумя сущностями. Одна сущность может быть связана с другой сущностью или сама с собою.

Связи позволяют по одной сущности находить другие сущности, связанные с нею.

Например, связи между сущностями могут выражаться следующими фразами - "СОТРУДНИК может иметь несколько ДЕТЕЙ", "каждый СОТРУДНИК обязан числиться ровно в одном ОТДЕЛЕ".

Графически  связь изображается линией, соединяющей  две сущности:

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

Каждая  связь может иметь один из следующих  типов связи:

Связь типа один-к-одному означает, что один экземпляр первой сущности (левой) связан с одним экземпляром второй сущности (правой). Связь один-к-одному чаще всего  свидетельствует о том, что на самом деле мы имеем всего одну сущность, неправильно разделенную на две.

Связь типа один-ко-многим означает, что один экземпляр первой сущности (левой) связан с несколькими экземплярами второй сущности (правой). Это наиболее часто  используемый тип связи. Левая сущность (со стороны "один") называется родительской, правая (со стороны "много") - дочерней. Связь типа много-ко-многим означает, что каждый экземпляр первой сущности может быть связан с несколькими экземплярами второй сущности, и каждый экземпляр второй сущности может быть связан с несколькими экземплярами первой сущности. Тип связи много-ко-многим является временным типом связи, допустимым на ранних этапах разработки модели. В дальнейшем этот тип связи должен быть заменен двумя связями типа один-ко-многим путем создания промежуточной сущности.

Каждая связь может иметь одну из двух модальностей связи:

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

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

Связь может иметь разную модальность  с разных концов 

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

<Каждый  экземпляр СУЩНОСТИ 1> <МОДАЛЬНОСТЬ  СВЯЗИ> <НАИМЕНОВАНИЕ СВЯЗИ> <ТИП  СВЯЗИ> <экземпляр СУЩНОСТИ 2>.

Каждая  связь может быть прочитана как  слева направо, так и справа налево.

Реальным  средством моделирования данных является не формальный метод нормализации отношений, а так называемое семантическое моделирование.

В качестве инструмента семантического моделирования  используются различные варианты диаграмм сущность-связь (ER - Entity-Relationship).

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

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

При правильном определении сущностей, полученные таблицы будут сразу находиться в 3НФ. Основное достоинство метода состоит в том, модель строится методом последовательных уточнений первоначальных диаграмм.

Под нормализацией отношения подразумевается процесс приведения отношения к одной из так называемых нормальных форм (или в дальнейшем НФ)

Всего в реляционной теории насчитывается 6 НФ:

1-я  НФ (обычно обозначается также 1НФ).

2НФ.

3НФ.

НФ  Бойса-Кодда (НФБК).

4НФ.

5НФ.

На практике, как правило, ограничиваются 3НФ.

1НФ

Схема отношения R находится в 1НФ, если значения в dom(A) являются атомарными для каждого  атрибута A в R.

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

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

Наим. Город Адрес Эл. почта WWW Вид Конт. Лица

Наим. Город Адрес Эл. почта WWW Вид Должность Ф.И.О. Код города Тел.

2НФ

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

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

Наим. Город Адрес Эл. почта WWW Вид Должность Ф.И.О. Код города Тел.

Город Код города

3НФ

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

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

Наим. Город Адрес Эл. почта WWW Вид

Наим. Город Ф.И.О. Должность Тел. 

2. Способы обеспечения  монопольного доступа  к разделяемым ресурсам. Алгоритмы распределения памяти. Способы защиты памяти.

Существуют  три типа доступа  к ресурсу (закрытия ресурса):

•   монопольный – только одна транзакция получает доступ к ресурсу (монопольный  тип доступа обычно используется при записи информации);

•   разделяемый – несколько транзакций получают доступ к ресурсу (разделяемый  тип доступа обычно используется при чтении информации);

•   предупредительный – в грáфе  запретов введен запрет на узел Х нижнего  уровня. Поддеревья, в которые входит узел X, помечаются меткой предупредительного запрета, чтобы не допустить наложения на поддеревья, содержащие узел X.

Известно  несколько способов распределения памяти:

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

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

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

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

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

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

Способы защиты памяти.

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

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