ПРО ОДИН ПІДХІД ДО СИНТЕЗУ СХЕМИ РЕЛЯЦІЙНОЇ БАЗИ ДАНИХ

Деталі
Категорія: П'ятнадцята всеукраїнська практично-пiзнавальна iнтернет-конференцiя

Онищенко Алла Георгіївна

Студентка, старший лаборант

Харківський національний університет радіоелектроніки

Україна, м. Харків

 

Філатов Валентин Олександрович

Доктор технічних наук, професор

Завідувач кафедрою штучного інтелекту

Харківський національний університет радіоелектроніки

 

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

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

 

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

  1. Структурна специфікація, або правила, за якими здійснюється структуризація даних у базі даних(БД); 
  2. Операційна специфікація, або правила маніпулювання даними в БД;
  3. Семантичні правила, які задають множину допустимих станів (реалізацій) БД.

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

  Основною структурною одиницею в реляційній моделі є n – арне відношення, тобто підмножина кортежів декартова добутку n доменів (не обов’язково різних). Як бачимо, поняття відношення в контексті БД генетично пов’язане з поняттям теоретико-множинного відношення, але має деякі особливості порівняна з останнім. Тому коли з контексту не зрозуміло, про яке саме відношення йде мова, вживатимемо також термін DB – відношення (тобто відношення бази даних) [1].

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

  Дамо тепер формальне означення структурної компоненти реляційної моделі. Нехай  D – множина доменів, які використовуються; D = {D1, ..., Dm}; Di – домен, тобто множина значень. Позначимо R множину атрибутів БД, R* - сімейство всіх скінченних непорожніх підмножин R; Ri - елемент R* , який називатимемо носієм DB – відношення. Нехай задано відображення Dom : R→D, яке для кожного атрибута відношення встановлює, з якого саме домену вибираються значення при формуванні кортежів. 

  Якщо носій відношення Ri  = { Ai  , …, Ak }, то для нього визначений декартів добуток 

 Pi = Dom A1 x … x Dom Ak  як множина k – кортежів. Сімейство P*i  підмножин множини Pi  є множиною відношень з носієм  Ri  : P*i  = {}. (Зважаючи на зроблене зауваження перестановка атрибутів у носії не враховується.) Позначимо тепер  P* множину всіх відношень, що здаються структурною компонентою реляційної моделі:  . Таким чином, у найпростішому випадку структурну компоненту можна задати як набір:

SRM = < D, R, Dom > [2,3]. 

  Розглянемо відношення зі схемою σ = (R;F) . З метою підтримки обмежень, заданих множиною F, у процесі функціонування БД для кожного кортежу t, що його потрібно додати до множини вже існуючих кортежів відношення (або, як кажуть, увести в БД), слід перевірити, чи не порушує цей кортеж якихось обмежень із F. У свою чергу, така перевірка, наприклад, для обмеження X→Y полягає у пошуку в DB – відношенні кортежу  δ такого, що   δ [Y] і t[Y]. Отже, з метою підвищення ефективності процесу введення кортежів бажано було б, по-перше, зменшити до мінімуму число перевірюваних залежностей, по-друге, звести до мінімуму число значень у кортежах, що зіставляються (за рахунок, скажімо, зменшення синтаксичної потужності множини атрибутів X і Y), по-третє, забезпечити використання найефективніших методів пошуку.

  Що стосується перших двох вимог, то деякою мірою їх виконання забезпечується використанням замість заданої довільної множини обмежень F редукованого базису G для F* , методи обчислення якого розглянуто вище. Що можна зробити на рівні логічного проектування для створення найсприятливіших умов для використання тих чи інших методів пошуку в БД, тобто для вирішення питань фізичної організації БД? Для відповіді на це запитання пригадаємо, що взагалі існують кілька еквівалентних образів “тієї самої” БД, які можуть різнитися числом кортежів, що переглядаються під час пошуку.

  Розглянемо найпростіший метод послідовного доступу до кортежів відношення. Нехай, наприклад, схема відношення   і число кортежів у якомусь стані БД становить N. Тоді для підтримки заданих обмежень при введенні нового кортежу слід переглянути “в середньому” N/2 + N/2 = N кортежів. Якщо “еквівалентним” є образ зі схемою  , а число кортежів у нових відношеннях  , що випливає з властивості проекції, то в середньому переглядається   кортежів, тобто є шанс зменшити число звернень до БД у ході перевірки обмежень. Крім того, розмір (довжина) переглянутих кортежів скорочується, що, як відомо, значно підвищує швидкість виконання операцій зчитування/запису. Щоправда, при такому “перетворенні” виникає ряд проблемних запитань [4].

  1. Чи буде наш новий образ насправді “еквівалентним”? Тобто, чи зможемо ми відновити початкове відношення з підтримуваних проекцій? І, по-друге, чи не втратимо ми можливості перевірити ті чи інші обмеження у проекціях без додаткових “обернених” операцій їх з’єднання?
  2. Чи варто “розщеплювати” початкове відношення, якщо у прикладних задачах, які обслуговує наша БД, необхідно отримувати повні кортежі початкового відношення?
  3. Якщо на перші два запитання одержано позитивну відповідь, але кілька еквівалентних образів БД, то який з них буде “найкращим”?

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

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

 

Література:

1. R.E. Stein. Re-Engineering the Manufacturing System: Applying the Theory of Constraints. [Текст] // Marcel Dekker, Inc.- 2003. – C.325. 

2. E.F.Codd. A Relational Model of Data for LargeShared Data Banks.[Текст] // Communications of the ACM.-1983.Vol.38, (№1). – C.17-36.

3. Дейт, К. Введение в системы баз данных [Текст] : пер. с англ. М. : Издательский дом «Вильямс», – 2001.  –1072 с.

4. Пономаренко, Л. А. Построение оптимальной последовательности соединения отношений в запросах реляционной базы данных [Текст] / Л. А. Пономаренко, С. С. Танянский, В. А. Филатов. // Системні дослідження та інформаційні технології. Міжнародний науково-технічний журнал. – 2003. – № 2. – С. 53-58.