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

U К'ЛЕСЬКА MICbKA ДЕРЖАВНА АЛМШСТРАШЯ .

1НСТИТУТ ПРИКЛАДН01 1НФ0РМАТИКИ

На правах рукопису УДС 681.3

ТАВПАШ ЮРШ АНДР1И0ВИЧ

МЕТОДИ ТА ЗАСОБИ БУЛЕВ01 I K-SHA4HOI ЛОГ1КИ " В СИСТЕМАХ РЕЛЯШИНИХ БАЗ ДАНИХ

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

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

Khïb - 1994

Робота виконана в 1нститут1 пркклагно! 1нфсрматкм!

Науковий кер1вник:

член-коресдандвнт АкадвиИ наук Украпш, д.ф.-и.н., професор А.О. Стогн!А

0фЩ1йй1 опонвнти: • .

д.ф.-м.н., проф. Г.П. Ко*8ВД1кова <м.Льв!в) к.ф.-м.н., М.В. Олен:н (м.КиКв)

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

(ч.ЮНв)

Захист В1дбудеться "¿р ^О_1994 р. 0 год.

на зас1данн! Спец1ал1зовано1 Ради Д 166.01.01 в- 1нстцтут!.

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

3 ди'сертатею можна о'знайомнтись в бтблготет 1нституту прикладно! гнформаткки.

. Автореферат роз!слан 1й "2В"

09

1994 р.

ВчениЯ секретар Спвщвл:зовано1 Ради Д 166.01.01

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

Актуальн1сть проблеки. Розвиток обчислювально! техн!ки I розшярення областей II викориотання прийели до квобх!дност! орган1зац!1 та п!дтримки велико! к!лькост! баз даних для вир!шення р!зноман!тних прикладних задач. Переважна б!льш!сть з них грунтуеться на реляц!йн!й Модел! даних, яка впврше була запропонована Е. Коддом в 1971 роц1. В практичному I теоретичному план! продовхуються . 1нтенсквн! досл!дкення з багатьох питань баз даних. Стандарта! дан!, основан! на в!домих знаниях, стали загальними, 1, по м!р! розвитку метод!в обробки даних, на перший план висуваеться питания обробки невизначених значень. Ця проблема в традиц!йи!й-реляц1йн1й модел! не мае однозначного вяр!сэння.

Створення бази даних, а також будь-як! зм!ни II зм!сту в процес! експлуатацп вимагають обов'язково! ггерев!рки виконання обмегень цШсност!. В зв'язку з цим впр!шення ряду питань ман!пулювання залежностями мае особливе значения в проектуванн! 1 перетворенн! схем. Ця проблема в досить актуальною з точки зору забезпвченвя адекватност! представления частини реального св!ту в базах даних. Одни;« з п!дход!в в цьому план! е використання " апарату булевих та К-значних лог!к.

Булев! екв!валенти залекностей даних вв!йшли в основу алгоритм!в, як! використовуються при проектуванн! та оновленн! баз даних, що грунтуються на клзсичн!й реляц!йн!й модель Тому велике значения мае виртсекня питания отримання лог!чного виразу, що описуе шдтримку задано! системи обмежень цШсност! з врахуванням фзктора невизначеност! у в!днотешп. Причому, для обробки даних 'з невизначеними значениями необх!дно забезпечиги эквгва^внтни?

перех!д в!д р!ввя вазначеност! до невизначеност! 1 навпахи. Цього мохна досягти за рахунок нароквння основа ломки, збер!гаючи íзoмopфlзм перетворень множили правил виводу для первинно! системи залекностей.

Основн! результата по даному напрямку були опуол1кован! в роботах Делобеля, Кейс1, Паркера, Саг;ва, Занюло, Б1р1, Фейда1на. Виходячи з анал!зу достуших публ!кац!й, можна вказати на ряд невир!шених проблем у ц!й-облает!:

- в!дсутн!сть единого п!дходу при отримашп лог1чних екв!валент!в залекностей, що використовуються при проектуванн! схем РБД;

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

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

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

Мета дасертацЮно! робота полягае в розробц! теоретичних 1 прикладных метод!в та засоб!в проектування, п!дтримки та оновлення реляц1йних баз даних з можливими невизначеними значениями, на основ! в!домостей про типи I структури системи обмекень ц1л!сност!, що накладаються на дан!, користуючись аларатом булево! та К-значно! лог!ки. Виходячи з цього, доелджання проводились в наступних напрямках:

- анал1тична ощнка 1снуючях в дан1й облает! роб!т та п!дход!в;

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

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

- розробка алгоритм:в ман!пулювання залезшостями. даних у в!дношенн1 з можливими невизначеними значения?®.

Наухова новазна дисертацИ полягэе в наступному:

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

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

- отриман! та обгрунтован! анал1тичн! сп1вв!днотення, як! дозволяють встановити факт п!дтримхи у в!днсе8ен1 Функц1овальноI та (або) багатозначно! залёкност!, забезпечувть немсжляв!сть присутност! кортеж1в дубл1кат!в, а також,дозволяють працювати в умовах невизначено! хнформацП;

- розроблен! алгоритми обробки даних, як! врвхсвувть обмеження ц!л!сност!, що накладаються на дан! у вЮТсзвшп з мозкливими невизначеними значениями.

Метода досл1дкень базуються на основнях пологеняях теорП' в1дношень, булево! та К-значно! лопки.

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

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

Цраетична ц!вн!стъ дасертацП, Результата дисертац!йних досл1дкень пврев1рял?сь на практиц! в процес! виконання ДСГСЗдрних . та держбвджетних .роб!т. Розроблен! метода, алгоритми I програми мохуть практично використовуватись :

I ■

- при розробц! промислово! СКБД, яка повинна давати мохлив!сть обробки невизначених значень;

- при розробц! .-прикладних !нформац!йних систем для цромисловоХ експлуатацН;

- в навчальному процес! при П1дготовц1 спец!ал1ст1в в облает! прикладной математики, АСУ, штучного !нтелекту.

Рвы1зад1я результат 1в досл!дкань. в план! реал!зац1Г основних результат!в дисертац!йнюс досл!дкень розроблен! метода та засоби проектування 1 оноглення реляЩйних баз даних з мохливими невизначеними значениями лри забезпеченв! п!дтримки задано! систеыи обмехень ц!л!сност!, на основ! апарату булевих та К-значних лог!к. Результата використовувались при виконанн! дерхбвдхетних роб 1т Державного ун!верситету "Льв!вська пол!техн1ка", -.а такок догов!рних роб!т для Льв!вського заводу зб!рних конструкта Я769, АТ "Гал!нстрах", Р!вненського обласного шпиталю ветеран!в в!йни. За результатами дисертац1йних досл!даень були п!дготован! та видан! у Льв!вському пол!гахн!чномг !нститут! методичн! вказ!вки "К-значн! лоПки в анал!з1 релящйних баз даних" до вивчення окремих роздШв курсу "База та банки даних".

Апробац1я - робота. Результата дисертац!йно1 робота дошв!дались на республ!канськ1й школ!-сем1нар; "Проблема !нтелектуад!зац!I !нформац!йних систем" (м.Ки1в, вересень

е

1988 р.), ВсесоазШй школ1-сем!нар1 "Бази даних та знань для ПЕОМ" (о. Славсько, Льв1всько1 облает!, березень 1989 р.), .Чикнародн!й науково-техн!чшй конференц! I студент!в, молодих • вчених ! спец!ал!ст!в "Молод! .вчен! у Вир!Ш8НН1 КПЕШ1 краш-член!в РЕЗ" (19-22 кв1тня 1989 р., м. Ки1в), Всесоюзна конференц!!' "Управл!ння великим м!стом"' ,(20-22 червня 1989 р., м. Москва), Мхжнародой конференц!! "1ятелектуальн! система управляли" (м. Варна, НРБ, 26.09-2.10.89 р.), Всесоюзн!й конференц!'! "Створення ! застосування г!бридних експертних систем" (10-15 листопада 1990 р., м. Рига), II Шжнародному науково-техн!чному сем!нар! "Теоретичн! ! приклада! проблеми моделювання предметно! облает! в системах баз даних та знань" (20-26 вересня 1993 р., м.Туапсе).

Публ1кац!1. По тем! дисертацМноЛ роботи опубл!ковано десять роб!т.

Структура та об'ем робота. Дисертац!я складаеться з! вступу, чотирьох розд!л!в, висновку, списку основно! використано! л!тератури 1 ' додатку. Робота м!стить 120 стор!нок основного тексту, список Л1тератури з 83 найменувань.

КОРОТКИ! ЗМ1СТ ДНСЕРТАЦН

У ветуп! о'Огрунтована важлив!сть та актуальн!сть питань ман1пулювання залекностями в базах даних реляЩйного типу. Сформульована мета досл1джень, наукова новизна, основн! положения, що виносяться на захист.

В перлону розд!л! наведен! основн1 поняття ' та визначення теорГ! реляЩйних моделей баз данпх.

Обгрунтовуеться застосування двозначних аналог; а за.-екноотей даних в реляц1йнШ твори. Розглядаеться узагальнене понят'тя булевого тарвтворення залежностей даних. Ана;пзуються дослЦдаення релящйних баз данйх з невизначеними .значения®: атрибут!в та'Хх оновлення -без порушення задано I систем: обмежень цШсност1.

При переход! бази даних з одного стану в шший виникае необх1дн1оть перевгрки, чи е новий стан допусткмим. При велик!й к1лькост1 складних яалежностей I част1й зм!Н1 стангв 1снуюч1 системи управлтня базами даних' не забезпечують перевгрку йс1х сп1вв1дношень; Тому одна з основних задач проектування схем релящйних баз даних може бути сформульована настунним чином : серед еквхвалентних схем вибрати такт, як1 забезпечують ефективну перев1рку вихонакня визначальних спхввиношень при змШ станхв бази даних. -Бона ошраеться на виршення ряду допомиших задач, якI .в той же час мають ц1лком самост1йний характер I пов'язанх з досл1дженням структур семантичних обмежень. Для б1Льшост1 з них 1снуе дек1лька алгоритма вир!шення. В дасертацН леревага надаеться там шдаодам, ЯК1 грунтуються на використанн! апарату булевих та К-значних лопк. Основна увага придШеться принципам побудови лопчних екв1валент1в залеиюстей даних.

Явите екв1вадентност1 мш певними типами залекностей .даних г п1дмнохиною алгебра лопни розширене за рахунок введения Сэпеом поняття булево1 залежност1.

Визначення. Булевою залежпстю називають дов:льну булеву фуккщю Г(х1,х1,...,хп>. да змиол х14хг,...,х„ спеш&льким чином поставлен! у • в1дпов1дшсть атрибутам

Х..Х,.....Х^ ыдносення Н.' Значения змлнних ••■

визначаьться настигав»', чином :

[" I, якдо значения атрибута сп1впадають : для деяко! пари кортеж!в в й

* = "I' .

! О, якщо для дано! пари кортеж!в в И [ атрибут Х^ приймае р!зН1 значения

Одним г основних недол!к1в використання поняття булево! залежносп рядом азтор!в е те, що вони не враховують при побудов! лог1чних екв!валент1в залежностей. !нших обмежень Ц1ЛЮНОСТ1, як1 накладаються на даик Такими е обмекення самого В1дношеняям як математичнох конструкцП. А саме, що у в1Дношенн! не можуть бути присутн! кортеж1-дубЛ1кати. Для функцюнально! залежност! - це ыпдування з не! Оагатозначно!, та 1нш1. В1дсутн1й також единий п!дх1д, який дозволяв би будувати лог!чн! екв!валенти залежностей даних, як1 базуються на р!вност! або нергвност! значень атрибута (чи мнбжини атрибут!в) для будь-яких пар кортеж!в заданого в!дношення. Використання булевих залежностей груятуеться т!льки на семантиц! т!е! чи ,!ншо! залежност! дашй, для яких вони виступають узагальненням, 1 не враховуеться повна множила атрибут!в, присута!х у в1дношвнеп , до обмежуе огляд схеми в!дношення 1 створюг - певн! незручност! для проектувалъника,

В)5ективн1сть системи управл1ння складнями об'ехтами суттевим чином заложить в!д вир!щення задач! Юдтрнмки 1 поповнення !нформац!Г. Ця задача усклэднюеться там, що ъ реальних задачах, як правило, доводиться • уати справу з невизначеними, недавними, а часто ! еуперечлиЕйга значениями. Поява под!ОноI !нформацп допустима, якщо передбачена можлизЮть п розп!знавання 1 разробден! спец!альн1 метода мая1пулювання.

В робот! на основ! анал!тичного огляду теоретоших 1

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

НвОбХ!ДН!СТЬ В ПОШУКУ ИОВИХ МОКЛИВИХ П1ДХОД1В до обробки

кевизначено! 1нформац11. В якост! апарату ман!пулювання I представления обмехень цШсност! вибрана К-значна лопка.

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

Розглядаемо в!дношвння, в якому. . п!дтримуеться функц!ональна залежн1сть. Для заданого в!дношення г, яке шдтримуеться на множин! атрибут!в и, для прикладу г ( Х,г. У, Ъ ), ( п=3 ) виберемо систему набор!в" 2П . <. 2 - основа ( в!доов!дно1 лог!ки ). Де вс! можлив1 набори, як! можуть бути отриман! в результат! , пор!вняння двох будь-яких кортек1в з!дноиэння. По визначенню функцхопальноI залежностг X -> У вщплимо групу наборгв, що приймають значения ютийа. Ка гх основ1 отримано лог!чний вираз, що описуе П1дтримку задано! функцюнально! залежност! у в!дношенн! :

х V у 2 ( 1 ) ,

Виз.чачення. Для шдтримки функц1онально! залежност! Х-> У в 1нформащ2ному В1дн0иенн! г ( X, У, 2 ) вимагаеться для будь-яких двох кортеж!В виконання умови -нер1Вност1 значень

корте»1в по множит атрибут!в X, або р!вн!сть значень корте»1в по атрибутам У х нер!вн1сть по атрибутам Ъ.

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

На практиц! часто виникають ситуацП, при яких не завясди вдаеться заповнити кортеж1 1нформац!йного вгдношення конкретними значениями. Таким чином, анал13 !нформащйних в!дношень з невизначеними даяими е важливим не т!лька в теоретичному, але 1 в чисто практичному план!. Наприклад, при ВВ9Д91Ш1 нового кортежа у вгдношення з МОЖЛИВИМИ невизначеними даними без порушення задано! систем, залежностей необх!дао мати результуючий лог!чний вкраз. вказаних залекностей, в якому б певним чином був закр!плений факт невизначеност! даних. Природньо задати питания : цо Суде являти собою функцхональна залезопсть I правила визоду для вказаного типу предикату в реляЩйн1й баз! даних з невизначеною !Еформац1ею ? Спробуемо в1ддов1сти на нього, використовуючи апарат К-значяо! логхки, да К > 2.

По заданому {нформац!йному в!дношенню г, що м!стить невизначен! значения, будуемо К-матрицю ( к = 3) або набори а^, що в!дображають результат пор1вняння значень епементарних атрибутхв для будь-яких двох кортеняв в!дношення у в!дпов!дност! з наступними правилами :

0, яшцо А ] + г [ А 3 ;

1, яшцо 1 [ А ] = ш ; а. = ■ 1 Ш = VI А 1;

4 п! = Ш , де п1 - значения

не визначене;

2, якщо 1С А ] = "г [ А ] .

Для визначеност! заф!ксуемо в!дношення на трьох атрибутах. К1льк1оть вслх можливих набор!в, як! м!стить

матрица, - к" ( в даному випадку к = 3, п = 3 ), отримуемо 27. 1х анал!з, з точки зору п1дтримки задано: функШональжн залежност!, наприклад Х-> Y, дозволяв вид!лити певн1 групм набор!в, в тому числ! запере.чувальн! для задано1 залехност!.

По K-матриц!, побудован!й за певними правилами для конкретного !нформац!йного вгдношення з можливими невизначеними значениями, можна зробитк висновок про наявн!сть функц!онально! залежност! м!ж р!зними атрибутами (множинами атрибут!в) в!дношення, про ti дП, як i необххдно виконати для забезпечення Шдтримки заданих залекностей. Можливе також розкриття невизначених значень атрибутib на основí отримуваних знань про обмеження, що накладаються на дан! в результат! пор!вняння кортеж!в, при умов! шдтримки т!е! чи 1ншо1 функШонально! залежност! даних, а сам®, забезпечуеться накопичення знань про, можлив! значения невизначеностей.

■Для отримання лопчного виразу, що одасуе обмеження, як! накладаються на дан1 црисутн1сио функционально! залежност! в умовах можливост! невизначених значень атрибут!в, використовуемо апарат К-значно! лог!ки ( к = 3 ) I вибираемо наступну систему елементарних функц1й : ■

1) кон'юнкц!я mln ( xlt х2 );

2) даз'шкЩя шах ( xif х2 ) ;

3) спаЩальна операЩя у = ха,ь. Означав таку операцЮ над х, яка значения х = а перетворюе в Ь, а вс1 !нш! значения в нуль. Система 1-3 функционально повна.

Побудуемо функШю ютинност! для задано! функц!онально1 залежностI, для прикладу X -> Y в гнформац!йному в!дношенн1 г ( X, Y, Z ). На заперечувальних : peían наборах вона прпЗмае значения в1жгов!дно < 0 > i < 2 >. Використовуючи

тэ

алгоритм I , але з врахуванням застосування апарату К-значно1 лопки I .вибражн система 1-3, отримуемо лоПчний вираз, со ошкуе шдтримку функщонально! залежност! X -> У в 1нфсрмац1йному вгднозюнш г ( X, У, 1 ) при можливост! невизначених значень, такого вигляду:

У2'2! г'-1) ( 2 )

Визначення. Для шдтримки фунхШонально! залежност! X -> У у вгдношенн! г ( X, У, I ), з врахуванням моюивост! невизначених значень атрибут!в, вимагаеться для будь-яких двох корте»!в виконання умови нергвност! значень по атрибутах X, або невизначэний результат шр!вняння по атрибутах X, або при однакових значениях по атрибутах У значения по атрибутах Ъ р1зн! або невдзначен!. Дане визначення попередне. Воно не враховуе обмежерь, як! нахладаються на дан1 «идуванням з функцЮнально! -багатозначно! залежност!, що буде показано ни*че.

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

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

Анал1тичн! сп1вв1дЕошення м!ж числом повторень значень множин атрибут!в, що визначають багатозначну залвжвхсть (г(Х.У,2). Х-~~У), 1 к! лькютю IX значень для кожного блоку | кортежш горизонтально! декомпозицП по множин: атрибут!в X, ; представимо наступним чином :

) = р< у1 ); . а(у^ ) = р( £ );

а(х1 ) = у' ) М г1); К=Еа (I,), 1 » Т^п. де

а ( г, ) - к!льк1сть повторень з-го значения кортежу по множив! атрибутов 1 для одного клаоу екв1валентност: по х, ;

р ( г1 ) - к!льк!сть значень кортеШв по множил! атрибут!в % для одного класу екв!валентност1 по х1 ;

а ( х1 ) - к!льк!сть повторень значения х, у в!дношенн! г або к!льк!сть кортея!в у клао! екв!валентност1 по х1 ;

М - к!льк!сть кортеж!в у в!дношенн! г, в якому •п!дтримуеться багатозначна залежн!сть X—»—»У, I - визначае ' клас екв!валентност! або мноаину блок!в кортех!в горизонтально! декомпозици Вхдношення г.

ЛоПчний вираз, що описуе шдтримку багатозначно'1 залегност! X—*—*У у в1дношенн! г(Х,У,г) приймае вигляд : з (у у г) ( 4 )

Визначення. Для Шдтримки багатозначно! залежнсл1! Х-»-» У в 1нформзц1Енсму в!дношенн! г ( X, У, г ) вимагаеться для Оудь-яких двох кортеж1в в!дношення при р!вност! значень кортеи!в по множин! атрибут!в X виконання умови нер!вност! значень по - У, при однакових значениях з облает! визначення кнозини атрибут!в г, вбо нер!врост! по - г, при однакових значениях з облает! визначення мнокини атрибут1в У. Область визначення значень кортек!в в даному випадку розглядаеться для одного класу екв!валентност! по шожин! багатозначно шзначаючих атрибут!в, або для блоку горизонтально! декошо.зиц!! однакових значень множили атрибут!в X. Дане визнЕЧекня т!сно пов'язане з визначеною нами семантикою багатог.^шо! залежност1. Для визначення багатозначно'1 залехност! необх1дний не лише лоПчний вираз, але !• додатков. у...овл на дан! в блоц! горизонтально! .декомпозици. Такими уыовьми можуть ваступати ! анал!тичн! сп!вв!дношення. Показано, що аксЮматика лоНчних в1фаз!в для

Сагатозначних залежностей cniвпадав з повною мноюшою правил виводу вказаних залежностей.

Лопчний вираз для багатозначно1 залежност! у в1дношенш з невизначеними значениями приймае екгляд : X2-2 ( у°-2 v z°'2 ) v X1-2 ( у°-2 v z°'3 ) ( 5 ) Визначення. Для тдтримки бзгатозначио1 залежност1 X —»—• У у в1даошенн1 г (X, Y, Z), з врахуванням мояливосп невизначених значень атрибуив, для будь-яких двох кортеж1в вимагаеться виконання умови : при ршносп або невизначеному результат! поршняння значень кортеж1в по атрибутах X -р1зний результат пор1вняння значень кортеж1в'по атрибутах Y або Z при однакових значениях, вхдповхдно, 2 або У з обласп визиачення для вказаних мнокин атрибупв. Область визначення значень кортешв в даному випадку розглядаеться для одного клэсу екв!Еалентност! по множил багатозначно визначаючих атрибут!в або для блоку горизонтально! декомпозици однакових значень множили атрибутib X.

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

При п!дтримц1 багатозначно! залежност1 X —•-» У у Е1дношенн1 г (X, Y, Z) в одному wiaci -экр.валентное?I по

MHOsami атрибутiв X можливг невизначен! значения по кнегсетах

>

атрибуитш Y або Z Т!льки в тому вкладку. ягсм по аказзиих множгнах атрибут'.в не з1доме жэднв знччення. --.шляеться окремий ' клзс екв1валентност! по множил атрибут:в У. -невизнзчений.

доведено 1?оморф:зм мхк отркманами ^.'.j-.

для функшенальних I багатозначних залежное-г** ? виводу системи вказаних ч^жно??-». '.:з"ч<»-н-.

шдтримуються у вцщошенн!.

Отримали дуже ц!кавий результат. В умовах невизначенос-т!, багатозначна залежнЮть як насл!док функцЮнально!, \ накладае додатковг обмекення на дан! в1дношення. Тому, лоПчний вираз, ш.о ошоуе факт Шдтримки залежност! X—»У .у в!дношенн! г(Х,У,г), з■врахуванням вказаних заперечувальних набор1в, може бути в!дкоректований до вигляду:

х0\, x,•I(y0•2v V "(6)

ТретЫ розд!л присвячений питанию побудови алгоритм!в ман!пулювання залежностями даних у в1дношенн! з мохливими невизначеними значениями. Введене • поняття К-значно!' залежност! даних I визначен! правила побудови лог!чшрс аналог!в залежностей.' Наведен! алгоритми оновлення стану !нформац!йного в!дношення на основ! лоПчних екв!валент!в обмежень цШсност! та анал!тичних сп!вв1даошень.

Як було показано вище, в якост! апарату манШулювання певного типу залежностей даних може виступати К-значна лоПка I в!дпов1дн! К-значн! екв!валенти. Доведений 1зоморф!зм множили правил виводу для вказаних залежностей 1 гобудованос за певними правилами К-значною функц!ею. Явще ехв!валенда>ст! м!ж залежностями даних 1 п!дмножиною алгебри К-значно! лопки може бути розширене за рахунок узагальнення понйття К-зна то перетворення залежностей даних. для цього автор робота вводить поняття К-значноI залежност!, яке в узагальнвнням I для булевих залежностей.

Визначення. К-значною залежн!стю будемо називати

дов!льну К-значну функщю 1{х1,г1.....хп), отриману за

певними правилами, де зм!нн! х,,!^,...,! спец!альним чином поставлен! у в!дпор!дн!сть атрибутам,Хп в!дношення И. Значения х1,хж,...,хп визначаються настушздм чином :

" К-1, якшо значения атрибута Х1 визначен! !

. егпвпадають для деяко1 .пари кортеж:в в Я;

(К-1')-1 в1дпов1дае певн!й 1нтерпретац!1 результату х> : пор!вняння дано! пари корте»1в, при

КЧК-П, невизначеному значенн! -атрибута Х^;

о; ' ямцо'значения атрибута визначен! I

не сшвпадаюь для дано! 'пари кортеж!в;

Наведен! правила -побудови К-значно! функцИ, що' е лопчним екв!валентом обмежвнь ц!л1сн0ст!, як! базуютьсн на р1вност! або нер!вноот! значекь атрибута для будь-яких. пар корте»;в задаяого в:дношення. '

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

Результуючий лог!чний вираз, який отримуеться внасл1док з'еднання через кон'юнкц!ю лопчних екв!валент!в обмежень д1л!сност1 заданих проектувальником, складаеться з деяко1 К!лькост: кон'юнкт зм!нних, що певним чином поставлен: у •в!дпов!дн1сть ,!менам атрибупв ,(множин атрибута) в!дношення. Таким чином, для того," щоб визначити чи ■порушуе новий корте» вказану систему залежностей. достатньо перев!рити виконання сп!вв1дношень, заданих в .кон'ккктах

ЛОГ1ЧИОГО вирчзу • при ПОр!ВИЯИН1 В1ДПОВ1ДНИХ ' ¿н^чень атрибут!в'вх1даого кортежа з кортежами вгдношения.

Наведен! алгоритми перев1рки забезпечения задано! ■системи'залежностей при встэвт нового кортежа у в.'дносення на основI лог!чного виразу та аиалгтичних сп:вз;днзс:вн1.

Лля машпулювання эалекностями застосовуетьсн алгоритм на'основ: методу семантичких тзблйць, якиЯ дсявс.-.я« ^риЯмагя рнаэкня : в умоввх невизнач^но! :нформаи11.

•В четвертому роздШ розглядаються вар1анти та можливост! практичного, застосування розроблених метод!в та засоб!в булево! та К-значно! лоПки в базах даних реляц!йного типу. 1х практична ц!нн!сть полягае в тому, то надаеться мокливЮть обробляти предотавлену певним чином невизначену !нформац!ю, грунтуючись на систем! обмекень ц!л!сност1, як! накладаються на дан!.-

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

Розглядаеться наступна проблема : заданий повний стан

бази даних на Й=(Н1.....10 1 новий кортеж X. Зможемо ми

визначити, чи буде И и (1) повним, а саме, чи не порушуе новий кортеж певну систему обмежень ц!л!сност1? Наведен! в розд!л! приклада показують, що це можливо.

Поняття К-значноI залежност! дозволяг перевизначити лог!чн! вирази обмежень ц!л1сност! на випадОк, коли необххдно вид1лити окрем1 класи невизначеност!. Для цього зб!льшуемо основу лоПки 1 наступним чиним !нтерпретуемо в!дпов1дн1 значения набор!в: 3 . - Ютина, при пор!внянн! визначених однакових значень; 2 - при пор!внянн1 окремого ■класу недовизначеност1; 1 - невизначен! значения; 0 -хибне, при пор!внянн! визначених неоднакових значень. Лог!чний вираз, що-описуе Шдтримку у вШошввв! г(Х,У,г) з мокливти недовизначеними 1 невизначеними значениями функцЮнально! залекност! X -» У буде мати вигляд:

х°'\,< Х*-\, X* ' * ) (у"' 2е'1) у л

/

Розглядаються приклада оновлення !нформащйного

\

й!дношення з окремими класами нввизначеност!.

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

у внсновку сформульован! основн! результата дисвртац!Йно! роботи.

В додатку наведен! документа, як! питверджують впровадження результат1в дисертац!йнях досл!джень.

0СН0ВШ РЕЗУЛЬТАТИ ДИСЕРТАЦП

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

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

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

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

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

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

4. Розроблен! алгоритми оновлення релящйно! бази даних з моаливими невизначеними значениями, як! з'абезпечують Шдтримку задано! системи обмежень цШсност!.

5. Розроблен! принципа тр алгоритми маншулювання системою залехностей у в!дношенн! з можливиыи невизначеними значениями.

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

1. Пасичник В.В., Тавпап D.A. "Компактное представление отношений в базах данных". Материалы Международной научно-технической конференции студентов, молодых ученых и специалистов "Молодые ученые в решении КПНГП стран-'членов СЭВ", 19-22 апреля 1989 г., г. Киев, с. 123.

2. Тавпаш С.А. "Проектирование компактных представлений •реляционных баз данных", Тематический вестник Львовского политехнического института "Технические средства автоматизации' измерений и управления научными исследованиями , Л 248, с. I3I-I35.

3. Пасичник В.Ь., Тавпаш D.A. "Программные средства поддержки целостности в РЕД", Материалы 4 Всесоюзной конференции "Управление большим городом", 20--22 июня 1989 г., г.Косква, с. I09-II0.

4. Тазшш U.A. "Распознавание типов зависимостей в РЦД",

Всесоюзной, конференции "Математические методы рагакзиаваа?п ооразов", 24-2Е 'октября I9S9'г.,- г. Рига,

С.114-117.

5. Тазпаа Ю.А. "Анал1з неЕизначеностей »нфоркащйгзх в1диошвнь баз данях з допомогою апарату К-значних лопк", ВJсник Льв'вського пол!техн1чного 1нсгитуту "Техн1чн1 засоба автоматизац!К вим!рювань t управл!ння науковззга досл!дженнями"-. 1990 р., с. 82-85.

6. Пас1чник В.В., Тавпаш Ю.А. Методичн! вказ!вки до вивчення окремих роздШв курсу "Бази i банки даних та знань" з теми "К-значн1 лог!ки в анал!з! релящйних баз даних" / ЛШ. - Льв1в, 1991. - 28 с.

7. Реляц1йн1 модвл! баз даних. : Зв!т про НД? (заверш.) / ЛП1; KepiBHEK Пас1чник В.В. - й 01880057829. - Льв1в, 1990. - 327 с. - В1дп. викон.: Берко A.B., Грабовецький Ю.В., Тавпаш Ю.А.

8 -Розробка елемент!в автоматазовано! системи обробки баз даних та знань реляцхйного типу на основ! ПЕОМ профес!йного. класу : Зв1т про НДР (заверш.) / ЛТП; Кер1вник Пас1чник В.В. - * 01890057488. - Льв!в, 1991. - 320 с. - В1дп. викон : Грабовецький Ю.В., Тавпаш В.А.,Берко A.D.

9 .Створення'програмно-математичного комплексу розширення функц!ональних можливостей систем баз даних 1 знань реляц!йного тицу на основ! апарату нетрадиц1йних лог!к. : Зв!т про НДР (заверш.) / ЛШ; Кер1вник Пас1чник В.В. й 01910041765. - ЛЬВ1В, 1991. 257 с. - В!ДП. аик::-'.: Грабовецький В.В., Люб1нець Я.В., Тавпаш В.А.

10. Пасичник В.В., Тавпаш D.A. Использование аппарата К-значных логик в анализе РБД с возможными неопределенными значениями. // Сборник тезисов докладов II Международного научно-технического семинара "Теоретические и прихладные проблемы моделирования предметной области а системах баз

данных и знаний", Туапсе, 20-26 сентября, 1993. - с. 86-91.

АН0ТАЦ1Я

Тавпаш Ю.А. Методы и средства булевой и К-значной логики в системах реляционных баз данных.

Дисертация на соискание ученой степени кандидата технических наук по специальности 05.13.17 - теоретические основы информатики, Институт прикладной информатики, г. Киев, 1994. ПроЕеденныо исследования связаны с разработкой теоретических и прикладных методов и средств проектирования, поддержки и ^ обновления реляцийнных баз данных •с возможными неопределенными значениями. Основой исследований являются сведения о типах и структуре системы ограничений целосности, которые накладываются на данные отношения, используя аппарат булевой и К-значной логики. В работе предложено и обосновано понятие К-значной зависимости данных, аналитических соотношений. Разработанные алгоритмы манипулирования системой зависимостей и обновления реляционной базы данных с возможными неопределенными значениями внедрена в промышленную эксплуатацию и в учебном процессе.

Tavpaah Y.A. Boolean and K-value logic methods and tools In relational database systems.

Dissertation proposed ior attribution' of technical sciences candidate degree In speciality 05.13.17 - theoretical foundations ol lnformatlc, Institute of Applied Informatics, Kiev,1994. ' .

Treats the problem of relational databases with possibly and partly undefined data design, support and updating theoretical and applied methods and tools developing." This proces Is based on Information about consistency restrictions system types and structures applied to given data using boolean and K-value logic. We propose and define an K-value data dependence and some analltlcal expressions. -40ur data lnterdependency system manipulation and updating algorithms are currently used In lndastreal and educational organisations.

Клвчов! слова : реляШйна база данях, К-значна .озлешють даких, невизначенЮть, оновлення.