По степени структурированности данных

Оглавление

1.Основные типы СУБД. 2

2.Основные принципы построения баз данных, проблемы хранения больших объемов информац. 3

3.Уровни представления информации, понятие модели данных. 5

4.Реляционная модель данных, основные понятия. 7

5.Теоретические основы реляционного исчисления, использ исчисления предикатов 1-го порядка. 8

6. Иерархический и сетевой подходы при постр БД, основные понятия, достоинства и недостатки. 9

7.Реляционные базы данных: достоинства и недостатки. 11

8.Основные компоненты СУБД и их взаимодействие. Типы и структуры данных. 12

9.Обработка данных в СУБД, основные методы доступа к данным, использование структуры данных типа «дерево». 13

10.Поиск информации в БД с использованием структуры типа «бинарное дерево». 14

11.Методы хеширования для реализации доступа к данным по ключу. 15

12.Поиск информации в БД с использованием структуры типа «сильно ветвящееся дерево». 17

13.Представление данных с помощью модели «сущность-связь», основные элементы модели. 18

14.Типы и характеристики связей сущностей; 19

15.Построение диаграммы «сущность-связь» в различных нотациях. 21

16.Проектирование реляционных баз данных, основные понятия, оценки текущего проекта БД. 23

17.Понятие ключа в базах данных, первичные и внешние ключи. 24

18.Нормализация в реляционных базах данных, понятие нормальной формы при проектир БД. 25

19. 1НФ: Основные определения и правила преобразования. 26

20.2НФ: Основные определения и правила преобразования. 27

21.3НФ: Основные определения и правила преобразования. 28

Основные типы СУБД.

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

Для работы с базой данных СУБД должна обеспечивать:

· возможность внесения и чтения информации;

· работу с большим объемом данных;

· быстроту поиска данных;

· целостность данных (их непротиворечивость);

· защиту от разрушения, уничтожения (не только при случайных ошибках пользователя), от несанкционированного доступа;

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

· СУБД классифицируются:

По степени структурированности данных

a. Сильно структурированные

Большинство или каждый элемент описания имеют жесткий установленный формат (бухгалтерские СУБД)

b. Слабо структурированные

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

По степени сосредоточенности информации в узлах вычислительной сети

a. Локальные

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

b. Распределенные

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

По степени специализации для конкретной предметной области

a. Специализированные

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

b. Интегрированные

Представляют собой объединение специализированных БД, для нескольких сходных предметных областей.

c. Универсальные

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

Обработка данных в СУБД, основные методы доступа к данным, использование структуры данных типа «дерево».

Методы доступа к данным:

Физическо-последовательный

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

Индексно-последовательный

До осуществления доступа к собственно записям БД проверяются значения ключей.

Индексно-произвольный

При индексно-произвольном методе доступа записи хранятся в произвольном порядке.

Метод прямого доступа

Между ключом записи и ее физическим адресом существует взаимно однозначное соответствие. Физическое местоположение записи определяется непосредственно из значения ключа. Не требует упорядоченности значений ключей физических записей.

Хешированный

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

Статическое хеширование

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

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

Недостатком большинства хеш-функций является то, что они не гарантируют получение уникального адреса, поскольку количество возможных значений поля хеширования может быть гораздо больше количества адресов, доступных для записи. Каждый вычисленный хеш-функцией адрес соответствует некоторой странице, или сегменту, с несколькими ячейками (слотами), предназначенными для нескольких записей. В пределах одного сегмента записи размещаются в слотах в порядке поступления. Тот случай, когда один и тот же адрес генерируется для двух или более записей, называется конфликтом (collision), a подобные записи — синонимами. В этой ситуации новую запись необходимо вставить в другую позицию, поскольку место с вычисленным для нее хеш-адресом уже занято.

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

• открытая адресация;
• несвязанная область переполнения;
• связанная область переполнения;
• многократное хеширование.
• Открытая адресация

При возникновении конфликта система выполняет линейный поиск первого доступного слота для вставки в него новой записи.

Многократное хеширование

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

Динамическое хеширование

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

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

Элементы модели.

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

1.Сущность(entity) - это объект, который может быть идентифицирован неким способом, отличающим его от других объектов. Примеры: конкретный человек, предприятие, событие и т.д.

2.Набор сущностей- множество сущностей одного типа (обладающих одинаковыми свойствами). Примеры: все люди, предприятия. Наборы сущностей не обязательно должны быть непересекающимися. Например, сущность, принадлежащая к набору МУЖЧИНЫ, также принадлежит набору ЛЮДИ.

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

Атрибут - функция, отображающая набор сущностей в набор значений или в декартово произведение наборов значений. Домен-множество значений атрибута.

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

5.Связь – в общем случае это некоторая ассоциация, которая устанавливается между несколькими сущностями. Набор связей – это отношение между N сущностями каждое из которых относится к отдельному набору сущностей (N>=2). N=2 – Бинарная связь. N>2 – N-арная связь.

При построении модели С-С N-арной связи:

лучше отражают семантику П.О.

позволяют создать более компактную модель С-С.

Такие связи трудно реализуемы, и не обеспечивают целостность информации.

Бинарные связи – позволяют в полной мере обеспечить целостность связи.

Модель сущность-связь–один из наиболее удобных инструментов унифицированного представления данных.Она является логическим представление данных.

Из модели"сущность-связь" могут быть порождены все существующие модели данных (иерархическая, сетевая, реляционная, объектная),

Элементы:

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

Экземпляр сущности – это конкретный представитель данной сущности(например Попов Егор)

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

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

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

Набор связей (relationship set) - это отношение между n (причем n не меньше 2) сущностями, каждая из которых относится к некоторому набору сущностей.

14. Типы и характеристики связей сущностей;

Связь (relationship) -это ассоциация, установленная между несколькими сущностями.

Пример:

· поскольку каждый сотрудник работает в каком-либо отделе, между сущностями СОТРУДНИК и ОТДЕЛ существует связь "работает в" или ОТДЕЛ-РАБОТНИК;

· так как один из работников отдела является его руководителем, то между сущностями СОТРУДНИК и ОТДЕЛ имеется связь "руководит" или ОТДЕЛ-РУКОВОДИТЕЛЬ;

· могут существовать и связи между сущностями одного типа, например связь РОДИТЕЛЬ - ПОТОМОК между двумя сущностями ЧЕЛОВЕК;

Набор связей - это отношение между n (причем n не меньше 2) сущностями, каждая из которых относится к некоторому набору сущностей.

Пример:

сущности наборы сущностей

---------- ----------------

e1 принадлежит E1

e2 принадлежит E2

. . .

en принадлежит En

тогда [e1,e2,...,en] - набор связей R

В случае n=2, т.е. когда связь объединяет две сущности, она называется бинарной.

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

Виды степеней связи:

1. один к одному (1 : 1 ). Это означает, что в такой связи сущности с одной ролью всегда соответствует не более одной сущности с другой ролью.

2. один ко многим ( 1 : n ).Это означает что сущности с одной ролью может соответствовать любое число сущностей с другой ролью.

3. много к одному (n:1).Этот тип связи аналогичен связям один ко многим.

4. много ко многим (n:n).В этом случае каждая из ассоциированных сущностей может быть представлена любым количеством экземпляров

Класс принадлежности сущности, входящей в состав связи (кординальность связи):

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

сущность "СОТРУДНИК" имеет ассоциированную с ней сущность "ОТДЕЛ".

Таким образом, говорят, что сущность "СОТРУДНИК" имеет обязательный класс принадлежности (этот факт обозначается также указанием интервала числа возможных вхождений сущности в связь, в данн случае это 1,1), а сущность "ОТДЕЛ" имеет необязательн класс принадлежности (0,1)

· Обязательный класс принадлежности;

· Необязательный класс принадлежности.

Если существование сущности X зависит от существования сущности Y, то X называется зависимой сущностью (иногда сущность X называют "слабой", а"сущность" Y - сильной).

Пример:

Рабочая группа создается только после того, как будет подписан контракт

с заказчиком, и прекращает свое существование по выполнению контракта. Таким

образом, сущность РАБОЧАЯ_ГРУППА является зависимой от сущности КОНТРАКТ.

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

линией со стрелкой.

Нотация Мартина

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

Пример:

Нотация IDEF1X.

Обозначения сущностей:

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

Обозначение кардинальности связей:

Пример:

Кроме того, в IDEF1X вводится понятие “отношение категоризации”, по смыслу эквивалентное рассмотренной нами иерархической связи.

рис 1) Отношение полной категоризации (сущности-категории составляют полное множество потомков родительской сущности) обозначается:

рис 2) Также может существовать отношение неполной категоризации (сущности-категории составляют неполное множество потомков общей сущности):

Нотация Баркера.

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

Пример: (пример 2 как пример 1 только с дугой)

Для обознач отнош категоризации ввод элемент "дуга":

16. Проектирование реляционных баз данных, основные понятия, оценки текущего проекта БД.

Рисунок Этапы жизненного цикла БД <-> этапы проектирования БД

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

1. Системный анализ и словесное описание информационных объектов предметной области.

2. Проектирование инфологическоймодели предметной области - частично формализованное описание объектов предметной области в терминах некоторой семантической модели, например, в терминах ЕR-модели.

3. Даталогическое или логическое проектирование БД, то есть описание БД в терминах принятой даталогической модели данных,

4. .Физическое проектирование БД, то есть выбор эффективного размещения БД па внешних носителях для обеспечения наиболее эффективной работы приложения

Оценка проекта БД:

1) сокращение избыточности д-х,

2) уменьш-е затрат на многократн. обновление полей,

3) устранение возм-х противоречий инф-ии из-за хранения в разл. местах Þ получение «чистого» проекта, т.е. каждый факт в БД встреч-ся т. 1 раз.

Этапы проектирования БД:

1. Концептуальное проектирование - сбор, анализ и редактирование требований к данным. Для этого осуществляются следующие мероприятия:

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

2. Логическое проектирование - преобразование требований к данным в структуры данных. На выходе получаем СУБД-ориентированную структуру базы данных и спецификации прикладных программ. На этом этапе часто моделируют базы данных применительно к различным СУБД и проводят сравнительный анализ моделей.

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

КОНЦЕПТУАЛЬНЫЙ УРОВЕНЬ Сущности, атрибуты, связи	Представление аналитика
ЛОГИЧЕСКИЙ УРОВЕНЬ Записи, элементы данных, связи между записями	Представление программиста
ФИЗИЧЕСКИЙ УРОВЕНЬ группирование данных, индексы, методы доступа	Представление администратора

Пример приведения таблицы ко второй нормальной форме

Сотрудник	Должность	Зарплата	Наличие компьютера
Гришин	Кладовщик		Нет
Васильев	Программист		Есть
Васильев	Кладовщик		Нет

Таблица 5 Сотрудник и должность - первичный ключ

Зарплату сотруднику каждый начальник устанавливает сам, но её границы зависят от должности. Наличие же компьютера у сотрудника зависит только от должности, то есть зависимость от первичного ключа неполная.

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

В результате приведения к 2NF получаются две таблицы:

Таблица 6 В рельтате приведения получаются 2 теблицы:

Сотрудник	Должность	Зарплата	## табл 2 ->	Должность	Наличие компьютера
Гришин	Кладовщик		## табл 2 ->	Кладовщик	Нет
Васильев	Программист		## табл 2 ->	Программист	Есть
Васильев	Кладовщик		## табл 2 ->

21. 3НФ: Основные определения и правила преобразования.

Согласно определению Кодда, отношение R находится в 3NF тогда и только тогда, когда выполняются следующие условия:

· Отношение R находится во второй нормальной форме.

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

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

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

Понятное определение Билла Кента: каждый неключевой атрибут “должен предоставлять информацию о ключе, полном ключе и ни о чем, кроме ключа”. Условие зависимости от «полного ключа» неключевых атрибутов обеспечивает то, что таблица находится во второй нормальной форме. А условие зависимости их от «ничего, кроме ключа» — то, что они находятся в третьей нормальной форме.

Пример:

Сотрудник(ключ)	Отдел	Телефон отдела
Гришин	Бухгалтерия	11-22-33
Васильев	Бухгалтерия	11-22-33
Петров	Снабжение	44-55-66

В отношении атрибут «Сотрудник» является первичным ключом. Личных телефонов у сотрудников нет, и телефон сотрудника зависит исключительно от отдела.

Таким образом, в отношении существуют следующие функциональные зависимости: Сотрудник → Отдел, Отдел → Телефон, Сотрудник → Телефон.

Зависимость Сотрудник → Телефон является транзитивной, следовательно, отношение не находится в 3NF.

В результате декомпозиции отношения R1 получаются два отношения, находящиеся в 3NF:

Отдел	Телефон
Бухгалтерия	11-22-33
Снабжение	44-55-66

Сотрудник	Отдел
Гришин	Бухгалтерия
Васильев	Бухгалтерия
Петров	Снабжение

Исходное отношение R1 при необходимости легко получается в результате операции соединения отношений R2 и R3.

Оглавление

1.Основные типы СУБД. 2

2.Основные принципы построения баз данных, проблемы хранения больших объемов информац. 3

3.Уровни представления информации, понятие модели данных. 5

4.Реляционная модель данных, основные понятия. 7

5.Теоретические основы реляционного исчисления, использ исчисления предикатов 1-го порядка. 8

6. Иерархический и сетевой подходы при постр БД, основные понятия, достоинства и недостатки. 9

7.Реляционные базы данных: достоинства и недостатки. 11

8.Основные компоненты СУБД и их взаимодействие. Типы и структуры данных. 12

9.Обработка данных в СУБД, основные методы доступа к данным, использование структуры данных типа «дерево». 13

10.Поиск информации в БД с использованием структуры типа «бинарное дерево». 14

11.Методы хеширования для реализации доступа к данным по ключу. 15

12.Поиск информации в БД с использованием структуры типа «сильно ветвящееся дерево». 17

13.Представление данных с помощью модели «сущность-связь», основные элементы модели. 18

14.Типы и характеристики связей сущностей; 19

15.Построение диаграммы «сущность-связь» в различных нотациях. 21

16.Проектирование реляционных баз данных, основные понятия, оценки текущего проекта БД. 23

17.Понятие ключа в базах данных, первичные и внешние ключи. 24

18.Нормализация в реляционных базах данных, понятие нормальной формы при проектир БД. 25

19. 1НФ: Основные определения и правила преобразования. 26

20.2НФ: Основные определения и правила преобразования. 27

21.3НФ: Основные определения и правила преобразования. 28

Основные типы СУБД.

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

Для работы с базой данных СУБД должна обеспечивать:

· возможность внесения и чтения информации;

· работу с большим объемом данных;

· быстроту поиска данных;

· целостность данных (их непротиворечивость);

· защиту от разрушения, уничтожения (не только при случайных ошибках пользователя), от несанкционированного доступа;

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

· СУБД классифицируются:

По степени структурированности данных

a. Сильно структурированные

Большинство или каждый элемент описания имеют жесткий установленный формат (бухгалтерские СУБД)

b. Слабо структурированные

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