Створення РБД

Специфічні етапи створення РБД - це фрагментація і локалізація. Проектні рішення на цих етапах неоднозначні, і в ряді випадків (при виборі структури РБД) корисно використовувати математичне моделювання.

РБД складається з пов'язаних локальних баз даних (ЛБД). Можливі два варіанти створення РБД: проектування РБД "з нуля"; об'єднання (інтеграція) вже готових ЛБД. У першому варіанті моделі даних ЛБД, як правило, однакові (однорідні ЛБД), у другому моделі даних можуть бути різні (неоднорідні ЛБД).

Розглянуто теорія інтеграції для однорідних і неоднорідних ЛБД як сукупності процесів опису та маніпулювання даними. Представлені правила перетворення моделей даних один в одного.

Забезпечення цілісності

Будемо дотримуватися порядку викладу відповідно до етапів проектування (див. Рис. 2.6).

Як принципів проектування можна використовувати;

  • • максимум локалізації даних і скорочення кількості пересилаються по найкоротшому шляху даних: рекомендується мати до 90% її в локальній БД (ЛБД) вузла і близько 10% - у ЛБД інших вузлів;
  • • локальність розташування даних слід визначати по відношенню до найбільшого числа додатків.

В якості критеріїв проектування РБД можуть бути [16]: 1) мінімум обсягу пересилаються даних і повідомлень; 2) мінімум вартості трафіку; 3) мінімум загального часу, необхідного для обслуговування запитів до БД.

У розгляді РБД можливо виділити два випадки роботи: з одним додатком і з системою додатків. Можливо спадний і висхідний проектування.

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

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

У загальному випадку цілісність даних може порушуватися за такими основними причинами:

  • • помилки в створенні структури локальних БД і їх заповненні;
  • • прорахунки в побудові структури РБД (процедури фрагментації і локалізації);
  • • системні помилки в програмному забезпеченні взаємодії локальних БД (одночасний доступ);
  • • аварійна ситуація (несправність технічних засобів) і відновлення РБД.

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

Проблеми РБД

Рис. 11.1. Проблеми РБД

Іноді до порушення цілісності вважають навмисне спотворення інформації, т. Е. Несанкціонований доступ. Ці питання будуть вивчені в гол. 12.

Фрагментація і локалізація

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

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

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

Фрагментація [2], як зазначалося раніше, може бути горизонтальною і вертикальною. Частковий може бути визначений послідовністю операції селекції і проекції реляційної алгебри (див. Гл. 5). При декомпозиції слід виконати ряд умов.

  • 1. Повнота - всі дані глобального відносини R повинні бути відображені в його фрагменти.
  • 2. Восстанавливаемость - завжди можливо відновити глобальне ставлення з фрагментів.
  • 3. неперетинання - доцільно, щоб фрагменти не перетиналися (дублювання проводиться на етапі локалізації).

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

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

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

Фрагментація спільно з локалізацією (рис. 11.2) визначає в кінцевому підсумку швидкість реакції РБД на запит.

Схема фрагментації і локалізації даних

Рис. 11.2. Схема фрагментації і локалізації даних

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

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

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

де; m - число записів в горизонтальному фрагменті.

Після фрагментації здійснюють локалізацію. В якості критерію локалізації [2] зручно використовувати вплив локалізації (розміщення) на задачу оптимізації запиту при відомій його структурі. Для цього необхідні моделювання та оптимізація всіх додатків для будь-якого варіанту розміщення.

Скористаємося позначеннями, введеними в даній главі. Нехай - частота активізації додатки до у вузлі); rкi. - Число посилань пошуку програми k у фрагменті i; - число посилань поновлення даних додатка до у фрагменті i;

Завдання розміщення має дві основні різновиди: без використання і з використанням копій.

Розглянемо перший різновид. Тут можливі евристичні і строго математичні алгоритми.

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

Крок 1. Використовуємо метод "найбільш підходящого" розміщення: фрагмент Ri розміщуємо у вузлі j, де число посилань на нього максимально. Число локальних посилань

(11.1)

З виразу (11.1) визначаємо вузол j ', де слід розмістити фрагмент.

Крок 2. Застосуємо метод виділення "всіх вигідних вузлів" для надлишкового розміщення: поміщаємо у всіх вузлах, де вартість посилань додатків, що здійснюють пошук, більше вартості посилань додатків, оновлюють дані у фрагменті Rj в будь-якому вузлі: Bij> 0 або

(11.2)

де С - відношення вартості поновлення і пошуку.

Крок 3. Використовуємо метод "додаткового копіювання". Нехай dj - ступінь надмірності Ri; Fi - вигідність розміщення копії в будь-якому вузлі РБД і Модифікуючи вираз

(11.2), одержимо

(11.3)

Врахуємо вертикальну фрагментацію.

Нехай схема Rs декомпозирована на Rs і Rt, де s і t - вузли.

Використовуємо наступні міркування.

  • 1. Якщо існує два додатки Пs і Пt, які використовують тільки атрибути Rs і Rt, тобто звертаються тільки до вузлів s і t, то результатом фрагментації і локалізації буде відсутність віддалених посилань.
  • 2. Якщо є додаток (безліч додатків) Пq1, локальне для вузла w, яке посилається на Rs або Rt, то з'явиться одна віддалена посилання.
  • 3. Якщо є додаток Пq2, локальне по відношенню до w і посилається на атрибути Rs і Rt, то вийдуть два віддалені посилання.
  • 4. Якщо є додаток Пq3 у вузлах, відмінних від w, s або t, і посилається на Rs і Rt, то з'явиться ще одна віддалена посилання.

У загальному випадку вигідність фрагментації і локалізації (при С = I)

(11.4)

Описані евристичні алгоритми можуть НЕ дати раціонального рішення, тому розглянемо деякі строгі алгоритми, що базуються на целочисленном програмуванні (16).

Введемо позначення: - незалежні файли-дані; - вузли; L. - обсяг файлу; Ь. - Обсяг пам'яті вузла (для файлів); dsj- коефіцієнти, що враховують відстань між вузлами і; - вартість передачі; - інтенсивність запитів до файлу i з вузла j; - інтенсивність коригування повідомлень; - обсяг запитів до файлу i з вузла j; - обсяг запитуваних даних при виконанні запиту i з вузла j ;

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

Можливі наступні критерії: обсяг переданих даних; загальна вартість трафіку.

При використанні першого критерію отримуємо наступну задачу цілочисельного програмування:

Аналогічні вирази виходять при використанні другого критерію.

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

Більш детальні результати отримані за допомогою теорії масового обслуговування і цілочисельного програмування (див. [21-23]).

 
< Попер   ЗМІСТ   Наст >