автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методы и средства представления и обработки информации с временным параметром в реляционных базах данных



КИ1ВСБКА MICbKA ДЕРЖАВНА АДМШСТРАЩЯ 1НСТИТУТ ПРИКЛАДН01 1НФ0РМАТИКИ

На правах рукошсу УДК 681.3

ЛБ1НЕЦБ ЯРОСЛАВ ВОЛОДИШРОВИЧ

МЕТОДИ ТА ЗАСОБИ ПРЕДСТАВЛЕНИЯ ТА ОБРОБКИ 1НФОИЩЦ1 3 ЧАСОВИМ ПАРАМЕТРОМ В РЕЛЯЦ1ИНИХ БАЗАХ ДАНИХ

Спец1альн1сть 05.13.17 - Теоретичн! основи 1нформатики

Автореферат дисертацП на здобуття вченого- ступени кандидата ф1зико-матвматичних наук

Khïb -1994

Робота виконана в державному ун1верситет!

"Льв1вська пол1техн!ка"

Науковий кер!вник: д.т.н. В.В.Пас1чяик-—----

0ф1ц1йн1 опоненти:

д.ф.-м.н., проф. Г.Г. Цвгелик (м.Льв!в) к.ф.-м.н., В.В.КсШнько (м.Ки!в)

Пров1дна орган!зац1я - 1нститут програмних систем АН УкраКни

на зас1данн! Спец1ал1зовано1 Ради Д 166.01.01 в 1нститут1 прикладно! 1нформатики (1ПР1Н) за адресов: 252004, м. Ки1в, вул. Червоноарм1йська 23-0.

3 дисертаШею мохна ознайомитись в С10л1отец1 1нституту прикладно! 1нформатики.

Автореферат роз 1слания _'_ 1994 р.

ВчениЯ секретар

(м.Ки!в)

год.

Спешал1зовано1 Ради Л 166.01.01

ЗАГАЛЪНА ХАРАКТЕРИСТИКА. РОБОТИ.

Актуальн!сть проблеми. Релящйна модель даних протягом останн!х рок!в здобула загальнв визнання як зручний зас!б для 1нформац!йного моделювання д!йсност1. Однак, поряд з багатьма перевалами, реляц!йна . модель в II традиц!йному розум!нн! та СКБД, побудован! на II основ! мавть ряд недол!к!в. Зокрема, виникають труднощ! при моделиванн! еволюцП • об'ект!в реально! . д!йсност1, тобто в!дсутн1 ефективн! метода та засоби представления часових П8раметр1в. Явне введения часового контексту та його в!добракення в конструкц!ях 1нформац!йних систем передбачае розробку спецхальних засоб!в, оск!лыш часова розм!рн!сть, часов! атрибута в!дношень бази даних мають особливу семантику. Введения часових моделей означав нео0х!дн1сть збереження в баз! даних значень властивостей об'ект!в, як! втратили достов!рн!сть. Концепц1я несуперечлгоост! реляц!йно! бази даних, яка означав недопустим!сть представления в н!й одночасно деякого факта I його заперечення, повинна бути розширена можлив!стю представления стан!в бази даних, як! в!дпов1дають р!зним дискретним момегстам часу.

В результат! анал!зу л!тературних джерел можна ввд1лити два основн! п!дходи до представления часу в реляц!йних базах даних: введения часового параметру на р!вн! атрибут!в та часова параметризац!я кортех!в. Кокен з вказаних п!дход1в мае ряд невир1шених питань,' наприклад:

- проблема надлкшковост! представления даних та часово! параметризац1I бзгатоатрибутних властивостей;

- реал!зац!я нав1гац!1 на р!вн! !сторИ об'ектз та на р!вн!'еволюцИ предметно! облает!.

Отжв проблема розширення традищйно! рвлящйно! моде л!

2£3 адекватного ¡.гаыигулювання часовою 1Ефориац!ею е актуальною як в теоретичному, так 1 в прикладному аспокт1.

Мата дисертааШю! робота полягег в розробц! таоротичшд та приклддних аспект! в ггроектування, представления та обробки еволюцн об'ект!в реально! д1йсност1 в базах даних, побудованих на основ! в1дпов1дао1'0 розширення реляд1йно1 модел! даних. Виходячи з цього, досл!даення проводились в настуших основних напрянках:

- анал1ткчна оц!нка основних результатов в облает! роляцНШих моделей даних, роззшрених для представления ифэрмац! I з часовими параметрами ;

- '!нтеграц!я р!зноман!тних п!дход!в до моделювання часу в !н35ормац!йних системах та побудова часовой рвляцШю! модел! даних. Розробка ун1ф1ковано! системи основних понять, казначень та позначень;

- побудова розшрено! реляц!8но1 алгебри, мови опису даних т<а нови зашт!в для часово! реляц!йно! модэл! даних (ЧВДЕ), як теоретичного фундаменту для побудови СКБД на II основ!;

- побудова досл1дшщького прототипу СКБД та анал!з мошивих практичних застосувань ВД на основ! ЧРМЯ.

Каткова новизна солягае в наступному:

- розроблена та представлена теор!я моделювання семантики !вформац!1 з часовими парше трамп в базах даних;

- введено поняття часових нормальннх форм, досл!давно сп!Ев!дношення м!к ними та побудовано алгоритки нормал!зац!г;

- сфэриульовано принцшш побудови часових реляц1йних алгебр, досл!двен! влаотивост! та умови коректност! роххреяь раляд!йних оператор!в;

- побудовая! Б0ь-под10в1 нова опису та «ан!пулпвання

дазтаа для ЧЩД. розроблоз! щзшщяшз небудоза досл1глп№г.ого прототипу СКБД на основ! ЧРМД.

Кэтоди дослиг-.ень базуяться на основяих полсгеннях Teopíl в1днсш8нь, формально! алгобрл, математзчго! лог!ки, часово! лог!ки, математичноК теорИ баз даних.

Достов!та!сть основних науковлх результат!в забезпечуеться строгим катематичшм доведениям сформульсваних твердкень ' та теорем, шляхом розв'язаняя практячних задач та 1х впровадженням- в конкрэтша !нформац!йних системах.

Практична Шнн1сть дисертацП. Результата дасертац!йшх досл!даень перев!рялись на практиц! в прочее! вкконання догов!рвих та держбюдеетних роб!т. Теоретичн! та методолоПчн! результата, розроблен! алгоритми í прогреми мокуть використовуватися:

- при гобудов! узагальнено! методики проектування БД;

- при розробц! промислових СКБД на основ! ЧРМД;

- в навчалыюму процес! при Шдготовц! спец!ал!ст!й' за

спец!альностями прикладно! математики, АСУ, систем штучного 1нтелекту;

- при розробц! прикладних '1нфоркац1йЕкх систем для промислово* експлуатац!I.

Реал!заи!я результат!в доел t гота нь. В процэс! впровадаення основних результат!в дисертац!2них досл1деэнь з i конкретних 1нформац!йних системах розроблена узагальнена методика проектування ЧБД, елементи прототипу СКБД па основ! ЧРМД з автономию модулями розиирвння б!бл!отеки базевлз процедур для ман!пулпвання часовиш, параметрами та вздоппл арх1в1в. Ц! результата Еякоркстовуввлпся щи ESOEanai дерЕбвдаетних та госцдогов!рних роб!т для Брркславсъхо!

б

фабрики нетканих матвр!ал1в, 1вано-Фраак1вського заводу КСМ, заводу зб1рних конструкдШ W769 (м. Льв1в), Бориславоького експеримеьтального ливарно- механ!чного заводу, Льв1вського домобуд!вного - комбинату» автомоб1льно! бази JS2440 (м. Льв1в), сп1льногс укра!нсько-н1мецького п!дприемства "ICH" по виробництву бурового 1нструменту (м. Дрогобич) та .1н.

АпробаШя роботи. R 1ультати дисерташйно! робота допов!дались на всесоюзных школах-сем1парах з баз даних та знань (м. Льв1в - Славсько), на щор!чних наукових копфвренц1ях професорсько- вихладацьхого, складу Льв1вського пол1техн!чного 1нституту (ф-т комгаотерно! техниси та 1нформац1йних технолог 1й, 1990-1993 роки), на м1жнародн!й конференцП з 1нформац1йних технологий та систем (Льв1в,4.10-9.10.Х993 р.). на сем1нар! "Новые информационные} технологии и инструментально- технологические средства поддержки принятия решений" (1н-т кибернетики 1м.В.М.Глушкова Ail Укра1ни)

Структура та' об'ем роботи. Дисертац1я - складаеться з вступу, чотирьох роздШв, висновку, списку cchobhol використано! л!тератури та додатку. Робота м1стить III CToplHOK основного тексту, - список л!тератури 1з 81 найменувань, б сторЦок додатку. Загальний об'ем дисертацП 124 стор1нки.

Z вступ! обгрунтована ваюшв!сть та актуальнхсть питань представления 1нфорыацП з часовим параметром в базах даних реляцГйного типу. Проведено короткий анал!з досл1джень в облает! часових реляШйних баз даних. Сформульована мета досл!дж8нь, наукова новизна, ' ochobhI 'положения, цо виносяться на загист.

ПервиЯ розд!л присвячэний питаниям моделювання зм!нно1

в час! 1вформацП в базах даних. Розглядаеться цояяття часового куба даних, досл!дхутъся його влзстивост!. Наведено формал!зкя структурування часовет домэн!в. Проведена тш!зац1я часових елемент!в. Досл1дкено р1зн1 ввди операц!й над ними.

В якост! фундаментального концепта моделхшання залегнях в!д часу даних використовуеться поняття под!!. Проведено дэтальниЯ анал1з цього яонлття, граблено визначення атомарно* поди, элементарно! поди та поди, показано !х зз а емовIдношення.

Означения. Еволюц1я вредоэтно! облгст! (об'сета) - це лосл)довн1сть стан!в предметно! облает! (об'екта). Предметна область (об'ект) переходить з попереднього стану в наступила в результат! зд!йснення под 11 (елвмшчарно* под11). АналоПчно виконання атомарних под 19 форму е еволвц1в атрибута об'екта. До моделювання еволици прэдметно! обхест! доставлено вимогн часово! повноти, часово! ц!льност1 та расового 1зоморф1зму.

Для представления атомарних под!й використано тр12кп 131тх (о.иД), де о - об'ект, - и - значения дэяко! сарактерястики цього об'екта, г - часовий момент, ио визначае час реал1зацП дано! под!!. СунупнЮть-трпшют1в з э!вними часовимя елементами представляв деяку под!ю. 5аф1ксувавши об'ект та атрибут, отримаемо сукупн!сть ,ркплет1в, впорядкованих зПдяо з значеншая часовнх !Лемент1в. Назвемо таку госл!довн1сть простое часовой |осл!дсвн1стю (ПЧП). Проста часова посл!довн!сть об'екта служить для представления еволвд!! атрибута об'екта. 1укупн1сть ПЧП вс!х атрибут1в об'екта називэеться часовое :осл1дошйстю (ЧП) цього об'екта. ЧП об'екта слуеггь дая

представления еволюцП об'екта. Часов! посл!довност! вс!к об'ектЧв предметно! облает! формувть сукупн1сть часоЕах посл1до!шостей (СЧП). СЧП представляткш еволюц!ю предметно! облает!_____

Для моделювання часових даних, враховуючи !х трьохм!рн1сть, на концептуальному р1вн! зручно використовувати просторову побудову - часовий куб даних. Одну розм!рн!сть куба даних становлять об'екти предметно! облает! О, другу розм!рн1сть - атрибута об'ект!в 0, третя розм!рн!сть куба - часова в!сь, на яку в!дображаються часов! елементи. Часовий куб даних адекватно вгдоОражае сукуот!сть часових посл!довностей.

Показано взаемозвязок р!зних компонент та зр!з!в куба з часовими посл!довностями, досл!даено 1х семантику. Описано властивост! синхронност! атрибут!в об'ект!в, в!дм!нн!сть атрибут!в по способу виведення пром!жних значекь. Вид!лено три евмантичн! р!зновиди часово! паранетризацП даних: час д1йсност! под!!, час транзакцИ та час, визначений корастувачем. Розглянуто вида п!дтримки актуальност! часового куба та способи задания його часового 1нтервалу 1снування.

При розробд! метод!в представления часових элемент!в в 1нформац1йних системах базовим е поняття структуруваиня.

Розглянемо множину 3=С...,80,а1.....вп,...}, на як!й

задано в1днсшення порядку < , тобто Уб^ .е^Б або з^ <8;, або

а >а , або 8 =а .

» 1 ' ^ 1

Якщо множина Б е ск!нченною, то можна визначити наступи! оператори :

Иг8г(5)=з;еЗ. Ув^З: 3)<31 1ави8)=в еБ, Ув^еБ: в^в^

Скппеинкм закритим ютервалом етошши Б е етохана Б*, яка задов!льняг наступим умоввм:

1)5'- ск!нченна;

2) Б' С Б; .

3) УзеЭ : 11гзг(3')<8^1азг(5') 4 зеБ'

Означения ■ Кехай Б0={з00,801.....эог1} мнояша з

в1дноиенням порядку <. Тод! структуруваннш множили Б0 називаеться пара <31,Г*>, дэ

1. 31={з>0,з11.....з1к), каг

2. Ух хе30=>2г31

3. Г'^зг50 е в1дображенням, яке волод!е властивостями:

а) ;* в1добранае кожей елэмент в ск!нчениий закритий

!нтервал множил Б0

б) иг^^о

Зг!дко з структурувавнян, мноташа Б0 розбиваеться на сум!жн! Ютервали, кокному з яких в1дпов!дае единкй элемент з 31, 1 навпаки, кожному элементу множини ставиться у в!дпов1дн1сть единий 1нтервал мнокини 30. Мнокина' Б0 повн1стп покриваеться даним в!добраЕенням. На мноаин! ка могемо ввести в!дношення порядку <• наступяим чином: О ^(^(В,. ))' < Пгзгс!^.))

На баз! структурування розроблено опособи представления часовях момент1в та доел!давно питания часових домен!в.

Часовий момент слухить для представления наймвклоГ часово! одиниц!, цо використовуеться в баз! даяих.

Кр!м часового моменту базовнми констругаЦями для представления часових влемент!в в !нформац!йнкх системах в наступи! типи даних: часовий !нтервал, тэрмШ часу та часовий ланцвг. Часовий 1нтервал задаеться за допомогов двох момент!в часу - початкового та к!нцевого, 1 складаеться з ■

множили Bctx момент 1 в часу, як! лазать м!ж початковим та к1нцевим. ПочаткоЕий момент вклвчаеться в 1нтервал, а к1нцевий не вклвчаеться. Терм1н часу використовуеться для задания тривалост! часовогоДнтервалу, або в!ддал! м!к двома моментами часу;—Часовий—ланцюг—-—це—мнохина —часових— 1нтервал1в, як! не мають сп!льних точок.

ОперацИ над часовими елементами можна под!лити на наступи! груш: операцП в!днолення, часов! операцП, арифметичн! операцП, функцП перетворення. Наведено опис огорац1й, доел!давно 1х повноту.

В другому розд!л! даеться визначення часового !нформац!йного в!дношення, реляц!йно! схема, кортежа, часового значения атрибута, розглядаоться onepauti на часових значениях. Введено часов! нормальн! форми в!дношення, розроблено алгоритми нормшпзацП. Досл!даено поняття ключа, залежностей даних в часов!й реляц1йн1й модел!.- Значна увага прид!лена властивост! 1нформац!йно1 piBHocil в!дношень.

Озаачення . Реляц!йною схемою часового в!диошення г називаеться тр!йка R={R,¥,2}, де RCU, U - це множила атрибут!в вс!х об'ект!в предметно! облает!, it - система тв!рних залежностей, 2 - мнокина залехностей даних.

В часовому в!дношенн! значениям атрибута е не окремий элемент облает! допустимих значень атрибута, як в традиц1йн!й реляц!йн!й модел!, а множина елемент!в, кожен з ЯКИ1 в1дпов!дае стану атрибута протягом деякого пром!жку часу.

Озаачення. Часовим значениям (надал1 просто значениям) атрибута А е ф/нкц1я Г=т(А), визначена на часовому елемент! , тека, до для кожыого tev, f(t) е елементом облает!

визначення атрибута А. ЧасЪвиЗ елемент V нпзивавться .часоЕдз доменом значения Г 1 позначаеться через Мсп(Г).

■ 3 мноиши залеЕНостеЗ, як! п!дтримуються на часовогзу в1дноп!енн1, автором вперше вид1ляеться система тв!ршх залежностей тт. На в1дм!ну в!д залежностей' з мзоотни .3, тв!рн!'залеяност! ви?начаються сп1вв1дношенням атрибут!в, а не 1х значень. Система тв!рних залеаностей задаеться розбиттям схеми И на класи атрибут!в та заданиям вид!леного ключа К в1дношення г. Тв1рн1 залекност! можуть прямо не залежати в!д семантики предметно! облает!, а впзначатись проектувальником в заленност! в!д потреб представления - та обробки даних. Тобто система тв!риих залегнсктеЯ в загальному випадау е привнесено» отстемою залежностей.

Означения. Кортежем т часового в1даошення-з1 схемою И називезться функц!я над ,й така, що для кожного атрибута АеИ т(А) е часовим значениям к. .

Означения. 1нфэрмац1йннд часоЕзм в!дношенням (дал! в!дношенням) з! схемой ®={н,тг,2У називаеться скЮТенна Шохина кортеа!в з! схемой И, до задов1льняв залешостям 3 та тт. •

Часове в1дношання можна трактувати, як посл!довн1сть ск1нченного числа статичних вгдношень. Тому доц!льно ввести Функц1в стану часового в1днозензя Тегар(гД): гхТ ■* Не1(Н), яка для кожного моменту "часу г е Иот(г) визначае статична в!днотення г(г) з1 схемою И.

На часовому в'1даовенн1 г тдтримуеться функц1ональна залежн1сть Х->У, якцо \Негаоа(г), У^ег, Ут2ег :

Конструктивна визначення залекност! випливае з паступного твердження.

Твердгепш;. Нехай г - часовв в!дношення з схемою R, X.YcH. X-»Y тод! I т!льки тод!, коли V^er, Vt2er : (%í (Х)/т2(X))v(t± (X)=t2 (Xbt, (У)=тг (Y)) Означения. На часовому в1дношенш r шдтримуеться

_______' а

глобальна функциональна залвШГсть X 5—Y",—якео—Vtr-rtjt— tdom(r), V^.^er :

(tt (X. tt (X. t2))v (t, (X, tt )=г2 (X, t2 )at (Y. tt )=т2 (Y, t2))

a

Очевидною e властив!сть X Y 4 X -> Y.

Традац!йне визначення ключа через функц1ональн1 залежност! мае ряд небажаних для часовoí модел1 властивостей, зокрема значения ключових атрибутхв може м!нятись з часом. Тому такий ключ називаеться слабим кличем, а для ключа наводиться !нше визначення.

Означения. Ключей в!дноиення г зг схемою R називаеться п!дмножина KCR, якщо виконуютъся 'наступи! умовя:

1) VAeK, 1т(А)| Mtстать единий элемент;

2) Нехай Т£ та тг е кортеж! в!дношення г, тод! VAeK lt1(A)l=ITi(A)l »'V=V

3) SXcK такоГ, що X е ключем.

Серед- специф!чних гип!в залежностей часово! модел! автором вперше вид!ляються так!:

- функц1ональн! залежност! з - затратою. Нехай т.т'ег, H,vetdom(T), ц',v'etdom(T'), begln(v)= end(n), begirHV )= end(¿t'), тод! (Х.Ю =».t(Y,v)=f (Y,V )

- ■функц!ональн! залежност! тривалост!. При зберехешп попередн!х припудень виконуеться:

KX.ní^'ÍX.n'jAdurationfuJ^duratiorKti') T(Y,V)=T'(Y.v') Значну роль ,в часових базах даних В1д1грають залежност!, пов'язан! з поняттям синхронност! , атрибут1в. Автором ДОСЛ1ДЖ9НО власгивост!, • дано конструктивна

визнг мння цього поняття та и8 яого основ! розроблено ' , алгоритма, якI використовуються в процесах нормал!38Ц1 1 часових в!дношень.

Означевня. Нехай К ключ в!дношення г з! схемою И, А4 та

I

А2 атрибути схемк И: А1 та А2 е асинхронними А1»А2, якщо I ■ильки якшо Юнують два сум!кн! часов! момента ц та та кортеж т, так!, що

1) т(А1 )|ц1=т(А1 )1 л т(А1)1ц,^':(А2)|ц2 , або

2) •с(А2)|ц2=а(А1)|^1 л КА.Нц^-иА^ц,

В робот! розвйнено теор!ю нормал1зац!1 часових з!дношень, яка «находиться в зародков!й стад!!.

Означезяя. Часове вгдношення г переОувае в еволщ!йн!й формг, якщо 1 т!льки якщо вс1 атрибути схеми Н налегать до одного класу розбиття.

Корте* часового вЮТошекня в1 еволюшйн1й форм! представляв елемеятарну поди) предметно! - облает!, а схема мгетить единий часовий атрибут.

Означевня. Часове в!дношення г перебував в еволгц!йн!й нормальн!й форм1, якщо . 1 т!лъки якщо воно перебував в еволюц!йн!й форм! та в схем! в!дношення не !снуе асинхронних атрибут!в.

Вводяться-такок !сторична та !сторична нормальна форта часового в!дношення.

Розглянуто поняття !нформац!йно! р!вност!, яке дозволяв в гнучзой манер! оперувата 1н$ормац1йним наповненням в!дношень.

Означевня. Нехай г I з - часов! вгднопення. Будемо говорите, що г 1 з !нформац!йно р!вн1 пз, ятсво вкхонувться умови: 1) 1йоа1(г)=1(1от(з)

2) ¥геШот(г) Тесг.р(г,г)=Тетр(з,г) Хоча 1нформац1йно р!ш1 в!дношення не е'екв!вален-гними, вони несуть однакове !нформащйне навантакення. В1дношоння Иф>рмац1йно1 р!вност! е в!дношенням екв!валентност!, тому для конюго в!диошения г 1снуе клас (г) в!дношень, !нформац!йно р!вних до г.

Нехай г^г2 та а^ зг. Б!нарний оператор. » називаеться !нформац!йно !нвар!аитним, якщо г^ з^ г2о а2. Аналог 1чно можна визначити 1нформац!йно 1нвар1антний унарний оператор.

Досл1джено оПерацП на .часових значениях атрибут1в, уточнено поняття предиката на часових значениях та оператор!в в!дношення м!ж часовими значения. Наприклад, вгдаошення р!вност! -часових -значень мае ряд семантичних трактувань: .

- р!вн! часов! значения гс1от(11=Г2)= {ге(г(1от(Г1)п МопКГ,)):'

- повнЮтю р1вн! г4 = 1г\ гйот(Г1=1г)=г(1от(Г1)=г(1от(Г2)

- р1вя! на сШльиому часовому домен! 11 Г2: К1оп1(Г =Г )= (гаопцг^гпаопк^)

.- часов! значения, р!вн! по датах ^ Г2; | Г^- = | Гг|

- р!вн1 по даних та 1х порядку =оГ2: Нехай к' - к!льк!сть елемент!в I . тод! повинн! виконуватися наступи! умови: (11,1 = |Г21 )' л(¥п, 0<п*к : ОгйегОз,^)^ 0г<1ег(п,Г2)

- часов! значения, р!вн! з точн!стю д<э зсуву часового домена г. =.ь V Зп ^МПСп.Г;) = г2 \

Тверда ння. М!н р!зними 'трактуваннями в!дношення р!вност! викс&уються наступи] сптввхдношешя.

1) (Г, " Тг) (Г, - Г2). (Г, ==.?ж) 4 (Г, = , 1г),

' <Г. = V =» <Г. % <Г, == У =» =.Ь V

2) (г ... г,) ч <г. т.)

3> ^ =„ V => (К =а V- (Г, ^ 1г) =» (Г, =о Г,)

В трэтьому роздШ розроблэно принципя та побудовано розширення оператор!п часово* реляц!Сно! алгеСрк. Досл1дазЕО взаемов1даоиення пржясс та часових розшрень алгебра1чвих операторгв 1 1х зв'язок з операторами традиц!йао! релкц!йно! алгебри. Сформульовано властивост! введених опоратор!в, зокрема властив!сть !нформац!йно1 1нвар!антност!.

Часова реляц1йна модель дае валику р!зноман!тн!сть в побудов! операторних розширень. Розглянемо деякий 01нарнзЯ оператор 7 традиц!йно£ реляц!йно! модел! даних.

Означения. Нехай г та э - часов! в!дяозення. Прямим розширенням оператора 7 називаеться оператор 7' часовоТ реляц!йно! алгебри такий, що 71;е1;с1ога(г)игс1огп;з) виконуеться

Тетр(гт'з,1)= Теир(г,{)7Тетр(е,1) Аналог1чно, прямим розширенням унарного оператора 7 назвемо оператор 7', такий то виконуеться

Тетр(7,(г),г)=7(Тепр(г,г))

Прям! розширення реляцгйних оператор!в володЮТь рядом бажаних властивостей, зокрема, !хня сукуш!сть склада е реляц!йно повну систему, але вони не дають моягавост! адекватно ман!пулввати з еволщ!еп значень атрибут!в 1 нэ враховують всП' особливостеЯ реляЩйно! схеми часового В1даошення. Тому для "часово!" повноти сл!д розглянути так! розширення оператор!в реляц!йнох алгебри, для ягса не виконуються вимоги означення. Назвемо так г розсирекня часовими. Часов1 розширення реляшйних огтератсргз в загальному виладку не моета виразити через приви рзсгкроння. Такий п!дх1д до пооудови часово! реляцШго! алгебри, а такая введения часових розширень реляц!йшп оператср!в вгэдяться

ГБ

авторш впараэ.

Нормально шзяачэш прям! та часов! розиирення оператор1в проехц! 1, селекШ, поеднання, р!зн! вида оператор1в об'еднання та доповнення. KptM прямого розшкрення

.введено—слабку_.та __сильну оформи_onepaiopis_pJэта 1_та.

перетяну. Зокрема, результат виконання прямого розширення оператора пврвтину првдставляеться формулою: rns^CtiH^er Зч^ез, ^(Ю^СЮат^! tdon(^) ntdom(тг)| tdotMi^ntdonUtJ} "Строгий" перетин включав в результат кортеж! т!лыш при повн!й И р!вност1: гпА8={т:теглтез}

"Ы'який" перетин вклвчае в результат розширення р!вних по ключу сумЮних кортеж!в до сп!льного часового домену: msB=li:3\er 3ifea, т1(К)=тг(К)лг=т1и'сг>

Викоауеться властив!сть rnAacrnacrnss, причому р!вн!сть досятаеться при R=K.

Наводяться алгоритма обчислення результат!в виконання введених оторатор!в. Доведена наступна теорема.

ТВОИМ». Для в1дношенъ в еволюц!йн!й форм! р!зновиди кожного оператора часово! релящйно! алгеСри сп!впадають.

Вводиться принципово новий оператор форма Perform, який оперуе в!двошеннями пишем зм!ни тв!рно! система.

Нехай задано часове в!дношення г з схемою Н={А1,Аж,А>,...,Ап}. В результат! виконання оператора Рег1огш(г;К;(Х1)...(Хт)) отримаемо в!дношення г', яке в !вфорнац1йно- р!вним в!дношенню г. ВадЦленим ключам в!днооення г' е К, атрибута форнують m клас!в синхронност! (Х,)...(Хт).

Вихонання оператора Perforn(r;Ki(X1)...(Xm)) проводаггьоя яаотупввм чином:

1) Для Bcix кортеж!в т, для яких i т| м!стить б!льаэ

одного элемента, проводиться розбиття tdom(T)=ni+ni+.. таке цо VI 0<1$п виконуеться - 1Шц.)| мютить ееткй елемент. Розбиваемо кортеж t на п кортеж!в: т^-и \it,

Vх1 ^.....

2) Впорядкуемо кортек! утвореного в1дношевня г за значениями атрибута К. Якщо !снують кортеж! т та г з ршмми К-значеннями, виконуемо операцгв t=xfUTi. Кортеж г додаемо до в1дновення г, а кортеж! та т вшишчаемо.

3) На кожному кортея! в1дноаеяня для кояного класу Х =

{А^.А^Л^.....AxJ знаходимо Z(.\)=TH\t)* E(A.lt)+

Е(А1Я)+ ... +Е(АП). Кехай £(Х)= U. t2, ts.....tb).

Часове значения кокного атрибута А^ , Kj\n Бизначаеться на штервалах [tlftUi), Kl'k. Для кохксго ¡нтервала зашсуемо конф!гурац!ю значень атрибут!в класу X .

Принципову роль в1д1грэе наступна теорема: ТЕОРЕМА. Надо оператор часово! реляц!йно! алгесря е прямим розиирэнням в!дпов!дного традпц!2ного оператора, то -" в!н е 1нформац!йно 1нвар!антнкм.

g чэтвертому розд!л! розрсблвно мову оггасу тз ман!пулювання даними TSQL, кка е розпшренням SQL на вгпадак в!дношень з часоВими параметрами. Оормально описано основа! синтаксичн! конструкц!! мовя, введено нов! семантичн! тала атрибут!в. Серед нововведень такси е ряд чаеових tehib даних, ключових сл!в мови, агрегусчих функшй. Показано звязок запропоновано! мови з реляц1йнов алгеброю.

Серед основних принцип!в побудови TSGL чюжня вад:лити

такк

- T£QI. повтен бути пркрояним розгогренняи SQL, то-'т"

дов!льии2 запит, оформульований на SQL, ' поешон в1рно 1нтэрпратуватиоь засобами TSQL, а обробка запи?!в до традшцвних баз даних обоиз ковами позянна даЕати однзковлй

.результат;_

додагков! конструкц!К TSQL, розроблен! для ман!пулювашя часовнми параметрам, повили! по замовчуваннзо встановлюватася в значения, що в!дпов!дають традиц!йша1 статичнкм дани,!, а тагсож поеиши бути синтаксично близькими до в1дпов!дних зворот1в звичайно? нош;

- часове в!дяо!зення - результат запиту "живе" в баз! даних, тобто п1дтркыуеться його актуальн!сть в колен момент часу.

Иова опису даних доповнена специф!чнкми можливостями опису в!даошень, зокрома введено так! ключов! слова:

ГШТШг - для задания семантичних тип!в часових атрибут!в, як! вклвдавться в часове в!дноавння та мають вбудований мвхан1гм п!дтрикки;

REFRESH - задав порядок ахтуал1зацП в!дноиення;

LIFESPAN, PERSISTENCY - ошсують пром!жок часу, який охошгоеться.

Для представления часових параметра введено нов! тали даних: TItffiCLOCK (часовий момент), INTERVAL (часовий 1нтврзал), SPAN (гтромИхж часу).

Зяачно зм!нэна семантика операц!й оловлення в!дношень, оск!лыси в часових базах даних виконуеться иимога збереження значень атрабуив, як! втратили свою достов!рн!сть. Виходячи з цього, в TSQL в!дсутня операц!я знищення кортежа в традэд!йному розум!нн!.

Блок SELECT Ml стать нов! конструкт К WHEN для виконання часово! .селекцМ в!дноиення та AS-OF.. .ALONG, яка служить

для часового обмеження ; в!дносно ' . виОрано! . часово1 роз"м!рност!. Потужн!сть отриманих задит!в не нияча за потужн!сть реляц!йно1 алгебри, що показано шляхом вираження алгебраÏ4HKX оператор!в через запита розроблено! мови.

Фраза GROUP BY доповнена ключовим словом ТШЕ, що, дозволяв формулювати склада! запита з скануванням расового !ятервалу задано!,тривалост! вздовж часово! ос!. Наведено алгоритм виконання запит!в такого типу.''

Наб!р агрегуючих функц!й розпирекий агрегатами, як! не

масть семантичних аналог!в в традац!йних мовах запит!в,

t > \

наприклад:

АСС - функц!я "акумулювання" для отримання наростасчих значень числових атрибут!в за певн! пром!жки часу;

Р_АУС - обчислеяня середаього те рыгну сталост! значень;

, 1_КАХ - повертае найб!льший часокий !нтервал дШсност! значень атрибут!в; . '

T_C0UNT - для обчислення розтод!лу значень, отраманшс функц!ев COUNT, вздовя часово! ос!.

ФункцП ÏIRST, LAST, OHDÈR служать для ©1ксування потр!бних !нтервал!в д!йсност! значень в оволецИ об'ект!в.

П'ятий poastJi прхсвяченвЗ побудов! досл!дащьхого прототипу СКЦД для М8Я1пулЕвання !вформац!ев э часовЕй параметров на баз! промислово! СКБД (1Ьаде-с!мейства. Наведено опис мови представления даних прототапу, яка включав механ!зм семантачного контролю - даних. Роэглянуто питания представлення та п!дтримки часового в!днс®епнл через систему в!дношень базово! СКБД.

При розробщ досл!дняцьКого прототапу створено автономну б!бл!отеку функц!8 обробки часових тяп!в данах, в

р;&£1зок&о СазоаиЗ наб1р часовзх продагсат1в, опэратор1в, ариЗмотичних фунюдй та функЩй перетворения. Значну увагу присвячено розвитку ыэтодаага створання Лнфэргац! Шды_^стем_для динам1чних та ютордчшя областей застосувашя на баз! традиЩйпих СКБД. Прототш СКБД вклвчае програший модуль забезпечення зручного корастувацького 1нтерфейсу для робота з 1нформац1ею, зм!нною в час1. Виклад розд!лу про!люстровано прикладами з прикладних розробок автора.

мал. I. .

ОункЩональна схема досл1дницького прототипу СКЦД зображона на «алЛ.

е еисяовкэх сфорыульован! основа! результата, отраман! в пэр 1 од виконаннл дасертаЩйшп досл!дань. Запропонован! та проанал!зазан1 можлив! напрямки подалыпих досл1даэнь.

Б долетку наведен! документа, як! шдтвердаують впровадкэння результат1в дасэртацИ.

OOHOBHi РЕЗУЛЬТАТУ! ДИСЕРТАЦП

1. Запропонована та обгрунтовana узагальнена кэтодяха модежвакня зм!нних в час! предмэтних областей. Проанал1зовано способа представления та тимзацП часових елемент1в.

2. Розроблено ун!ф1кований п!дх{д до фор<ал!зац1Г часового 1Ефэрмац1йного в!дношення. Введено поняття часових чормзльнах форм, проавал1зован1 питания залегяостей данях в часов1й реляц1йн1й модель

3. Зопропоновано принцип побудовя та розроблено чвсову реляц{йну алгебру. Досл1даено властивост! часових реляц!£них оператopie.

4. Побудовано моей опксу та ман{пуяюання двнгаш д-".я часово! релящйно! модел! даних, як! е роззиреннями SQL, представлено зв'язок основних конструкЩй дави М8н1пуясзаяня данимл з операторами часово1' реляц!йно! алгебри.

5. Розроблен! принципа, метода, алгорятми побудовя програшого комплексу досл!дницького прототипу СКБД на баз! часово! pejimtSaol моделг дата.

Основн! результата дясертад!! викладен! в роботах:

1. Люб1нець Я.В.' Моделввання часочо! 1нформацП в Сазах даних.- В1сник Львгвського пол!техн1чного 1нстптуту. зб1ряззс "Комп'ютерна тохн!ка".

2. Любинвц Я.В. Временная реляционная ноделъ zsiomx.-Твз.дск. на семинаре "Новые информационные твхз'ожгса я инструментально- технологические средстве подг»>рх«1 .трияятяя решений" пос. Кецквэ.чи. 21- 26 дек..- Киев, ин-т п^гя-ткк» им.В.И.ГлуетоЕа m Украины. 1992.

3. Розробка та анал!з метод1в t заооб!в 'обробки ненормал1зованих реляЩйних баз даних I _знань (розробка досуЦдаицького прототипу СКБД на основ! розширено! ненормал1зовано! реляц1йно! модел! даних): Зв1т про .ВДР Тзаварш.) Mil] Кер 1 вник ПасТчник ВТВ^ - ~OI9U006I893.—-Льв1в, 1994. - В!дп. викон.: Грабовецький D.B., ЛюбШець Я.В., Тавпаш С.А.

4. Любинец Я.В. Временная реляционная модель данных.-Тез.док. на II международном семинаре "Теоретические и прикладные проблемы моделирования предметных областей в системах баз данных и знаний" /Под. ред. Игнатенко Б.К. -Киев: Concept Ltd.

5. Лвб1нець Я.В. Представления часових параметр!в в реляц!йних базах даних. Тези доповШ на 1-й м1*тародн!й конференц!! з 1нформац1йних технологifl t систем, 4- 9 ков. 1993 р., - м. Льв1в.

6. Створення програмно- математичного комплексу розширення функШональних можливостей систем баз даних I знань реляц1йного типу на основ! апарату нетрадиц!йних лог!к: Зв!т про ВДР (заверш.) ЛШ; Кер1вник Пас!чник B.B. - 0I9I0Q4I765. - Льв1в, 1991. - 267 с, - БШ. викон.: Грабовецький Ю.В., Люб1нець Я.В., Тавпаш D.A.

7. Люб1нець Я.В... Пас1чник. В.В. УкраКномовн! бази даних. Тези допов!д1 на I м!жнародн1й ковференцП з проблем украКномовних компютерних систем. 28.09-2.10.1992 р..

АН0ТАЦ1Я.

Ляоинец Я.В. Метода и средства представления и обработки информации с временным параметром в реляционных базах дааныаЕ.

Диссертация на соискание ученой степени кандидата {иззпсо-математических наук го специальности 05.13.17 -теоретические основы информатики. Институт прикладной информатика, Киев, 1994.

Диссертационная работа содержат теоретические исследования расширения возможностей реляционных без данных для адекватного манипулирования информацией с временным параметром, а также результаты их практического применения. Разработатна обобщенная временная реляционная модель данных, которая учитывает зависимости синхронности атрибутов, и SQIi-подобный язык описания и манипулирования данными на ее основе. Предложены принципа расширения и построено соответствупцее расширение реляционной алгебры. Осуществлен ряд промышленных внедрений информационных систем с использованием технологии временных баз данных.

Lublnetc Ya.V. Methods and toola for representation and processing or Information with temporal parameters in relational databases.

The candldat's thesis on physics and mathematics in 05.13.17 - Theoretical foundations of informatics. Institute of applied Informatics, Kiev.

The thesis contains theoretic research, which expanding the capability of relational databases for adequate information processing with temporal paraoeters, as well as the practical application of that theory. Developed the generalized temporal relational data model, which takes into account the dependencies on synchronized attributes, SQL-like language of data describing and manipulation based on this theory. Principles of relational algebia extending are proposed and respective relational algebra is designed . Implemented several Instances of applied information system using tenporal database technology.

Ключов! слова: реляшйл бази даних, часов! модел! данях, мови запит!в.