Шпаргалка по "Информатике"

И наконец, программная  адаптация подразумевает процесс  модификации прикладных программ и  случае проведения реструктуризации базы данных. Обычно эта проблема возникает вследствие отсутствия логической независимости данных [121, 123, 125], а модификации включают новые последовательности команд манипулирования данными и замену переменных для подсчета числа логических записей в случае изменения коэффициент блокирования. 

27.Использование семантического моделирования при проектировании БД. ER-модели.

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

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

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

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

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

PRODUCT  ID       INTEOER JCT_NAMECHAR(10)

При правильном определении  сущностей, полученные таблицы будут  сразу находиться в ЗНФ.  Основное достоинство метода состоит   в   том,   модель   строится   методом   последовательных уточнений первоначальных диаграмм. В данной главе, являющейся иллюстрацией к методам ER-моделирования, не рассмотрены более сложные аспекты построения диаграмм, такие как подтипы, роли, исключающие связи, непереносимые связи, идентифицирующие связи и т.п. Концептуальные и физические ER-модели Разработанный выше пример ER-диаграммы является примером концептуальной диаграммы   Это означает, что диаграмма не учитывает     особенности     конкретной     СУБД.     По     данной концептуальной    диаграмме    можно    построить    физическую диаграмму, которая уже будут учитываться такие особенности СУБД, как допустимые типы и наименования полей и таблиц, ограничения целостности и т.п. Физический вариант диаграммы, приведенной на Рис. 9 может выглядеть, например, следующим

 

CUSTOMER
CUSTOMER  ID              INTEGER ADDRESS   ~                 CHAR(100) BANK                               CHAR(1CIO)				custom tnjo-cii
T		cust id          inteoer cust'summa    number(10.2)

CUST  ID INTEOER

PRODUCT ID     INTEOER

ГО  ПОЛЯМИ

и только есл

 

	SKLAD  ID           INTEOER
-SftAOJO

Рис. 10

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

"PRODINSKLAD", соответствующих сущностям "Запись списка накладной" и "Товар на складе", появились новые атрибуты, которых не было в концептуальной модели - это ключевые атрибуты родительских таблиц, мигрировавших в дочерние таблицы для того, чтобы обеспечить связь между таблицами посредством внешних ключей

 

23.3акрытое хеширование. Анализ открытого и закрытого

хеширования.

Закрытое хеширование

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

При закрытом хешировании применяется методика повторного хеширования, т.е. если мы пытаемся поместить элемент х в сегмент с номером h(x), который уже занят другим элементом (коллизия), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов h/ (x),        h₂ (х)..., куда можно поместить элемент х. Каждый из них проверяется, пока не будет найдено свободное местоположение (сегмент), если свободных сегментов нет, то таблица заполняется, и элемент х вставить нельзя. В=8

а, Ь, с, d

h(a)=3, h(b)=0, h(c)=4, h(d)=3 empty, deleted

методика линейного  хеширования: h1 (x)= (h(x)+i)mod В Если допускается удаление элементов, то при достижении пустого сегмента и не найдя элемента х, мы не можем быть уверены, что его нет вообще в хеш-таблице, т.к. сегмент может стать пустым уже после вставки элемента х. Поэтому для увеличения эффективности при поиске элемента X в хеш-таблице вводится константа delete, которая помещается в сегмент после удаления элемента данного сегмента.

26.Проектирование БД методом нормальных форм

Нормальные  формы

В п. 4.4 было дано определение первой нормальной формы (1НФ). Приведем здесь более строгое ее определение, а также определения других нормальных форм.

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

Из таблиц, рассмотренных в п. 4, не удовлетворяет  этим требованиям (т.е. не находится в 1НФ) только таблица

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

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

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

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

После разделения таблицы Поставщики рис. 4.3 на две  части все таблицы этого проекта удовлетворяют определению 2НФ, а так как в них нет неключевых полей, функционально зависящих друг от друга, то все они находятся в ЗНФ.

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

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

Таблица находится в нормальной форме Бойса-Кодда (НФБК), ее. ключа.

В соответствие с этой формулировкой таблицы  Блюда и Продукты рис. 4_;4, имеющие по паре возможных ключей (БЛ и Блюдо) и (ПР и Продукт) находятся в НФБК или в ЗНФ.

Процедура нормализации

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

21.Индексирование данных. Схемы индексирования. Плотные и разреженные индексы. Вторичные индексы.

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

Индекс исполняет  роль оглавления таблицы, просмотр которого предшествует обращению к записям  таблицы. Варианты решения проблемы организации физического доступа информации зависит:

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

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

Недостатком хеширования является то, что необходимо выполнять операцию свертки:

1. это требует дополнительного времени
2. могут возникнуть коллизии

Коллизии - это когда свертка дает одинаковый хеш-код для различных значений ключа.

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

1. одноуровневой

2, двухуровневой

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

1. поле значения старшего ключа, адресуемого блока
2. поле адреса начала этого блока

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

Алгоритм поиска для  данной схемы состоит из трех шагов:

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

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

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

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

Вторичные индексы- это файлы состоящие из пар (v , р), где v-это список значений по одному для каждого из полей F1, F2... Fn, а р-это указатель на v.

Сам факт вторичного индекса может быть организован  любым способом из перечисленных выше.

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

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

1. Для хранения вторичного индекса требуется место на диске.
2. Каждый создаваемый вторичный индекс замедляет выполнение всех операций вставки и удалений.

Несортированный файл с плотным индексом

В этом случае файл записей  сохраняет произвольный порядок  самих записей и     создается  другой файл называемый плотным индексом, он состоит из пар (х,р), где р- это  указатель с ключом х в основном файле. Эти пары отсортированы по значению ключа. Для поиска ключей в плотном индексе можно использовать структуру, подобную разряженному индексу. Если необходимо вставить новую запись, находится последний блок основного файла и производится вставка. Если последний блок полностью заполнен, то из файловой системы получают новый блок, одновременно вставляется указатель на |   соответствующую запись в файле плотного индекса. Чтобы {   удалить запись, в ней устанавливается бит удаления и удаляется соответствующий вход в индексном файле. 

37.Деревья. Основные  понятия. Бинарные деревья. Операции с бинарными деревьями.

Определим дерево таким образом дерево с базовым типом Т—это либо:

1. пустое дерево; либо
2. некоторая вершина типа Те конечным числом связанных с ней отдельных деревьев с базовым типом Т, называемых поддеревьями.

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