Фрагментація

Коректність фрагментації. Фрагментація даних не повинна виконуватися непродумано, навмання. Існують три правила, яких слід обов'язково дотримуватись при проведенні фрагментації.

1. Повнота. Якщо екземпляр відношення R розбивається на фрагменти, наприклад R1, R2,..., Rn, то кожен елемент, присутній у відношенні R, повинен бути, принаймні, в одному з створених фрагментів. Виконання цього правила гарантує, що будь-які дані не будуть втрачені в результаті виконання фрагментації.

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

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

Типи фрагментації. Існують два основних типи фрагментації: горизонтальна і вертикальна. У разі горизонтальної фрагментації елементом даних є кортеж, а у випадку вертикальної фрагментації – атрибут. Горизонтальні фрагменти являють собою підмножини кортежів відношення, а вертикальні – підмножину атрибутів відношення, як показано на рис. 11. Крім того, існують ще два типи фрагментації: змішана (рис. 12) і похідна (представляє собою варіант горизонтальної фрагментації).

……………………………….

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

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

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

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

Вертикальна фрагментація. Вертикальний фрагмент – виділений по вертикалі фрагмент відносини, що складається з підмножини атрибутів цього відношення. При вертикальній фрагментації в різні фрагменти об'єднуються атрибути, використовувані окремими додатками. Визначення фрагментів у цьому випадку виконується за допомогою операції проекції реляційної алгебри. Для заданого відношення R вертикальний фрагмент може бути обчислено за допомогою формули: (),, 1 R naa Kπ. Тут al,..., an являють собою атрибути відношення R. Вертикальні фрагменти визначаються шляхом встановлення спорідненості одного атрибута по відношенню до іншого. Один із способів вирішити цю задачу полягає у створенні матриці, що містить кількість звернень з вибіркою кожної з пар атрибутів. Наприклад, транзакція, яка здійснює доступ до атрибутів а1, а2 і а4 відношення R, що складається з набору атрибутів (а1, а2, а3, а4), може бути представлена наступною матрицею:

………………………..

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

Змішана фрагментація. В деяких випадках застосування лише горизонтальної і вертикальної фрагментації елементів схеми БД виявляється недостатньо для адекватного розподілу даних між додатками. Тоді доводиться вдаватися до змішаної (або гібридної) фрагментації.

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

Змішана фрагментація визначається за допомогою операцій вибірки і проекції реляційної алгебри. Якщо є деяке відношення R, то змішаний фрагмент може бути визначений за формулою: σ P(π a1, а2,..., an (R)). Тут р є предикатом, побудованим на використанні одного або більше атрибутів відношення R, позначених у формулах символами а1, а2,..., ап.

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

Термін «дочірнє» ми будемо використовувати для посилань на відношення, що містить зовнішній ключ, а термін «батьківське» для посилань на відношення з відповідним первинним ключем. Визначення похідних фрагментів здійснюється з допомогою операції полусоединения реляційної алгебри. Якщо задані дочірнє відношення R і батьківське відношення S, то похідний фрагмент відношення R може бути визначений наступним чином: Ri = R ⏐ > < ⏐ F Si, 1 ≤ i ≤ w.

Тут значення w – це кількість горизонтальних фрагментів, визначених для стосунки S, а параметр F задає атрибут, за яким виконується з'єднання.

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