?????? ?? ?????? ??????????? ???????? ????????? ? ????????????? ???????? ?? ?????? ?????????? ??? ?????
Національний університет“
Львівська політехніка”
ЖЕЖНИЧ ПАВЛО ІВАНОВИЧ
УДК 51.001.57+681.142.2
МЕТОДИ ТА ЗАСОБИ МОДЕЛЮВАННЯ ЧАСОВОГО ПАРАМЕТРУ В ІНФОРМАЦІЙНИХ СИСТЕМАХ НА ОСНОВІ РЕЛЯЦІЙНИХ БАЗ ДАНИХ
Спеціальність 01.05.02 – Математичне моделювання та обчислювальні методи
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Львів – 2001
Дисертацією є рукопис.
Робота виконана в Національному університеті “Львівська політехніка”, кафедра “Інформаційні системи та мережі”
Науковий керівник: доктор технічних наук
Пасічник Володимир Володимирович
Національний університет “Львівська політехніка”,
завідувач кафедри “Інформаційні системи та мережі”
Офіційні опоненти:
доктор фізико-математичних наук, професор
Кожевнікова Галина Павлівна
Львівська комерційна академія
кандидат технічних наук, старший науковий співробітник
Ващенко Неоніла Дмитрівна
Інститут кібернетики ім.Глушкова В.М. НАН України (м. Київ)
Провідна установа: Державний науково-дослідний інститут інформаційної інфраструктури Державного комітету зв’язку та інформатизації і НАН України (м.Львів)
Захист відбудеться 15 березня 2001р. о 16 год. на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м.Львів, вул.С.Бандери, 12)
З дисертацією можна ознайомитися у науково-технічній бібліотеці Національного університету “Львівська політехніка” (79013, м.Львів, вул.Професорська, 1)
Автореферат розісланий “14” лютого 2001р.
Вчений секретар спеціалізованої вченої ради
кандидат технічних наук, доцент Ткаченко С.П.
Актуальність роботи. Фактор часу є важливим у багатьох предметних областях (ПО), зокрема в таких, як бухгалтерський облік, банківська діяльність, інвентарний облік, законодавство, медичні записи, системи замовлень, аналіз історичних відомостей тощо. Традиційні бази даних (БД) дозволяють відобразити стан ПО в один конкретно визначений момент часу. Вміст БД розглядається як поточний стан предметної області. Часова база даних – це така БД, яка підтримує деякий аспект часу. Більшість прикладних систем керують історичною інформацією, тоді як традиційні системи керування базами даних (СКБД) слабо підтримують маніпулювання інформацією в розрізі часу. Дослідження в рамках дисертаційної роботи скеровані на аналіз та моделювання часових залежностей у процесах проектування та створення інформаційних систем (ІС), побудованих із використанням СКБД на основі часової моделі даних.
Часова модель даних повинна одночасно задовольняти декілька вимог:
·
Вона повинна ясно й чітко відображати часову семантику ПО, що моделюється.
·
Вона повинна бути сумісним мінімальним розширенням існуючої моделі даних, наприклад, реляційної моделі.
·
Часова модель повинна відображати усі змінні в часі особливості об’єкта.
·
Модель даних повинна бути простою в реалізації.
На ринку програмного забезпечення відсутні комерційні часові СКБД, які б повністю задовольняли ці вимоги. Основною причиною такої ситуації є складність запропонованих дослідниками часових моделей порівняно, наприклад, з класичною реляційною моделлю, на основі якої створено багато відомих комерційних СКБД.
Проблема збереження в БД часових семантичних особливостей інформації вирішується щонайменше двома шляхами:
1?
Створенням спеціалізованої часової СКБД на базі нової чи наявної часової моделі даних.
2?
Використанням однієї з наявних СКБД (наприклад, промислової СКБД реляційного типу), адаптуванням її для збереження залежної від часу інформації (наприклад, заміною традиційної інтерпретації наповнення БД).
Відсутність широко відомих комерційних часових СКБД вказує на реалізаційну складність першого способу. Тому ця дисертаційна робота присвячена реалізації другого способу, що ґрунтується на побудові відповідної часової моделі.
Зв’язок роботи з науковими програмами, планами, темами.
Робота виконана в рамках пріоритетного наукового напрямку Міністерства освіти і науки України “Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв’язку” за темами: “Дослідження процесів проектування розподілених інтелектуальних інформаційних систем прийняття рішень для слабоструктурованих проблем на основі реляційних баз даних (на прикладі сфери фінансів, бізнесу та управління)”, шифр 0196U000179; “Розробка макетів та моделей для проектування розподілених інтелектуальних інформаційних систем, алгоритмів і програм виявлення та апробації систем переваг особи, що приймає рішення, методів відсіювання та відбору альтернатив в слабоструктурованому середовищі” , шифр 0198U002391.
Метою дисертаційної роботи є розроблення методологічних основ структурного моделювання та основних принципів їх застосування для проектування інформаційних систем на основі часової реляційної моделі даних.
Мета дисертаційної роботи визначає необхідність розв’язання таких задач.
·
Аналіз особливостей моделювання предметних областей з урахуванням фактора часу.
·
Побудова часової моделі як прямого розширення реляційної моделі даних, формулювання означень операцій визначення інформаційного стану, зрізу та операцій часової реляційної алгебри як засобів маніпулювання даними.
·
Конструктивна реалізація часової моделі даних засобами традиційної реляційної моделі.
·
Побудова системи базових правил застосування структурного моделювання при створенні інформаційних систем з урахуванням фактора часу.
·
Апробація результатів дисертаційних досліджень шляхом створення прикладної інформаційної системи.
Методи досліджень. Дослідження, виконані під час роботи над дисертацією, ґрунтуються на теорії реляційних баз даних, теорії функціональних залежностей, теорії нормалізації реляційних баз даних, на апараті часової логіки, апараті реляційної алгебри, на структурній та об’єктно-орієнтованій методології проектування інформаційних систем.
Наукова новизна роботи полягає у досягненні таких результатів.
·
Сформульовано нове математично строге означення часового відношення з одним часовим параметром, яке відображає поділ ПО на інформаційні об’єкти та має просту структуру в порівнянні з визначеннями інших дослідників. Для часового інформаційного відношення подано операції визначення його стану та зрізу, які встановлюють способи інтерпретації даних. Стан часового інформаційного відношення відображає інформаційний стан класу об’єктів ПО введений автором уперше. Запропоноване поняття часового відношення узагальнено для довільної кількості часових параметрів.
·
Проведено класифікацію функціональних залежностей та ключів для часової реляційної моделі даних. Подано відповідні математичні визначення, що базуються на поняттях стану та зрізу часового інформаційного відношення. Введено поняття функціональних залежностей від часового параметра. Згідно з новими визначеннями функціональних залежностей та ключів запропоновано розширення теорії нормалізації, за допомогою якої оптимізується інформаційна схема часової бази даних за аномаліями та надлишковими даними.
·
Шляхом прямого розширення традиційних реляційних операторів та введення нових часових розширень визначено часову алгебру, яка служить засобом маніпулювання даними в запропонованій часовій реляційній моделі.
·
Уперше реалізовано часову модель даних засобами традиційної реляційної моделі, що забезпечує практичне використання цієї моделі. Введено поняття зведення часового відношення. Подано реалізації операцій визначення стану та зрізу для зведень часових відношень. Виведено математичні співвідношення між операторами часової реляційної алгебри та операторами традиційної реляційної алгебри для зведень часових відношень.
Практичне значення одержаних результатів полягає у наступному.
·
Часова модель даних конструктивно реалізована засобами реляційної моделі, що забезпечує її використання у відомих комерційних СКБД.
·
Визначено основні правила застосування методологічних основ структурного моделювання для побудови інформаційних систем з урахуванням фактора часу, сформульованих у вигляді об’єктно-часової методики.
·
Розроблено та створено інформаційну систему історичного напрямку “Електронний музей”, в якій практично апробовані результати теоретичних дисертаційних досліджень.
·
На завершення роботи подано практичні рекомендації та наведено перелік перспективних тем та напрямків подальших наукових досліджень.
Впровадження результатів роботи. Розробки впроваджені у Львівському історичному музеї, у фонді “Транспорт” м.Ужгород, у ВАТ “Оріана” м.Калуш, у СП “Галінфоком”, а також в навчальному процесі, зокрема, в курсах “Організація баз даних та знань”, “Банки і бази даних”, “Проектування розподілених інформаційних систем”, “Проектування розподілених баз даних та знань”, “Менеджмент інформаційних систем”, в яких використовувались результати досліджень як в окремих розділах, так і в циклах лабораторних та практичних робіт.
Особистий внесок здобувача. Усі наукові результати, подані у дисертації, одержані здобувачем особисто. У друкованих працях, опублікованих у співавторстві, особистий внесок автора такий: [] – визначення компоненти обліку музейних експонатів, [] – подання ПО у вигляді ієрархії об’єктів, [] – методика поділу ПО на інформаційні об’єкти, [] – правила побудови концептуальної моделі даних та системи нотацій, [] – концептуальні та логічні схеми даних інформаційної системи “Електронний музей”.
Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися на семінарах та конференціях: науковий семінар міжнародної комп’ютерної виставки “Комп’ютер і Офіс” – Львів 1997, 1998, 1999, 2000; науковий семінар міжнародної комп’ютерної виставки “Комп’ютер+Бізнес” – Львів 1997, 1998, 1999, 2000; шоста Всеукраїнська наукова конференція “Застосування обчислювальної техніки, математичного моделювання та математичних методів у наукових дослідженнях” – Львів 1999; щорічні (1996, 1997, 1998, 1999, 2000) наукові семінари кафедри ІСМ та наукові конференції викладачів і науковців ДУ “Львівська політехніка”.
Публікації. За темою дисертації опубліковано 12 друкованих праць, із них 7 – одноосібні. 10 праць опубліковані у фахових виданнях ВАК.
Структура та обсяг роботи. Дисертаційна робота складається з переліку умовних скорочень, позначень та термінів, вступу, чотирьох розділів, висновку та додатків. Загальний обсяг дисертації 150 сторінок, список літератури містить 143 найменування.
Зміст дисертації
У вступі обґрунтовано актуальність теми, визначено мету і задачі досліджень, відзначено наукову новизну та практичне значення одержаних результатів.
У першому розділі наведено огляд літературних джерел у напрямку досліджень часових баз даних та розглядаються проблеми подання фактору часу в реляційних БД.
Дослідження в області часових баз даних ведуться понад 20 років і за цей період подано описи понад 40 різних реляційних та об’єктно-орієнтованих часових моделей даних. Лише незначна частина запропонованих моделей практично реалізована, проте без широкого розповсюдження. Основною причиною цього є складність самих моделей. Таким чином, підтверджується актуальність цієї дисертаційної роботи.
У першому розділі закладено основу для моделювання часового параметру в інформаційних системах. Зазначено, що необхідно притримуватись таких трьох вимог: часова повнота, часова щільність та часовий ізоморфізм.
Часова повнота. Еволюція ПО описується скінченною множиною послідовних подій, що трапляються лише у фіксовані моменти часу, а не постійно. Ця вимога взагалі забезпечує можливість моделювання ПО за допомогою відповідної БД.
Часова щільність. Стан бази даних або множини об’єктів, що в ній відображаються, як у довільний момент часу появи подій, так і між двома сусідніми моментами появи подій, може бути виведений з інформації про усі попередні події. При визначенні стану за основу береться гіпотеза про постійність властивостей об’єкта, згідно з якою об’єкти ПО зберігають свій стан до появи наступної події.
Часовий ізоморфізм. Порядок і темп подій в БД відповідає порядку і темпу подій ПО. Ця вимога забезпечує відповідність між ПО та відповідною базою даних.
Предметна область поділяється на елементи – об’єкти, які мають певні характеристики. З плином часу в результаті появи подій частина характеристик об’єктів змінюється. Кожна подія визначається набором атрибутів. Атрибут нової події змінює значення однієї або декількох характеристик одного об’єкта ПО.
В ПО виникають факти та події. Факти відображають первинну незмінну, актуальну на будь-який момент часу інформацію ПО. Ними оперують при проектуванні схеми традиційної реляційної БД. Події несуть інформацію про зміну характеристик ПО внаслідок здійснення в часі певних дій. За ступенем складності вони класифікуються так: атомарна подія, елементарна подія та подія.
Об’єкти ПО об’єднуються в класи. Клас об’єктів – множина O об’єктів, які мають однакові характеристики. Кожному класу об’єктів Oi відповідає множина атрибутів {Ai1,…,Ain}. Події, що змінюють характеристики об’єктів класу Oi, визначаються атрибутами з множини {Ai1,…,Ain}. Щоб обчислити значення характеристик об’єкта на заданий момент часу, треба знайти стан цього об’єкта.
З теорії формальних систем стан деякої складної системи на заданий момент часу визначається набором внутрішніх характеристик. Внутрішній стан БД як складної системи на момент часу t0 однозначно визначається відповідним набором подій, що трапилися в моменти часу tt0. З точки зору моделювання поведінки ПО в часі за допомогою БД оперування станами як сукупностями відповідних подій є громіздким. Тому вводиться поняття інформаційного стану, яке значно спрощує аналіз поведінки ПО. Інформаційний стан атрибута Aij(oi) об’єкта oi на момент часу t – це значення відповідної характеристики об’єкта oi.
Стан атрибута на момент часу t одночасно несе відомості про значення атрибута в подіях, що трапилися не пізніше моменту t. Інформаційний стан атрибута – це одне значення відповідної характеристики. Стан на заданий момент часу однозначно визначається вмістом бази даних, тоді як інформаційний стан може визначатися по-різному. Інформаційний стан об’єкта oi на момент часу t – це набір інформаційних станів кожного з атрибутів:
.
Інформаційний стан – це відображення з часовим параметром, для якого автором сформульовані такі природні вимоги:
1?
Історична послідовність – на інформаційний стан об’єкта в момент часу t0 не можуть впливати події, що трапилися в момент часу t > t0.
2?
Історична щільність – якщо подія в момент часу t’ впливає на інформаційний стан об’єкта в момент t0, tt0, то будь-яка подія, що стосується цього об’єкта і трапилася в момент часу t, ttt0, повинна впливати на цей інформаційний стан.
При поданні операції визначення стану інформаційного відношення та її реалізації за допомогою операторів реляційної алгебри ці вимоги є дотримані.
У другому розділі описано часову реляційну модель даних. Вона включає визначення структур даних (часові інформаційні відношення) та засобів маніпулювання даними (часова реляційна алгебра).
Кожному атрибуту Ai з ПО поставимо у відповідність множину його можливих значень dom(Ai)=Dj – домен атрибута. Якщо Ti – часовий параметр атрибута Ai, то tdom(Ai)=dom(Ti) – множина можливих значень цього часового параметра. Часове значення атрибута A – результат багатозначного відображення A, визначеного на tdom(A), що ttdom(A): A(t)dom(A).
Нехай G=(G1,…,Gk) – множина атрибутів, яка в сукупності характеризує ідентифікатор об’єкта, XA=(A1,…,An) – атрибути об’єктів. Атрибути XA визначені на одному домені dom(T) параметра T, тобто .
Часове відношення – підмножина такого декартового добутку:
, де .
Елементи часового відношення – кортежі. Елементи декартового добутку dom(XA|T) – часові записи.
Введемо позначення: tdom() – область визначення часового параметра кортежу , tdom(r) – область визначення часового параметра відношення r.
Схема часового відношення – скінченна множина атрибутів .
Часова база даних – скінченна множина часових відношень .
Схема часової бази даних – скінченна множина схем .
Поряд з абстрактними відношеннями розглядаються відношення з конкретним наповненням. Ці відношення мають характеристики, що визначаються його вмістом: правила визначення стану та залежності даних. Тому, якщо відношення моделює історію конкретної ПО, то його називатимемо інформаційним.
Інформаційна схема відношення – це трійка =R;;}, де R – множина атрибутів, – множина правил визначення стану, – множина залежностей даних.
В інформаційній схемі відношення схема R описує логічну структуру даних, правила визначення стану вказують на способи їх інтерпретації, характерні для даної моделі ПО, а залежності описують цілісність даних інформаційної моделі.
Інформаційна схема D часової бази даних – сукупність схем .
Стан інформаційного відношення r на момент часу t – традиційне інформаційне відношення State(r|t), яке отримується з r шляхом відображення: кожному кортежу r, який відповідає об’єкту g, ставиться у відповідність кортеж традиційного відношення
, де .
Стан інформаційного відношення на заданий момент часу повертає значення характеристик усіх об’єктів, тобто інформаційний стан об’єктів. Для визначення набору події, які трапилися в заданий момент часу, вводиться поняття зрізу.
Зріз кортежу на момент часу ttdom() – множина традиційних кортежів Slice(|t) (або |t), які отримуються з шляхом відображення: кожному атрибуту з G ставиться у відповідність його значення, кожному атрибуту з XA ставиться у відповідність його часове значення на момент часу t.
Зріз інформаційного відношення r на момент часу t – традиційне відношення Slice(r|t) (або r|t), яке отримується з r шляхом відображення: кожному кортежу r ставиться у відповідність зріз |t.
Невід’ємними характеристиками вмісту інформаційних відношень є функціональні залежності (ФЗ). Вводяться три принципи визначення ФЗ в часовій реляційній моделі: через стан, через зріз та залежності від часового параметра
На інформаційній схемі підтримується еволюційна ФЗ , якщо для довільного інформаційного відношення r з цією схемою ttdom(r), 1,2r:
.
Аналогічно визначається історична ФЗ через поняття зрізу.
На інформаційній схемі підтримується об’єктна ФЗ від часового параметра , якщо для довільного інформаційного відношення r з цією схемою r 1,2 виконується умова:
.
Розглянемо інформаційну схему =R;;AXA, BXA. Нехай r – довільне інформаційне часове відношення зі схемою , та – вагові коефіцієнти A та B. Нехай в момент часу t трапляється деяка подія, яка характеризується атрибутами (A,B). Позначимо: P(A|B) – ймовірність встановлення значення атрибута A цією подією при умові, що вона встановила значення атрибута B; P(B|A) – ймовірність встановлення значення атрибута B цією подією при умові, що вона встановила значення атрибута A.
Третя часова НФ забезпечує відсутність транзитивних еволюційних та історичних залежностей неключових атрибутів від відповідно еволюційного та історичного ключа. Інформаційна схема в третій часовій НФ уникає аномалій та надлишковості даних, що трапляються при наявності транзитивних залежностей.
Часова НФ Бойса-Кодда, забезпечує залежність кожного з неключових атрибутів інформаційної схеми лише від ключа.
Об’єктно-часова НФ інформаційної схеми передбачає наявність об’єктної залежності від часового параметра і забезпечує таке обмеження: в один момент часу з одним об’єктом ПО може трапитися лише одна подія.
Інформаційна схема перебуває в достатньо синхронізованій НФ, якщо атрибути A1,…,An є достатньо синхронними.
Якщо інформаційна схема не перебуває в одній з часових НФ (крім першої), то вона “оптимізується” декомпозицією – розділенням на декілька схем.
Для маніпулювання даними описується часова реляційна алгебра. Вона містить розширення операторів традиційної реляційної алгебри для випадку часової моделі даних, а також нові часові оператори.
Фактичне або пряме розширення бінарного оператора – оператор ’ часової реляційної алгебри такий, що виконується:
.
Прямі розширення над традиційними відношеннями працюють аналогічно до традиційних операторів. Крім прямих розширень традиційних операторів розглядаються оператори, які не відповідають попереднім визначенням.
Описана часова реляційна модель даних узагальнюється для довільної кількості часових параметрів. Нехай T1,…,Tq – часові параметри.
Узагальнене часове відношення – підмножина декартового добутку:
,
де .
Усі викладки щодо схеми, стану та зрізу відношення справджуються для узагальнених відношень, якщо замість атрибута T поставити XT=(T1,…,Tq). Поняття функціональних залежностей для узагальнених часових інформаційних відношень визначаються аналогічно, як і у випадку відношень з одним часовим параметром. Крім того мають сенс функціональні залежності, визначені лише для підмножини набору часових параметрів .
Твердження. Якщо на узагальненому часовому інформаційному відношенні r підтримується деяка функціональна залежність , визначена для підмножини , , то очевидно виконується така сама функціональна залежність, визначена для всього набору часових параметрів.
Функціональні залежності для узагальнених часових інформаційних відношень не змінюють формулювання означень ключів. Тому НФ для узагальнених часових відношень формулюються аналогічно, як у випадку одного часового параметра. Оскільки мають сенс функціональні залежності, визначені для підмножини часових параметрів, то й нормальні форми також передбачають відповідні формулювання.
У третьому розділі розглядаються методи реалізації часової моделі даних засобами реляційної моделі та визначається процес проектування архітектури інформаційної системи. Відповідні викладки оформлені у вигляді об’єктно-часової методики проектування ІС.
Запропонована часова реляційна модель має ряд переваг.
1?
Часова реляційна модель є простішою порівняно з багатьма існуючими моделями. Це досягається конструктивним визначення поняття часового відношення.
2?
Поняття часового відношення є достатньо гнучким та потужним засобом збереження та інтерпретації залежних від часу даних, оскільки воно орієнтоване на збереження інформації про події, а не про стани предметної області.
3?
Часова реляційна модель легко узагальнюється в напрямку збільшення кількості часових параметрів, оскільки усі часові параметри вважаються рівноправними.
4?
Часові відношення конструктивно реалізуються за допомогою традиційних відношень.
Проектування ІС полягає у побудові відповідної часової інформаційної моделі ПО засобами реляційних баз даних. Для цього основні поняття часової моделі зводяться до понять традиційної реляційної моделі даних.
Нехай r – часове інформаційне відношення зі схемою =R;;R=(G;XA|XT), де G=(G1,…,Gk), XA=(A1,…,An), XT=(T1,…,Tq).
Зведення часового інформаційного відношення r – це традиційне відношення r+ зі схемою R+=(G,XA,XT), яке отримується з r шляхом відображення: кожному кортежу r ставиться у відповідність множина кортежів відношення r+:
.
Зведення часового відношення – це традиційне відношення, що розглядається як часове відношення із застосуванням операції традиційної реляційної алгебри.
Стан та зріз зведення часового відношення – це операції над зведенням часового відношення, результатом яких є традиційні відношення:
, ,
де та – відповідно стан та зріз зведення r+.
Зріз завжди визначається за одним правилом:
.
З означення операції визначення стану випливає, що стан відношення на один момент часу t може визначатись по-різному. Позначимо клас агрегуючих правил AR (Aggregation Rule). Вважаємо, що відношення r має один часовий параметр. Стан часового відношення, визначений за одним з правил цього класу, позначимо:
,
де t – момент часу визначення стану, AGGi – агрегуюча функція, що відповідає атрибуту Ai, tp – часовий термін для визначення подій, що впливають на стан.
В результаті отримуємо традиційне відношення зі схемою (G,A1,…,Am), яке складається з наступних кортежів:
.
Для реалізації часової алгебри засобами реляційної алгебри оператори часової реляційної алгебри поділимо на дві групи: оператори, побудовані за прямим розширенням, та інші оператори.
Розглянемо деякий бінарний оператор традиційної реляційної моделі даних. Якщо ’ – відповідний розширений оператор часової реляційної алгебри, то аналогічний оператор для зведень часових відношень позначимо ’+. Нехай r+ та s+ – зведення часових інформаційних відношень r та s. Оператор ’+, побудований за прямим розширенням, формально повинен задовольняти умову:
.
Твердження. Прямі розширення операторів часової алгебри для зведень часових відношень реалізуються відповідними операторами традиційної алгебри.
Інші оператори часової алгебри реалізуються через комбінації операторів вибірки, проекції та поєднання традиційної алгебри.
Поняття зведення часового відношення в об’єктно-часовій методиці чітко обмежує рамки визначення структур даних при побудові часової моделі інформаційної системи. А саме, дозволяється оперувати або традиційними відношеннями, або зведеннями часових відношень.
Математичного апарату зведень часових відношень та операторів часової алгебри ще недостатньо для побудови “якісної” часової моделі ІС. Тому в об’єктно-часовій методиці також визначається процес проектування всієї архітектури інформаційної системи. Розрізняють три рівні архітектури системи: концептуальний рівень – рівень абстрактної моделі, логічний рівень – рівень користувача, фізичний рівень – рівень збереження інформації на фізичних носіях зберігання.
У випадку часової бази даних концептуальна модель відображає загальну схему об’єктів ПО та взаємозв’язків між ними. Цей рівень проектується за допомогою ER-діаграм (Entity-Relationship) – діаграм сутність-взаємозв’язок. Сутність – це неподільний набір атрибутів. Між сутностями встановлюються взаємозв’язки: один-до-одного, один-до-багатьох, багато-до-багатьох. Сутності та інформаційні об’єкти пов’язані між собою. Одна сутність може відображати один клас об’єктів, кожен клас об’єктів зображається однією або кількома взаємозв’язаними сутностями. Клас об’єктів ПО, який описується однією сутністю, є атомарним. Модель ПО подається у вигляді ієрархії класів об’єктів – деревовидного графа з коренем. Причому коренем виступає уся ПО, а кінцевими вершинами – усі атомарні класи об’єктів.
Складений клас об’єктів O – клас, до якого в ієрархії є підчеплене деяке піддерево.
Об’єднуючи визначення атомарного та складеного класу об’єктів, загальна структура класу об’єктів O(i) ІС, який розташований на i-рівні ієрархії, подається як сукупність атомарних та складених класів об’єктів (i+1)-рівня:
,
де – основна частина класу, яка містить атомарних класів об’єктів (i+1)-рівня, – описова частина, яка характеризується складеними класами об’єктів (i+1)-рівня, NL – висота дерева ієрархії. Якщо складений клас об’єктів описується лише атомарними класами, то він є елементарним. Якщо ж складений клас об’єктів описується лише складеними класами, то він є узагальненим.
Логічний рівень – це інформаційна схема бази даних, яка будується на основі концептуальної моделі даних. Логічний рівень фактично слугує інтерфейсом між користувачем та базою даних. На логічному рівні подаються схеми таблиць та переглядів, які з точки зору традиційної реляційної моделі виступають відношеннями. Однак таблиця – це відношення, яке прямо служить для збереження інформації у базі даних. А перегляд – це відношення, яке отримують із таблиць чи інших переглядів за допомогою операторів реляційної алгебри.
Фізичний рівень – це власне база даних. Подання даних на фізичних носіях залежить від конкретної СКБД, яка використовується при роботі з базою даних. Якщо припустити, що логічну модель даних треба реалізувати за допомогою СКБД реляційного типу, яка підтримує мову SQL, то фізична реалізація логічної моделі полягає у виконанні команд SQL, необхідних для відображення усіх елементів логічної моделі у фізичній базі даних.
У четвертому розділі описується інформаційна система “Електронний музей”, при проектуванні та розробленні якої було використано теоретичні результати дисертаційних досліджень перших трьох розділів. Система побудована за об’єктно-часовою методикою.
Систему “Електронний музей” розроблено та впроваджено у Львівському історичному музеї у рамках відповідної угоди між кафедрою “Інформаційні системи та мережі” НУ “Львівська політехніка” та Львівським історичним музеєм.
При проектуванні інформаційної системи використовувались елементи узагальненої часової моделі даних. Наявність великої кількості атрибутів (близько 50) для експонату, залежних від різних часових параметрів вимагала ретельних досліджень щодо їх синхронності в дійсному часі. В цьому напрямку проводився статистичний аналіз даних та було використано досвід фахівців музейної справи.
Опис інформаційної системи на концептуальному рівні містить такі елементи: функціональну структуру, ієрархію класів та концептуальні схеми даних.
<Рисунок>
Рис. 1. Контекстна діаграма потоків даних ІС “Електронний музей”.
Функціональна структура системи подається за допомогою діаграм потоків даних (Data Flow Diagram). Аналіз предметної області показав, що робота зі системою повинно базуватись на трьох функціях: “Облік нормативної інформації”, “Облік колекцій експонатів” та “Облік експонатів”. Для кожної з цих функцій окремо подаються діаграми потоків даних. Загальна схема функціонування системи зображена на контекстній діаграмі потоків даних (див. рис. 1).
Ієрархія класів показує поділ ПО на класи об’єктів (див. рис. 2). Вона побудована на основі діаграм потоків даних і служить для виділення в інформаційній схемі бази даних “Електронного музею” окремих відношень (як традиційних, так і часових). Деталізація класів об’єктів за допомогою окремих відношень відображається у відповідних концептуальних схемах – діаграмах “сутність-відношення”.
Елементи ієрархії, які не є листковими (з піддеревом), відповідають узагальненим об’єктам ПО. Листкові елементи відповідають елементарним об’єктам. На концептуальній схемі вони відображаються за допомогою одного або декількох зв’язаних відношень.
На логічному рівні системи відображаються інформаційні схеми даних: таблиць та переглядів. На рис. 3 подано схеми основних таблиць для обліку експонатів. Структури таблиць побудовано відповідно до третьої часової нормальної форми, часової нормальної форми Бойса-Кодда, об’єктно-часової та синхронізованої нормальних форм. Перегляди окремо відображають стан експонатів по кожному з наборів достатньо синхронних атрибутів.
Програмна реалізація ІС “Електронний музей” здійснювалась засобами СКБД Microsoft Access 2000. У базі даних електронного музею за допомогою мови SQL створено необхідні структури даних, засобами мови програмування VBA побудовано користувацькі форми та готові до друку звіти. Система дозволяє опрацьовувати мультимедійну інформацію, яка є одним із способів опису експонатів.
У додатках наводяться сценарії створення таблиць та переглядів інформаційної системи “Електронний музей”, матеріали про впровадження результатів роботи.
Основні результати роботи.
Дисертантом отримано такі основні результати.
·
Проведено класифікацію інформації ПО за відношенням до часу, що виступає підґрунтям для побудови часової моделі даних. ПО ділиться на елементи – об’єкти, з якими пов’язуються факти та трапляються події. Введено поняття інформаційного стану, яке відображає значення характеристик об’єктів ПО на заданий момент часу.
·
Сформульовано нове математично строге означення часового відношення через домени атрибутів та часового параметра, яке відображає поділ ПО на інформаційні об’єкти та має просту структуру в порівнянні з визначеннями інших дослідників. Виділено операції стану для визначення інформаційного стану об’єктів ПО та зрізу для визначення набору подій, які трапилися в заданий момент часу. Стан та зріз часового інформаційного відношення встановлює можливі способи інтерпретації даних. Досліджено узагальнення часового відношення у випадку довільної кількості часових параметрів, що забезпечує збереження та аналіз інформації в розрізі декількох незалежних часових вимірів.
·
Розширено традиційну теорію нормалізації для оптимізації схем часових інформаційних відношень, що дозволяє уникати різних аномалій та надлишковості даних.
·
Описано часову реляційну алгебру, в яку ввійшли як прямі розширення традиційних реляційних операторів, так і нові часові оператори. Оператори часової алгебри служать засобом маніпулювання даними.
·
Розроблено об’єктно-часову методику проектування інформаційної системи на основі часової бази даних. Як структури даних застосовуються поняття зведень часових відношень до традиційних. Інформаційний стан ПО визначається за допомогою агрегуючих правил визначення стану. Маніпулювання даними проводиться за допомогою операторів часової алгебри, реалізованих через оператори традиційної алгебри. Побудова інформаційної системи здійснюється із застосування основ структурного моделювання та згідно до чіткої системи нотацій.
·
Розроблено історичну інформаційну систему “Електронний музей”, в якій на практиці відображено основні результати дисертаційних досліджень.
Результати дисертації опубліковані в таких роботах.
1?
Жежнич П. Дослідження методів побудови інформаційних систем на основі часових баз даних. //Львів: Вісник ДУ “Львівська політехніка”, Інформаційні системи та мерержі, №315, 1997. – с.43-50.
2?
Жежнич П. Періодичність в часових базах даних. //Львів: Вісник ДУ “Львівська політехніка”, Інформаційні системи та мерержі, №330, 1998. – с.99-108.
3?
Жежнич П. Проблеми подання часових даних в інформаційних системах (на прикладі системи “Електронного музею”). //Львів: Вісник ДУ ім.І.Франка, “Задачі та методи прикладної математики”, №50, 1998. – с.95-98.
4?
Жежнич П. Часові аспекти інформаційної системи “Пошук”. //Львів: Вісник ДУ “Львівська політехніка”, Інформаційні системи та мерержі, №330, 1998. – с.92-98.
5?
Пасічник В.В., Жежнич П.І., Пелещишин А.М., Чайковський Б.М. Застосування сучасних інформаційних технологій у музейній справі. //Львів: Вісник ДУ “Львівська політехніка”, Інформаційні системи та мерержі, №330, 1998. – с.109-112.
6?
Жежнич П.І. Реляційні бази даних з часовою інтерпретацією. //Львів: Вісник ДУ "Львівська політехніка", Інформаційні системи та мерержі, №383, 1999. – с.62-72.
7?
Пасічник В.В., Жежнич П.І., Кравець Р.Б., Пелещишин А.М. Основні правила побудови семантично відкритих інформаційних систем. //Львів: Вісник ДУ "Львівська політехніка", Інформаційні системи та мерержі, №383, 1999. – с.84-95.
8?
Пасічник В.В., Жежнич П.І., Кравець Р.Б., Пелещишин А.М. Семантично відкриті інформаційні системи. //Львів: Вісник ДУ "Львівська політехніка", Інформаційні системи та мерержі, №383, 1999. – с.73-84.
9?
Жежнич П.І. Функціональні залежності в часовій реляційній моделі. //Львів: Вісник НУ "Львівська політехніка", Інформаційні системи та мережі, №406, 2000. – с.84-90.
10?
Жежнич П.І., Пелещишин А.М. Історична інформаційна система “Електронний музей”. //Львів: Вісник НУ "Львівська політехніка", Інформаційні системи та мережі, №406, 2000. – с.91-100.
11?
Жежнич П.І. Кравець Р.Б., Пелещишин А.М. Семантично відкриті інформаційні системи (основні правила побудови). //Львів: ДУ ім.І.Франка, 6-а Всеукр. наук. конф. “Застосування обчислювальної техніки, математичного моделювання та математичних методів у наукових дослідженнях”, Тези доп., 1999.
12?
Жежнич П.І. Стан та зріз у часовій реляційній моделі. //Львів: ДУ ім.І.Франка, 6-а Всеукр. наук. конф. “Застосування обчислювальної техніки, математичного моделювання та математичних методів у наукових дослідженнях”, Тези доп., 1999.
Анотації
Жежнич П.І. . – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – “Математичне моделювання та обчислювальні методи”. – Національний університет “Львівська політехніка”, 2001.
Дисертацію присвячено питанням моделювання часового параметру в інформаційних системах на основі реляційних баз даних. Побудовано часову реляційну модель даних. Сформульовано нове математично строге визначення часового відношення. Введено нові типи функціональних залежностей та ключів. Викладено теорію нормалізації для оптимізації інформаційних схем часових відношень. Визначено часову реляційну алгебру. Узагальнено поняття часового відношення для довільної кількості часових параметрів. Розроблено методи реалізації часової моделі даних засобами реляційної моделі. Розроблено принциапи застосування основ структурного моделювання при побудові інформаційних систем на основі часової реляційної моделі. Розроблено інформаційну систему історичного напрямку “Електронний музей”, яка на практиці відображає результати теоретичних дисертаційних досліджень.
Ключові слова: часові бази даних, часова реляційна модель, часові залежності, розподілені інформаційні системи.
Жежнич П.И. Методы и средства моделирования временного параметра в информационных системах на основе реляционных баз данных. – Рукопись.
Диссертация на соискание научной степени кандидата технических наук за специальностью 01.05.02 – “Математическое моделирование и вычислитеньные методы”. – Национальный университет “Львовская политехника”, 2001.
Диссертация посвящена вопросам моделирования временного параметру в информационных системах на основе реляционных баз данных. Построена временная реляционная модель данных. Сформулировано новое математически строгое определение временного отношения. Введены новые типы функциональных зависимостей и ключей. Изложена теория нормализации для оптимизации информационных схем временных отношений. Определена временная реляционная алгебра. Обобщенно понятие временного отношения для произвольного количества временных параметров. Разработаны методы реализации временной модели данных средствами реляционной модели. Разработаны принципы применения основ структурного моделирования при построении информационных систем на основе временной реляционной модели. Разработана информационная система исторического направления “Электронный музей”, которая на практике отображает результаты теоретических диссертационных исследований.
Ключевые слова: временные базы данных, временная реляционная модель, временные зависимости, распределенные информационные системы.
Zhezhnych P.I. Methods and algorithms of temporal parameter modeling in information systems based on relational databases. – Manuscript.
Thesis for a Ph.D. science degree by specialty 01.05.02 – “Mathematical modeling and calculating methods”. – National university "Lvivska Polytechnika", Lviv, 2001.
The thesis is dedicated to problems of temporal parameter modeling in information systems based on relational databases. Scientists investigate a temporal database area during more than 20 years and proposed more than 40 different relational and object-oriented temporal data models. These models were not realized in popular commercial DBMSs due to their complexity. The most research directions of the thesis are concentrated on qualitative temporal relational data model building and its implementation with relational data model.
At the beginning problems of time-depended information storing in databases were considered. We emphasize three requirements that should be followed during data domain modeling: temporal completeness, temporal density and temporal isomorphism. Time-depended information was classified so whole data domain is divided on object. Data domain facts are bounded with objects and events referring to these objects. Each object has characteristics, which can be changed with events. An object information state is used to calculate values of these characteristics. An information state has to satisfy following requirements: historical consecution and historical density.
In the second chapter we propose temporal relational data model based on a notion of temporal relation. The temporal relation was defined as Cartesian product of attributes’ and time parameter’s domains. Beside the abstract temporal relations informational relations are considered. To know object characteristics’ values at a time moment a relation state has to be calculated. To choose a set of events referring to the object and happened at the time moment a relation slice has to be calculated. Analyzing informational relations we classified temporal functional dependencies: state dependencies, slice dependencies and dependencies from time parameter. Following these dependencies’ definitions new formulations of first, second, third and Boyce-Codd normal forms were proposed. Also object-temporal and synchronized normal forms were introduced. Using state and slice operations the conventional relational algebra was extended to temporal data model requirements. We considered straight, static and temporal extensions of relational operators. At the end of second chapter the temporal relational data model was generalized up to any number of temporal parameters. For generalized relations two new operations were introduced: temporal state and temporal slice. Functional dependencies based on whole set of temporal parameters and its subset are considered. So we propose temporal normal forms using whole set of temporal parameters and its subset as well.
In the third chapter an object-temporal methodic of information system design was considered. The methodic is based on a concept of transformed temporal relation. A transformed relation is a convenient relation but with temporal interpretation. A transformed relation has state and slice, temporal state and temporal slice. A transformed relation state can be calculated using several rules. For this reason we introduce class of state calculation aggregation rules and implemented it with relational algebra operators. Also operators of temporal relational algebra were implemented. The second part of the chapter was dedicated to information system architecture design. We distinguish three levels of the architecture: a conceptual level (an abstract model level), a logical level (an user level) and a physical level (a data store level). For temporal databases the conceptual model represents a general schema of data domain objects and relationships between them. The logical level is an information schema of database. The physical level is a database stored on data medium.
In the fourth chapter we described an information system “Electronic museum” designed according to object-temporal methodic. At a conceptual level the information system description includes functional structure (represented with Data Flow Diagrams), classes hierarchy and conceptual data schemas (represented with Entity-Relationship Diagrams). At a logical level database schema was given. It describes logical structure of tables and views have to be stored in the database. The system was implemented with DBMS Microsoft Access
