Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Ярцев в. П. Створення та обробка баз даних на пеом

Ярцев в. П. Створення та обробка баз даних на пеом




Сторінка7/20
Дата конвертації10.03.2017
Розмір2.36 Mb.
ТипПротокол
1   2   3   4   5   6   7   8   9   10   ...   20

ПІБ





КодВикл




Предм


Каф





Посада

Оклад




ВидЗанят


Рис. 4.1. Схема залежностей між атрибутами вихідного

відношення ВИКЛАДАЧ


Отже, існує функціональна залежність атрибута Оклад від атрибута Посада.

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

Виявлені залежності між атрибутами в даному прикладі відбивають об'єктивно існуючі залежності між властивостями сутності. Питання про те, бажані вони чи небажані, як позбутися від небажаних залежностей розглянемо далі.


4.3. Перетворення відношень до 1, 2 і 3 нормальних форм

Тепер розглянемо конкретні вимоги, яким повинні задовольняти відношення у 1НФ, 2НФ і 3НФ, і проілюструємо на прикладах правила перетворення (декомпозиції) відносин для приведення їхній до тієї чи інший НФ.



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

Вихідне відношення завжди знаходиться в 1НФ, тому що по визначенню відношення його атрибути повинні бути простими.



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

У розглянутому вище прикладі відношення ВИКЛАДАЧ не задовольняє вимогам 2НФ. Неключові атрибути ПІБ, Каф і Посада знаходяться в частковій функціональній залежності від первинного ключа.

Для перетворення відношення до 2НФ виконується його декомпозиція за наступними правилами:

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

Для відношення ВИКЛАДАЧ така проекція єдина. Вона включає атрибути: КодВикл, Предм, ВидЗанят. Одержимо нове відношення, що доцільно назвати ЗАНЯТТЯ. Схема залежності між атрибутами приведена на Рис. 4.2.


Рис. 4.2. Схема залежності між атрибутами відносини ЗАНЯТТЯ
Б) Побудувати проекції на частині складеного первинного ключа й атрибути, що знаходяться у функціональній залежності від цих частин.

У розглянутому прикладі тільки одна така частина – атрибут


КодВикл. Одержувана проекція є відношенням, яку назвемо ВИКЛАДАЧ. Схема залежності атрибутів отриманого відношення показана на Рис. 4.3.

Рис. 4.3. Схема залежностей між атрибутами відношення ВИКЛАДАЧ, отриманого за правилом Б


Отже, у результаті зробленої декомпозиції вихідного відношення ми одержали два нових відношення: ЗАНЯТТЯ і ВИКЛАДАЧ. Неважко бачити, що отримані відношення задовольняють вимогам 2НФ.

Третя нормальна форма (3НФ). Відношення знаходиться в 3НФ, якщо воно знаходиться в 2НФ і кожний його неключовий атрибут нетранзитивно залежить від первинного ключа. У розглянутому прикладі відношення ЗАНЯТТЯ знаходиться в 3НФ. Відношення ВИКЛАДАЧ не задовольняє вимогам 3НФ, тому що атрибут Оклад від первинного ключа залежить транзитивно.

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

Проекція на атрибути Посада і Оклад дає відношення, що назвемо ОКЛАДИ. Схема залежності між атрибутами зображена на Рис. 4.4.

Рис. 4.4. Схема залежностей між атрибутами відношення ОКЛАДИ


Проекція на атрибути КодВикл, ПІБ, Каф і Посада дасть відношення ВИКЛАДАЧ. Схема залежності між його атрибутами показана на Рис. 4.5.


Рис. 4.5. Схема залежностей між атрибутами відношення ВИКЛАДАЧ, перетвореного до 3НФ

Отже, у результаті послідовної декомпозиції вихідного відношення ВИКЛАДАЧ (Рис. 4.1) ми одержали наступні три відношення:

ЗАНЯТТЯ (КодВикл, Предмет, ВидЗанят); (Рис. 4.2)

ОКЛАДИ (Посада, Оклад); (Рис. 4.4)

ВИКЛАДАЧ (КодВикл, ПІБ, Каф, Посада). (Рис. 4.5)

Кожне з цих відношень задовольняє вимогам 1, 2 і 3 НФ. У більшості практичних випадків цього досить для виключення аномалій і нормальної роботи БД.

Отримані відношення повинні бути зв'язані між собою. Схема зв'язків зображена на Рис. 4.6.


1
Рис. 4.6. Схема зв'язків між відношеннями, отриманими в результаті нормалізації вихідного відношення ВИКЛАДАЧ



4.4. Файлова організація даних

У різних СУБД збереження і доступ до даних організовані по різному. Однак, існують деякі загальні принципи, що застосовуються практично у всіх СУБД. Розглянемо їх основні положення.

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

Зовнішні носії інформації підрозділяються на пристрої з довільною адресацією (магнітні й оптичні диски) і пристрої з послідовною адресацією (магнітофони, стрімери).

Опти́чний диск - носій даних у вигляді пластикового чи алюмінієвого диска, призначеного для запису й відтворення звуку, зображення, буквенно-цифрової інформації тощо за допомогою лазерного променя. Щільність запису - понад 108 біт/см.
Носі́й інформа́ції (data medium) - матеріальний об'єкт , створений природою або ж навмисно людиною, за допомогою якого можна зберігати і передавати інформацію
На пристроях з довільною адресацією установка голівок запису-читання на потрібну адресу виконується практично миттєво. Час позиціювання голівок дуже малий в порівнянні з часом зчитування запису. Такі пристрої називають також пристроями прямого доступу.

У пристроях з послідовною адресацією для установки голівок на потрібну адресу потрібно послідовно “переглянути” усі попередні записи. Такі пристрої називають пристроями послідовного доступу. Для збереження БД такі пристрої не застосовуються.

Файли, розміщені на пристроях прямого доступу, які утримують записи постійної довжини, називають файлами прямого доступу. У таких файлах до будь-якого запису можна звертатися по фізичній адресі розташування запису на диску. Якщо записи у файлі мають довільну довжину, то звертатися до потрібного запису по його адресі не можна – потрібно послідовно переглянути всі попередні записи. Такі файли називають файлами послідовного доступу, незважаючи на те, що вони можуть розміщатися на пристрої прямого доступу.

Однак, на жаль, не завжди можна зберігати інформацію у вигляді файлів прямого доступу. Тому для БД винятково важливою є проблема швидкого доступу до даних. Причому суттю проблеми є навіть не стільки неможливість прямого доступу до фізичного запису, а насамперед взагалі низька ефективність доступу до записів по їхній фізичній адресі.

Розроблено дуже велика кількість засобів для подолання цієї проблеми. Однак основним засобом забезпечення швидкого доступу до даних є індексування.



4.5. Індексування

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

Пошук запису, у якій міститься задане значення поля (ключа), виконується по індексі в такий спосіб. На початку виконується пошук значення поля в індексі. Завдяки упорядкованості значень поля в індексі пошук виробляється дуже швидко тому, що застосовується так називаний “бінарний пошук” (іноді “логарифмічний пошук”), заснований на відомому методі розподілу навпіл. Зі знайденої в індексі запису визначається адреса основного запису, у якому міститься шукане значення. По цій адресі і виконується звертання до потрібного запису.

Крім того, висока швидкість досягається завдяки тому, записи в індексному файлі завжди мають постійну довжину.

Така загальна схема застосування індексу. Відомі різні варіанти реалізації цієї загальної схеми. Розглянемо найбільш розповсюджені з них.

4.5.1. Файли з щільним індексом

В основній області файлу розміщається послідовність записів однакової довжини, розташованих у довільному порядку. В індексній області розміщені індексні записи так само постійної довжини, які мають таку структуру:



Значення ключа (чи його згортка)

Номер запису

Тут значення ключа – це значення поля (це може бути первинний чи зовнішній ключ, або звичайне поле), для якого створюється даний індекс. Замість значення ключа звичайно зберігають його згортку (чи хеш-код), що має завжди невелику і фіксовану довжину, наприклад, 4 байти. Усі записи в індексній області упорядковані за значеннями ключа. Завдяки цьому в індексній області можна застосувати ефективний бінарний пошук, що вимагає мінімальних витрат часу на пошук.

Ефективність того чи іншого методу пошуку прийнято оцінювати максимальним часом доступу до довільного запису. Прийнято час доступу визначати не в абсолютних значеннях часу, а в кількості звертань до пристрою зовнішньої пам'яті, яким звичайно є диск. У випадку бінарного пошуку максимальна кількість звертань до диску (кроків пошуку) дорівнює:

Tпошуку = log2N,

де N – число записів, серед яких виконується пошук. Тому бінарний пошук часто називають також логарифмічним пошуком.

На диску записи зберігаються в блоках. Розмір блоку визначається фізичними параметрами дискового контролера і настроюваннями операційної системи. В одному блоці можуть розміщатися кілька записів.

На Рис. 4.7 показаний приклад організації файлу з щільним індексом.

Для оцінки виграшу, що дає використання щільного індексу, розглянемо такий приклад. Нехай відомі такі характеристики:


  • розмір блоку LB = 1024 байта;

  • довжина запису у файлі LZ = 256 байтів;

  • довжина первинного ключа LK = 4 байти;

  • кількість записів у файлі KZ = 100000.

Розрахуємо розмір індексного запису LI у такий спосіб. Для збереження номера запису нам буде потрібно 3 байти:

28 = 256 - 1 байт;

216 = 65536 - 2 байти;

224 = 16777216 - 3 байти.

Число 100000 можна зберігати у області пам’яти розміром не менше трьох байтів. Звичайно допускається тільки парна адресація. Тому для збереження номера запису відводимо 4 байти. З обліком цього довжина індексного запису буде дорівнювати:

LI = LK 4 = 4 4 = 8 байт.

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



KIZB = 1024/8 = 128.

Тепер знайдемо необхідну кількість індексних блоків:



KIB = 100000/128 = 781,25  782 блоку.

Тут результати ми округляємо у більшу сторону, тому що пам'ять виділяється тільки цілими блоками.



Обчислимо максимальну кількість звертань до диска при пошуку довільного запису в такий спосіб:

Тпошуку = Log2KIB 1 = Log2728 1  10 1 = 11.


2301

7

2302

5

3024

1






4025

6

4080

3

4100

2







4830

4

5420

8

Вільний простір

















Основна область

1

3024

Іванов

2

4100

Петров

3

4080

Симонов

4

4830

Олійник

5

2302

Зикін

6

4025

Кохан

7

2301

Бондар

8

5420

Токар









Блок 1

Індексна

область
Блок 2



Блок 3



Рис. 4.7. Приклад організації файлу з щільним індексом
Тут ми так само округляємо результат до найближчого цілого. Одиниця додана для обліку звертання до запису в основній області.

Отже, ми визначили, що для пошуку довільного запису в даному прикладі при застосуванні щільного індексу буде потрібно не більш 11 звертань до диска.

Тепер визначимо, скільки нам треба було б звертань до диска у випадку, якби індекс не створювався. Для цього треба було б у гіршому випадку переглянути всі блоки, у яких зберігаються записи в основній області. Часом пошуку усередині блоку ми зневажаємо, тому що цей процес протікає в оперативній пам'яті.

Кількість блоків основної області, необхідних для збереження всіх 100000 записів, дорівнює:



KBO = KZ/(LB/LZ) = 100000/ (1024/256) = 100000/4 = 25000 блоків.

Це значить, що максимальна довжина доступу при безпосередньому пошуку довільного запису дорівнює 25000 звертань до диска. Раніше ми визначили, що с застосуванням індексу достатньо лише 11 звертань. Як бачимо, виграш дуже істотний.

Тепер розглянемо, як будуть здійснюватися операції додавання і видалення записів при застосуванні щільного індексу.

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

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

Таким чином, максимальна кількість звертань до диска, що потрібно при додаванні нового запису – це кількість звертань при пошуку потрібного індексного блоку плюс 1 звертання для занесення зміненого індексного блоку і плюс 1 звертання для занесення запису в основну область:

Тдодав = Log2KIB 1 1 = Log2728 1 1  10 1 1 = 12.

Природно, у міру додавання нових записів відсоток розширення (вільний простір) буде зменшуватися. Коли зникне вільний простір, відбувається переповнення індексної області. У цьому випадку можливі два варіанти рішення: або перешикувати індексну область заново, або організувати область переповнення для індексної області, у якій розміщати записи, яки не помістилися в індексній області. У першому випадку буде потрібно витрачати додатковий час на перебудову індексної області. В другому випадку збільшиться час доступу до довільного запису і буде потрібно зберігати в індексному запису додаткові посилання на область переповнення. Саме тому при проектуванні БД важливо заздалегідь по можливості точніше визначити обсяги інформації, яка буде зберігатися, спрогнозувати ріст обсягу інформації і на основі цього розрахувати необхідний обсяг відсотка розширення в індексних блоках.



Видалення записів виконується в такий спосіб. Запис в основній області позначається як вилучений (відсутній). В індексній області відповідний індексний запис знищується фізично, тобто всі наступні за ним записи переміщаються таким чином, щоб заповнити місце вилученого попереднього запису. Ці дії виконуються в оперативній пам'яті. Таким чином, кількість звертань до диска при видаленні запису таке ж, як і при додаванні нового запису.

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



4.5.2. Файли з нещільним індексом чи індексно-послідовні файли

Нещільний індекс використовується у файлах, у яких записи в основній області зберігаються в упорядкованому виді. Записи в індексній області мають наступну структуру:



Значення ключа (згортки) першого запису блоку

Номер блоку, у якому зберігається запис

В індексній області записи містять ключі (згортки) перших записів із блоків основної області.

На Рис. 4.8 показаний приклад заповнення індексної й основної області при нещільному індексі.
Індексна область Основна область


2030

2031



Вільна область

3500

3501



Вільна область

4200

4201



Вільна область




Блок 0



2030

0

3500

1

4200

2






Блок 1


Блок 2

Рис. 4.8. Приклад індексної й основної області при нещільному індексі
В індексній і основній областях записи упорядковані. Пошук запису виконується наступним чином. В індексній області за заданим значенням ключа виконується пошук номера блоку, у якому знаходиться потрібний запис. Тому що всі записи в основній області упорядковані, знайдений блок буде завжди містити шуканий запис. Потім виконується зчитування блоку в оперативну пам'ять і там уже відбувається пошук і обробка потрібного запису. Після цього блок перезаписується на колишнє місце.

Звичайно, сортування даних в основній області вимагає значних витрат часу. Але оскільки один раз відсортовані файли при їхньому створенні потім тільки підтримуються у відсортованому виді, накладні витрати в процесі додавання нової інформації будуть значно менше.

Оцінимо довжину доступу до довільного запису для файлу з нещільним індексом. Як і раніше будемо думати, що у файлі зберігаються 100000 записів. Раніше ми уже визначили, що для їхнього збереження в основній області потрібно 25000 блоків. Для посилань на таку кількість блоків досить в індексному запису відвести 2 байти. Тоді довжина індексного запису дорівнює:

LI = LK 2 = 4 2 = 6 байт.

Кількість індексних записів в одному блоці буде дорівнювати:



KIZB = LB/LI = 1024/6 =170,6  171 запис.

Визначимо кількість індексних блоків, яка необхідна для збереження індексних записів:



KIB = KBO/KIZB = 25000/171 = 146,2  147 блоків.

Тепер визначимо довжину доступу при звертанні до довільного запису:



Тпошуку = Log2KIB 1 = Log2147 1  8 1 = 9.

Отже, ми бачимо, що у випадку нещільного індексу час доступу скоротилося до 9 у порівнянні з 11 при щільному індексі.



Додавання нового запису у випадку нещільного індексу виробляється так. Спочатку шукається необхідний блок в основній області, у якому потрібно помістити новий запис. Знайдений блок основної області зчитується в оперативну пам'ять і там дописується в нього новий запис. Змінений блок потім зберігається на колишнім місці. При додаванні нового запису індексна область не корегується.

Тут так само задається відсоток розширення, але вже стосовно до основної області.



Видалення запису виробляється шляхом її фізичного видалення з основної області. Корегування індексної області при цьому так само не потрібно.


4.5.3. Організація індексів у виді В-дерев

Ідея побудови В-дерев проста і полягає в наступному. Спочатку будується нещільний індекс, як це було описано вище. Потім індексна область розглядається як основний файл і для нього ще будується нещільний індекс. Потім знову над новим індексом будується індекс наступного рівня і так доти, поки не виявиться, що індексна область складається з одного блоку. У результаті одержуємо деяке дерево, у якому кожен батьківський блок зв'язаний з однаковою кількістю підлеглих блоків, число яких дорівнює числу індексних записів, розміщених в одному блоці. Кількість звертань до диска для пошуку довільного запису при використанні такого багаторівневого індексу буде завжди однаково (для будь-якого запису) і дорівнювати кількості рівнів в отриманому дереві. Такі дерева називають збалансованими (від англ.. balanced), звідси назва В-дерево. На Рис. 5.3 зображена схема, що пояснює організацію індексу у виді В-дерева.

Побудуємо В-дерево для умов нашого приклада. На першому рівні число блоків дорівнює числу блоків основної області, тобто дорівнює 25000 блоків. Другий рівень утвориться як нещільний індекс над основною областю. Його ми вже будували, кількість блоків у ньому – 147. Тепер над цим другим рівнем знову побудуємо нещільний індекс.

Довжину індексного запису будемо вважати колишньою і рівною 6 байтам. Кількість індексних записів в одному блоці ми також уже визначали, вона дорівнює - 171 запис. Визначимо, скільки потрібно блоків, що необхідні для індексної області наступного 3-го рівня. Оскільки індексна область попереднього рівня містить 147 блоків, а в одному блоці можна розмістити посилання на 171 блок, то ясно, що на 3 рівні досить одного блоку.

Отже, ми одержали для розглянутого приклада дерево, що складається з 3 рівнів (Рис. 4.9). Це значить, що для доступу до довільного запису у випадку індексу у виді В-дерева буде необхідно лише 3 звертання до диска. Причому це не максимальна кількість звертань, а завжди та сама, однакова для доступу до будь-якого запису.

Нещільний Основна



індекс область

































3 2 1


рівень рівень рівень

(1 блок) (147 блоків) (25000 блоків)


Рис. 4.9. Приклад організації індексу у вигляді В-дерева
Механізм додавання і видалення записів при організації індексу у виді В-дерева аналогічний розглянутому вище механізму для нещільного індексу.

4.6. Первинні і вторинні індекси

Для первинного ключа індекс створюється автоматично практично у всіх СУБД. Але при роботі з БД доводиться робити пошук по будь-якому полю, не тільки по первинному ключу. Тому у всіх СУБД передбачається можливість створення вторинних (чи користувальницьких) індексів, що можуть створюватися для не ключових полів. Оскільки створення кожного нового індексу завжди вимагає додаткових витрат дискової пам'яті, рекомендується вторинні індекси створювати тільки для тих полів, по яких передбачається найчастіше робити пошук даних.

Створення вторинних індексів, як правило, засноване на використанні первинного індексу. В індексній області вторинного індексу містяться у відсортованому виді хеш-коди (згортки) значень індексованого поля з відповідними посиланнями на первинний індекс. При пошуку по вторинному індексі спочатку визначається відповідний потрібному запису первинний ключ, а потім через цей ключ і первинний індекс здійснюється доступ до потрібного запису в основній області файлу. На Рис. 5.4 приведена узагальнена схема, що пояснює механізм використання вторинних індексів.


Пошук по


первинному

ключу

Пошук по Пошук по Пошук по

полю Х полю Y полю Z


Рис. 4.10. Схема використання вторинних індексів
У деяких СУБД, наприклад, у Access, розподіл індексів на первинні і вторинні не виконується. Вторинні індекси можуть знищуватися, чи змінюватися, створюватися заново.
Контрольні запитання

  1. Для чого потрібна нормалізація відношень?

  2. Загальні властивості нормальних форм.

  3. Поясніть поняття функціонально-повної, часткової і транзитивної залежностей між атрибутами відношень. Наведіть приклади.

  4. Вимоги до 1 НФ і 2 НФ.

  5. Правило перетворення відношень в 2 НФ.

6. Вимоги до 3 НФ. Правило перетворення відношень в 3 НФ.

7. Яка різниця між файлами прямого та послідовного доступу: недоліки, переваги.

8. Ідея та механізм роботи індексу. Первинні та вторинні індекси.

9. Файли з щільним індексом. Ідея та механізм роботи.

10. Файли з нещільним індексом. Ідея та механізм роботи.

11.Організація індексу у виді В-дерева. Ідея та механізм роботи, переваги.



1   2   3   4   5   6   7   8   9   10   ...   20



  • Посада
  • 4.3. Перетворення відношень до 1, 2 і 3 нормальних форм
  • 4.4. Файлова організація даних
  • 4.5. Індексування
  • 4.5.1. Файли з щільним індексом
  • 4.5.2. Файли з нещільним індексом чи індексно-послідовні файли
  • 4.5.3. Організація індексів у виді В-дерев
  • 4.6. Первинні і вторинні індекси