Базові моделі даних

1.

Лекція 3.
Базові моделі даних
Мета лекції:
Розглянути основні види моделей даних і їх характеристики.
План лекції:
1. Інфологічна модель
2. Ієрархічна модель
3. Квадратомічне дерево
4. Реляційна модель
12.12.2016
1

2.

3.1. Інфологічна модель
Інфологічна модель дає формалізований опис предметної області незалежно від структур
даних. Інфологічна область моделювання даних охоплює природні для людини концепції
відображення реального світу .
Одне з основних понять інфологічної моделі - об'єкт. Це поняття пов'язане з подіями:
виникнення, зникнення і зміна. Об'єкти можуть бути атомарними чи складовими .
А т о м а р н и й об'єкт - це об'єкт певного типу, подальше розкладання якого на більш
дрібні об'єкти усередині даного типу неможливе .
С к л а д о в и й об'єкт включає множину об'єктів, кортежі об'єктів.
Застосовуючи це визначення, рекурсивно можна отримати довільну структуру складових
об'єктів.
Зазвичай об'єкт має деяку властивість або взаємозв'язок (зв'язок) з іншими
об'єктами. Властивість може не бути визначене формально, а лише охарактеризовано як
деяке твердження з приводу множини об'єктів.
Мета інфологічного моделювання - формалізація об'єктів реального світу
предметної області і методів обробки інформації відповідно до поставлених задач
обробки і вимог представлення даних природними для людини способами збору і
представлення інформації.
Інфологічна модель припускає можливість представлення будь-якого об’єкту з якоюсь
часткою вірогідності, тобто у вигляді аналога думки.
12.12.2016
2

3.

Інфологічна модель може включати ряд компонентів (рис. 3.1).
І
н
ф
о
л
о
г
і
ч
н
а
м
о
д
е
л
ь
Опис об'єктів
Опис предметної
області
Опис зв’язків між об’єктами
Опис вихідних даних
Опис лінгвістичних вимог
Опис методів
обробки
Опис алгоритмічних зв’язків
Обмеження цілісності
Опис
інформаційних
потреб
користувача
Види вихідних даних
Основними компонентами інфологічної
моделі є :
опис предметної області;
опис методів обробки;
опис інформаційних потреб
користувача.
Форми представлення
Рис. 3.1. Основні компоненти інфологічної моделі
Інфологічна модель носить описовий характер.
В силу деякої довільності форм опису в даний час не існує загальноприйнятих
способів її побудови.
Через це при побудові інфологічної моделі використовують:
аналітичні методи,
методи графічного опису,
системний підхід.
12.12.2016
3

4.

3.2. Ієрархічна модель
До найпростіших, структурно визначених, відноситься ієрархічна модель. В цій моделі
даних зв'язки між її частинами є жорсткими, а її структурна діаграма повинна бути
впорядкованим деревом
Одне із важливих понять для цієї моделі - рівень.
корінь,
стовбур,
Для опису різних рівнів застосовують поняття:
гілки,
листя,
ліс
Це підкреслює схожість структури моделі із структурою дерева.
Вузол
Дуга
1
2
5
4
3
6
7
8
9
10
Граф ієрархічної моделі (її схемне представлення) включає два
типи елементів: дуги і вузли (або записи) (рис.3.2). Дуги сполучають
різні вузли між собою. Дуги, відповідні функціональним зв'язкам,
повинні бути завжди направлені від коріння в листя дерева, тобто
вони є орієнтованим графом. Така структурна схема називається
ієрархічним деревом визначення або деревом визначення.
Рис.3.2. Приклад графа
Дуга дерева визначення, відповідна функціональному типу зв'язку, називається зв'язком
вихідний - породжений.
Між двома типами записів в ієрархічній моделі може бути не більше одному такому зв'язку.
Дуга виходить з типу батьківського (що породжує) запису і заходить в тип дочірнього
(породженого ) запису.
12.12.2016
4

5.

У найпростішому випадку ієрархічна модель є описом процесу або системи, що
складається з сукупності рівнів, зв'язаних однією дугою.
Перший породжений запис називають кореневим (рідше смолом), проміжні записи гілками, записи самого нижнього рівня ієрархічної моделі — листям.
Поняття коренева, стовбур, гілки, листя визначає тип запису в ієрархічній моделі .
Ієрархічний шлях, або маршрутизація, - це послідовність типів записів, що починається з
типу кореневого запису, в якому типи записів виступають позмінно в ролях початкового і
породженого .
1. (1, 2, 5);
Для графа (рис.3.2) шляхи:
2. (1, 2, 6);
3. (1, 3, 7);
4. (1, 3, 8);
5. (1,4,9);
6. (1,4,10).
1
2
5
4
3
6
7
8
9
10
Рис.3.2. Приклад графа
Відома програмістам послідовність "диск - коренева папка – вкладена папка - програма"
- характерний приклад ієрархічної моделі (рис.3.3)
Іноді структуру
ієрархічної моделі
називають Є-деревом
Рис.3.3. Приклад маршрутизації в ОС Windows
Ієрархічним моделям даних властиві два внутрішні обмеження:
перше - всі типи зв'язків повинні бути функціональними;
друге - структура зв'язків повинна бути деревовидною.
Очевидний недолік ієрархічних моделей - зниження часу доступу при великому числі рівнів, тому в ГІС
не використовують моделі при великому числі рівнів (більше 10).
12.12.2016
5

6.

3.3. Квадратомічне дерево
Ієрархічна структура даних, відома як квадратомічне дерево, використовується для
накопичення і зберігання географічної інформації. В цій структурі двомірна геометрична
область рекурсивно підрозділяється на квадранти, що визначило назву даної моделі.
На рис. 3.4 показаний фрагмент двовимірної області QT, що
складається з 16 пікселів. Кожний піксель позначений цифрою.
Вся область розбивається на чотири квадранти: А, В, С, D.
Кожний з чотирьох квадрантів є вузлом квадратомічного дерева.
Великий квадрант QT стає вузлом більш високого ієрархічного
рівня квадратомічного дерева, а менші квадранти з'являються на
більш низьких рівнях
Рис.3.4. Фрагмент двовимірної області
Технологія побудови квадратомічного дерева заснована на рекурсивному поділенні квадрата
на квадранти і підквадранти до тих пір, поки всі підквадранти не стануть однорідними по
відношенню до значення зображення (кольору) або поки не буде досягнутий наперед
зазначений якнайменший рівень дозволу.
На рис. 3.5 показано квадратомічне дерево, побудоване за даними рис. 3.4.
Як видно, ця структура являє собою класичний приклад Є-дерева.
Моделі, засновані на квадратомічних деревах, забезпечують розрахунки
площ, розпізнавання образів, визначення сусідства, перетворення
відстаней, розподілення зображень, згладжування даних і посилення
краєвих ефектів.
Внаслідок цього з'явилася можливість використовувати квадратомічні
дерева для зберігання географічних даних.
Рис.3.5. Квадратомічне дерево у
вигляді Є-структури
Перевага представлення, заснованого на покажчиках, полягає в тому, що воно виражає тільки
значущу частину повного квадратомічного дерева.
12.12.2016
6

7.

3.4. Реляційна модель
У сучасних інформаційних системах і базах даних найбільш широко представлені
реляційні моделі (РМ)
РМ спирається на систему понять, найважливіші з яких - таблиця, відношення, стовпець,
рядок, первинний ключ, зовнішній ключ, домен
Таблиця складається із рядків і стовпців, и має ім'я унікальне усередині бази даних.
Таблиця відображає тип об'єкту реального світу (сутність), а кожний її рядок - конкретний
об'єкт .
Доменом називається сукупність значень, що не повторюються в одному стовпці.
Основним засобом структуризації даних в реляційній моделі є відношення (relation).
Відношення можна визначити як декартовий добуток доменів .
Таблиця має стовпці і рядки (записи). Кожний запис має набір атрибутів. Записи кожного
типу утворюють таблицю або відношення.
Кожний рядок - це запис або кортеж .
Кожний стовпець - це атрибут .
Діапазон допустимих значень (домен) визначається для кожного атрибуту.
Ступінь відношення - число атрибутів у таблиці :
один атрибут - унарне відношення;
два атрибута - бінарне відношення,
n атрибутов – n - арне відношення.
Ключ відношення - це підмножина атрибутів, що має наступні властивості:
унікальну ідентифікацію;
не надмірність;
ні один із атрибутів ключа не можна вилучити, не порушивши його
унікальність.
Первинний атрибут відношення - це атрибут, присутній, принаймні, в одному ключі,
усі інші атрибути не первинні.
12.12.2016
7

8.

Реляційна модель є табличною моделлю, деякі типи зв'язків між відношеннями можуть
представлятися у схемі неявно .
Висновки
1. Для ефективної роботи ГІС необхідний обґрунтований вибір
базових моделей даних і створення інтегрованої інформаційної основи.
2. Вибір моделей даних здійснюється при аналізі області вживання
ГІС .
3. Організація моделей даних ГІС для управління дозволяє
вирішувати задачі, які раніше входили в сферу діяльності АСУ .
4. ГІС є системою більш широкого вживання в порівнянні з АСУ. Вона
використовується в областях, в яких АСУ не застосовувалися, - це
військова справа, навігація, екологічний моніторинг, розвідка підземних
копалин, аналіз мереж тощо .
12.12.2016
8