Розвиток логічних моделей даних, Інші СУБД, Бази даних, статті

Класифікація логічних моделей даних


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

Розрізняють чотири логічні моделі даних:


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


посилальна модель даних з іменами (ідентифікаторами) даних.


До навігаційним моделям даних відносяться ієрархічна, мережева і багатовимірна логічні моделі, до посилальної моделі даних – реляційна модель.

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

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

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


У 1970 році Е. Ф. Коддом теоретично обгрунтував, що більш універсальним рішенням в області баз даних є посилальна модель: "Реляційна модель надає засоби опису даних на основі тільки їх природної структури, тобто без потреби введення будь-якої додаткової структури для цілей машинного вистави "[1].

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

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

Ефективність посилальної моделі даних


Перевага теоретичної посилальної моделі перед навігаційної моделлю даних засноване на двох постулатах:


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

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

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

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

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

Для локалізації місця розташування ідентифікаторів даних застосовують В+-Дерева, в складі яких окремий атрибут відбивається в декількох вузлах у напрямку ієрархічному зв'язку, що веде до одного з листів дерева, де, крім цього атрибута, відображається список пов'язаних з ним ідентифікаторів даних [2]. У загальному випадку атрибут відображається у кількості вузлів, що дорівнює половині від числа рівнів В+-Дерева.

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

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

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

Ефективність навігаційної моделі даних


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

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

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

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

K произв. = M ссыл. / M навиг. + N ссыл. / N навиг.,

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

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

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

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

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

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

Кінцева мета розвитку логічних моделей даних


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

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

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

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

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

Єдиний недолік класичної багатовимірної моделі даних – "вибухового" зростання осередків багатовимірного простору при збільшенні числа вимірювань і кількості координат у складі вимірювань. Обсяг багатовимірного простору при цьому зростає по експоненті. Кількість осередків, заповнених NULL-значеннями, на порядки перевищує кількість осередків, заповнених реальними даними. З метою стиснення багатовимірного простору використовується прийом, реалізований в навігаційній моделі даних – адресні покажчики, що зв'язують в тому чи іншому порядку клітинки зі значимими даними. Стислий багатовимірний простір, в свою чергу, вимагає заміни механізму пошуку, заснованого на одноразових переміщеннях уздовж осей вимірювань, на механізм пошуку, заснований на ієрархічних структурах.

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

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

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

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*