Використання протоколу двох фазного блокування для усунення проблем.

12.4. Впорядкованість і відновлюваність.

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

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

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

Розрізняють впорядкований та відновлюваний непослідовні графіки:

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

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

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

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

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

Відновлюваний графік – це графік, у якому для кожної пари транзакцій Т_i і T_j виконується наступне правило: якщо транзакція Т_j зчитує елемент даних, попередньо записаний транзакцією Т_i, то фіксація результатів транзакції Т_i повинна виконуватися до фіксації результатів транзакції Т_j.

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

12.5 Методи керування паралельністю.

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

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

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

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

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

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

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

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

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

- якщо транзакція встановила блокування елемента даних для читання, воно зможе читати його, але не зможе оновити.

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

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

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

Порядок блокування:

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

- якщо елемент ще не заблокований іншою транзакцією, блокування елемента буде виконано успішно;

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

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

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

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

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

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

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

Відповідно, кожна транзакція може бути розділена на дві фази:

-фазу наростання,у якій виконуються всі необхідні блокування і не звільняється жодного з елементів даних;

-фазу стискування,у якій знімаються усі, виконані раніше, блокування елементів даних.

Засоби підтримки підсистеми транзакцій

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

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

Лекція 13. Індексація даних в БД.

Поняття індексації даних. Структура індекса. Способи організації індексів. Деревоподібні, хеш та бітові індекси. Методи доступу. Зберігання даних. Індексація. Кластеризація. Розподіл. Індексація за і проти.

13.1. Поняття індексації даних.

Індекс- це допоміжна структура, що дозволяє СУБД пришвидшити пошук даних по запитах користувачів.

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

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

Використання індексації даних дозволяє кардинально знизити кількість операцій звернення до зовнішньої пам’яті (дискових, ...), прискоривши доступ до даних і звільнивши системні ресурси для інших операцій.

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

2.Структура індекса.

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

Найпростіша структура індекса має вигляд:

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

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

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

Структури індексу відрізняється способом пошуку ключа за заданим значенням. По цьому критерію розрізняють системи індексації з використанням технології B-дерева та хеширування

3. Технологія B-дерева

Є найбільш популярним підходом до організації індексів у базах даних. З погляду зовнішнього логічного представлення B-дерево - це збалансоване гіллясте дерево в зовнішній пам'яті.

Збалансованість означає, що довжина шляху від кореня дерева до будь-якого його листа та сама.

Гіллястість дерева - це властивість кожного вузла дерева посилатися вузли-нащадки.

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

Мал.13.1 Структура корення дерева та вузлів-гілок

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

Він містить містить ряд значень індексу, що включають значення ключа і покажчик на визначену індексну сторінку (яка називається вузлом-гілкою)

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

Індекс діє в такий спосіб:

При співпаданні перших елементів розшукуваних даних “a” переходимо до індексної сторінки “a*”, при співпадані наступного елемента розшукуваних даних “aa” до індексної сторінки наступного рівня, що містить адреси елементів “aa*” і так до тих пір, поки не вийдемо на елемент індекса, що безпосередньо вказує на самі розшукувані дані.

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

Мал.13.2.Дерево пошуку з вузлами-гілками і вузлами-листками

Як і кореневий вузол, кожен вузол-гілка містить ряд індексних рядків у структурі індексної сторінки. Кожен індексний рядок указує на інший вузол-гілку або на вузол-лист (кінцевий вузол) (мал. 11.2). Вузол-лист є останнім рівнем індексу. На відміну від кореневого вузла кожен вузол-гілка містить також зв'язаний список вузлів-гілок того ж рівня. Іншими словами, вузол "знає" про суміжні вузли і про вузли більш низького рівня

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

Кількість операцій звернення до зовнішньої пам’яті, які необхідні для досягнення вузлів-листів (вузлів самого нижнього рівня дерева), залежить від кількості рівнів індексу.

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

3.1.Типи індексів B-дерева.

Існує два типи індексів B-дерев: кластерні і некластерні індекси.

3.1.1.Кластерні індекси

Кластерний індекс зберігає у своїх вузлах-листах реальні рядки даних у відсортованому порядку, оскільки індекс є впорядкованою структурою.

Мал.13.3. Кластерний індекс

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

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

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

Якщо відомо, що дані після зчитування потрібно видавати у визначеному порядку, то використання кластерного індексу дозволяє, уникнути сортування.

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

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

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

З іншого боку, можна створити некластерний індекс в кластерній таблиці. (Кластерна таблиця – це таблиця, що містить кластерний індекс).

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

3.1.2.Некластерні індекси

Рис.13.4.Некластерний індекс по таблиці, що не має кластерного індекса.

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

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

Кожна таблиця може мати тільки один кластерний індекс і до n- некластерних (наприклад 249 некластерних індексів для таблиці MS SQL Server 2000).

Рис.13.5.Некластерний індекс по таблиці, що має кластеризований індекс.

4. Технологія хеширування.

Є альтернативою технології B-дерева. Загальною ідеєю методів хеширування є застосування до значення ключа деякої функції згортки (хеш-функції), що генерує значення меншого розміру.

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

Основною вимогою до хеш-функції є:

- стійкість до колізій (два різні набори даних повинні мати різні результати перетворення);

- рівномірний розподіл значення згортки.

Її використання дозволяє на одній індексній сторінці розмістити більше інформації.

Разом з тим хеширування не гарантує відсутності колізій. Для подолання виникаючих конфліктів використовують наступні методи:

-відкритої адресації:

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

-використання зв’язаної області переповнення

При виникнені колізій для записів, що мають однакову функцію згортки створюється т.з. область переповнення, куди поміщаються конфліктуючі записи. При цьому вводиться додаткове поле – покажчик синоніму, що є адресою записів всередині області переповнення. Якщо він дорівнює 0, то це означає відсутність конфлікту.

-багатократного хеширування:

Спосіб вирішення конфліктів, що полягає в використані другої хеш-функції, якщо перша призводить до колізії. Її метою є отримання нової адреси хешируваня, яка б дозволила б уникнути конфлікту. Вона використовується для розміщення записів в області переповнення.

Переліченні вище методи хеширювавання є статичними – в них простір хеш-адрес задається при створені таблиці.

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

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

Для подолання проблеми використовують метод динамічного хеширування:

Хэш-функція при цьому міняється динамічно, у залежності від глибини B-дерева.

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

Більш того, хеширування не підходить для пошуку і вибірки даних по будь якому іншому полю, відмінному від поля хеширування.

Разом з тим, слід відмітити можливість поєднання кращих властивостей методів B-дерева та хеширування.

Основою методу динамічного хеширування є обробка числа, згенерованого хеш-функцією у вигляді послідовності біт, і розподілу записів по сегментам на основі так званої прогресуючої оцифровки (progressive digitization) цієї послідовності. Динамічна хеш-функція генерує значення в широкому діапазоні, а іменно n-бітові двійкові цілі числа, де n, як правило дорівнює 32

5.Алгоритм роботи СКБД при внесенні та видаленні запису в таблицю, що містить індексовані поля з використанням технології В-дерева.

Основною "ізюминкою" B-дерев є автоматична підтримка властивості збалансованості. Розглянемо, як це робиться при виконанні операцій вставки і видалення записів.

5.1.При вставці нового запису в таблицю виконується:

1.Пошук листкової сторінки. Фактично, виконується звичайний пошук по ключу. Якщо в B-дереві відсутній ключ із заданим значенням, то буде отримано номер сторінки, у якій йому слід знаходитись, і відповідні координати усередині сторінки.

2.Переміщення запису на місце. Природно, що вся робота виконується в буферах оперативної пам'яті. Листкова сторінка, у яку потрібно занести запис, зчитується в буфер, і в ньому виконується операція вставки. Розмір буфера повинний перевищувати розмір сторінки зовнішньої пам'яті.

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

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

5.Щоб забезпечити доступ від кореня дерева до ново створеної сторінки, необхідно відповідним чином модифікувати внутрішню сторінку, що є предком раніше існуючої листкової сторінки, тобто вставити в неї відповідне значення ключа і посилання на нову сторінку. При виконанні цієї дії може знову відбутися переповнення тепер уже внутрішньої сторінки, і вона також буде розщеплена на дві. У результаті буде потрібно вставити значення ключа і посилання на нову сторінку у внутрішню сторінку-предка вище по ієрархії і т.д.

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

5.2.При видаленні запису виконуються наступні дії:

1.Пошук запису по ключу. Якщо запис не знайдений, то значить видаляти нічого не потрібно.

2.Реальне видалення запису в буфері, у якому прочитана відповідна листова сторінка.

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

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

5.Листкова сторінка, що стала непотрібною, заноситься в список вільних сторінок. Відповідним чином коректується список листкових сторінок.

6.Щоб усунути можливість доступу від кореня до звільненої сторінки, потрібно видалити відповідне значення ключа і посилання на звільнену сторінку з внутрішньої сторінки - її предка. При цьому може виникнути потреба в злитті цієї сторінки з її лівою або правою сусідньою внутрішньою сторінкою і т.д.

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

Як видно, при виконанні операцій вставки і видалення записів властивість збалансованості B-дерева зберігається, а зовнішня пам'ять витрачається досить ощадливо.

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

-розщеплення, що випереджають, тобто розщеплення сторінки не при її переповненні, а трохи раніш, коли ступінь заповнювання сторінки досягає деякого рівня;

- переливання, тобто підтримка рівноважного заповнення сусідніх сторінок;

-злиття 3-в-2, тобто породження двох листових сторінок на основі вмісту трьох сусідніх.

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

6.Властивості індексів.

Індекси можуть бути простими та складними.

Простий індекс визначається тільки на одному атрибуті відношення.

Щоб індекс використовувався оператором SQL, посилання на цей стовпчик повинно бути включене в речення WHERE даного оператора.

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

Індекс може бути унікальним або не унікальним. В унікальному індексі кожне значення індексного ключа повинне бути унікальним. В не унікальному індексі допускається дублювання індексних ключів у таблиці даних. Ефективність не унікального індексу залежить від вибірковості (селективності) даного індексу.

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

7.Індексація. За і проти. Ефективність використання.

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

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

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

8.Обмеження використання індексів.

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

1.Візьмемо такий запит SQL: Select P1 from T1 where P2 like '%ров';

Цей запит повинен нам знайти всіх клієнтів, у яких прізвище закінчується на «ров», однак навіть якщо стовпxbr P2 проіндексований, СКБД все одно буде використати повний перебір таблиці.

Це пов'язане з тим, що індекси будуються в припущенні, що слова/символи йдуть зліва на право. Використання символу підстановки на початку умови пошуку виключає для СКБД можливість використання пошуку по бінарному дереву.

Ця проблема може бути вирішена створенням додаткового індексу за виразом reverse(P2) і формуванням запиту виду:

Select p1 from T1 where reverse(P2) like reverse('%ров');

У цьому випадку символ підстановки виявиться в найбільш правій позиції («вор%»), що не виключає використання індексу за reverse(P2).

8.1.Обмеження послідовності стовпців складного ключа.

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

Наприклад, ми маємо телефонний довідник, відсортований спочатку за містом, потім за прізвищем, і потім за ім’ям. Якщо ви знаєте місто, тоді ви легко можете знайти всі телефони цього міста. Однак і такому довіднику буде складно знайти всі телефони, записані на певне прізвище – для цього необхідно подивитися в секцію кожного міста і пошукати там потрібну інформацію. Деякі СКБД виконують цю роботу, інші ж просто не використовують такий індекс.

8.2.Обмеження пов’язані з низькою селективністю індекса.

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

Для швидкої вибірки по індексах, що побудовані на таких даних використовуються двійкові маскові індекси (в БД Oracl).

9.Індексація данних БД та оптимізатор SQL-запитів.

Оптимізатор SQL-запитів являє собою модуль ядра монопольної цільової СУБД або SQL-сервера.

Його задача – пошук найбільш оптимального шляху доступу до даних. Він повинен знайти таку послідовність дій, яка б забезпечила побудову найбільш ефективного плану виконання SQL-запиту.

Його роботою можна керувати шляхом введення в SQL-запит речення PLAN.

Select P1 from T1 where P2 =’Петров’ plan natural; - відключає використання індекса, якщо поле P2 проіндексоване.

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

Такий тип індексів підтримується MS SQL Server 2000 і насправді більше схожий на каталог, ніж на індекс. Його структура, відміна від B-дерева. Повнотекстовий індекс дозволяє виконувати пошук по групах ключових слів в механізмах пошуку Wеb-вузлів.

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

Лекція 14. Розподілені інформаційні системи.

Переваги і недоліки, властиві розподілених СКБД. Гомогенні і гетерогенні розподілені СКБД. Архітектура та принципи функцонуванняї розподілених БД. Компонентна архітектура розподілених СКБД Побудова розподілених БД. Розподіл даних. Фрагментація. Забезпечення прозорості в РБД. Прозорість розподіленості. Прозорість транзакцій. Прозорість виконання. Прозорість використання СКБД. Дванадцять правил Дейта для РСКБД.

14.1. Розподіленні бази даних.

14.1.1. Класифікація РБД.

БД по географії місцезнаходження даних поділяються на централізованіта розподілені.

Розподілені БД класифікуються як гомогенні та гетерогенні.

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

Останні, як правило, є результатом об’єднання в єдину інформаційну систему раніше локально існуючих інформаційних систем. Їх експлуатація повязана з додатковими труднощами:

-відображення структури даних однієї моделі в відповідні структури даних іншої моделі (наприклад відношення реляційної моделі в типові записи і набори мережевої моделі);

-трансляції текстів запитів з однієї мови в іншу (наприклад, запит з SQL-оператором SELECT необхідно буде трансформувати в запит з операторами FIND и GET мови манііпулювання даними мережевої СУБД);

Все це надзвичайно ускладнює обробку даних в гетерогенних СУБД та підтримку правил цілістності БД та системи управління транзакціями.

Виділяють ще один тип РБД - мультибазові системы в яких управління кожною локальною частиною ІС виконується абсолютно автономно їх власними операторами.

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