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

РГО 0.1

кшвська м1сбкл деряавна адщн10тращя тнстйтут прюшдко! нееорматики-

На правах рукошсу удк 681.3

квдш тарас володимирович представления неч1тк01 1к5срмаци в базах дашх

рглящяного типу

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

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

шв - 1993

Рг-' ота виконана в 1нспгаут1 прикладно I Информатики

Науковий кергвник: -член-коресповдент УАН 1 РАН, д.ф.-м.н., проф. А.О. Стогнтй

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

член-кореспондент УАН, д.ф.-м.н., проф. В.Н. Редько (м.КяХв) К.Т.Н., А.П. СЬОМИК (М.КИхВ)

Пров 5дна оргашзацхя - 1нститут програмних систем АН Ух'фахвд 4 (м.Кихв)

Захист вШудвться С(1(НЯ 1992/р. о 4^ год,

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

3 дисертацхею (ложна ознайомитись в бхсШотецг шституту прикладной информатики.

Автореферат розхслашй ЗрЦОН/^ 1993 р.

Вчений секрётар Спвд1ал1зованох Ради Д 166.01.01

ГиаЪчк В. п.

"АТ'АЛЬНА ХАРАКТЕРИСТИКА РОБОТИ.

Лхтувльн1сть проблем. Прих1д ери електронних обчислювилышх машин, гфагнвннй розв'язувати hobi ггоактичнг задач!, якг породзнуються все б!льш i б!льш складними моделями, прискорило потребу в отримаши та обробц1 все гИлыц складно'1 1нфсрмац1Т. Значна чэсткна 1нформацП недоступна лшдиш в форм! ч1тко вязнэчеиил чисел г по ргзшге причинах е неточною, с^пере^ливою, непсвною. Остеннш часом значко актив1зувались досл1джвння в областт розширення семантично!' виразностг моделей даних i знэнь. В русл! цього напрямку розвиваеться шдхХд гюв'язаний з розширенням можливостей представления х мзшпулювання неточними, розмитимм i частково незаповкеними значениями в базах даних реляхийного типу.

Теор1я покилок t теор1я ймовхрностей- два класичн1 подходи до представления неповноти" шформацп'. Але вони вияляються недостатньми при появ! нових потрэб. ДШсно, обмекентсть теори помилок полягае в тому, що вона не в1доСраяае В1дт1нки. Принцип "все або к1чого"- характерна риса Teopii номилок, тод1 як теоргя ймов1рностей враховуз в1дт1яки, градацИ невизначеност!. Проте теор!я ймовгрностей пропонуе надто нормативн! рамки для облшу суб'ектавних суджень. Суб'ективн! ймовгрност!, не дозволяють в!др1зняти piBHi шформативност1 i виявляються малозастосовними в ситуациях, коли мало 1нформацИ, або у вшадках повного незнания. В Ц1й робот! в основу Шдходу до представления неповшп хкформацп в базах даних поставлено с!мейство Mip невизначенност:, як! ticho пов'язан! з Teopieio помилок,- м:ри моклизостг.

Ochobhi результата по вказвному напрямку бут опублтковаш в роботах Дюбуа, Прадэ, Умано, Pay, Тестемале, Бтскана, Менаде. Проведений анал1з публ!кац!й вказуе на ряд лерозв'язаних проблем у Ц1Й o&nacTi:

- в!деутн1сть единого гпдходу до назначения неч1ткого вгдношення;

- не зустр1чались роботи, як! С торкалися гатання побудови Функцт i межливих рояширень POSS у внпадку викориотання розподШв мокливостей для представления неповноти хнформацП. Як наелi док цього В1дчрктим заливалось питания визначення взаемоав'яаяоет! неч tтких термлв, що мае прямий вплив ка cnoci6 оЩнки запитхв, га^удову розширено! реляц1йно'1 алгебри;

- слабо вивчен! проблеми побудови 31Дповхдаих алгебр, mi

чадекватно ъхдоОракяють прсцэсн каШпулювання в рв.пяЩЗнхх базах;

- на даякй час практично в!дсутн! промислов! вар1внтн вдет» рвляц1Яних баз даншс, як1,дозволяють моделюввти реалъд! ситу ад И ; нечеткостями, розматост^йи 1 неточностями.

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

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

- 1нтегрец1я р1зноман1т1ИХ шдаодЦз, побудова ушфт ковано: система понять, визначень, позначень;

- кокцентрац1Я досл1дницьких зусилъ на. нерозв'язаних проблема: представления та обробки Ееч!ткс! !нформаци:

- побудова досл^дного прототипу СКБД, яка дорволяе оброблят неч!тк! значения.

Ивукова новЬзна дисартаии полягае в наступному:

- введено поняття множини нечетких тверджень на базовхй мнеакин под!й О. Вказано зв'язок м!» мнохикою тверджень та в1дпов1дни розпод1лом можливост! зс(и), досл1даен! влаотивост1 нечхткп тверджень;

введено . ун!ф!кований п!дзпд до визначення нечхтюэп 1нформац1йного в!дношвння. Це досягагться шляхом розгляд неч!ткото шформац1йного в1дношення як деякоГ множили нечетки твердаэнь. Тили неч^ких тверджень задають форми нечХтког в1дкешення. Введен! неч!тк1 нормальн! форми, показаш осковн сп!вЫдаошення мш нормальными формами, !х ьластивоот!;

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

- нобудована мова машпулювання нвЧ1ткими даними ГЗОЬ, дсолщжен зв'язок основних конструкШЯ мови 1з виразами неч1Тко!' реляцШю алгебри;

- розроблеяд пршзцшш та алгоритми побудови програмного комплекс досл!дного прототшу СУБД.

Пагода даол1двань Оазувться ка ссновявх гомюгсеннах тдорП' |1дношань, формально)! алгебри 1 алгебраЧчшх систем, штематично'т 10Г1КИ, ТеорП мож.щвост9й, твори нэчп'ккх мноеин.

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

конкретно: 1нформаЩйних системах.

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

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

- пря ровробц! прикладних 1нформац1йних систем для промислово'1 експлуатецП;

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

Реал1зац1я результат гв доел! дне кь. Результата наухових досл1дкень викорисговувэдисъ при виконанн! дбркбюдявтниж робгт, а також догов¿рних роб!т для Бориславсько! фабрики нетканнкх матер:ал1в, Еориславського вкспвриментального ливарно- мехамчного заводу, 1вано- Фрагаавського заводу кэрам1чно- ст!кових вироб!в, 1вано- Франкхвського заводу "Прокприлад".

АпроСацхя робота. Результата дисертац1йно* робота допов!дались на семинар! "Нов1 1нформац1Епг технологах" I 1нструментально-технолог1чн! засоби П1дтримки прийняття ршень* (1н-т к1бернетики 1м.В.М.Глушкова АК УкрЕ1ни, 1932), на науКових конференциях иро$есореько~ викладацъкого склада Льв1вського дал1твхв1чвого институту (факультет комп'втерно* твшШ та 1нформац1йних технологи, 1950- 1993 рр.), на науховому сем шар! Шсттуту "Лрограмаих систем" наукового комплексу "1нститут к1Сернетика хм. В.М. Глушкова АН УкраКни", кафедр теорИ прогремування 1Швського державного университету, кафедр} прикладной математики вського 1УШтехя1чного 1нституту.

Публ1кац13£. По теш дасерташйноУ робота опубликовано дев'ять роб!т.

Структура та об'ем робота. Дисертацхя складаеться 13 встуиу, п'яти розд!Л1В, Еисновку, списку основноI використано! Л1тератури I додвтку. Робота м:стать ПС сгоршок основного тексту, список лгтератури 13 76 найменувань.

!

КОРОТКИЙ 5М1СГ даСЕРТАЦИ

У встуш обгрунтсвана важливХсть тс актуальнють штань представления нечгтко! мформацп в базах , даюк релящйного типу. Приведений короткий аналхз дослхдкень в областХ представления вепознс 1 шфермат г в базах дзних релящйного типу. Зформульована Ц1Ль дослхдкень, наукова новизна, основнХ положения, ща виносяться на захяст.

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

Дервходячи до застосування теорп можливостей в ргзноманхтних областях (в тому числ1 в БД) виникають ситуаЦ11, коли розподХл мохливостХ на базевхй множил в явному виглядХ не заданий. Неявна тХльки множина дэяких твердаеяь про можливхегь чи нео«х1Днхсть нэчХтких под1й (в звгальному випадку). Вшшкае питания побудоья розподХлу иохжвоат! на базовгй мникшп подХй П.

Тут сгостер! гаеться прмщилова В1дмшн1сть мХк розподхлами мовливост! та ймов1рност1 як субъективною та объективною мхров. РозподХл йков:рност1 на базовому ймовхрнХсному простор1 не заложить В1Д рхвня нвших знанв I щлком вкзначаеться ф1зячнши влястивостями явища, яке моделюеться. Розподгл ймов1рносп може змхнитися тхльки при змХнх ймовхрнхеного простору. Розподгл можлнвостХ виступае, як функцХя вгд знань про прост1р можливих подХЯ. Ягацо знания повнх, то вхдповХднлй розподхл можливост!

в

;орхвнюе одшшц б однхй единхй точц}, яка вхдоовхдае поди, цо *1дбулася. Якщо нема« hihkoi !яформац1х про мозиши поди о, то ;1дпсв1дний розподхл можлевхст1 дор1внюе I у bcix точках. Тому 1еобх1дно вказати зв'язок м:ж знаниями про мноккну годой Q i хззгадхлом можливост: к(и), який в1дпов1дае цим знаниям. Шд =наннями розум1еться множина з1домостей, яку мае суб'ект чи трупа зуб'ектхв t в1Днооиться до предметно! област1, що задаеться Q. Знания про О представляються у формх множини нечхтких тверджень.

Означения I. Твердаеншш на множил елементарних нодШ Q хазиваеться триплет (АД,а), де feiU.fl}, ае[0,1] i . А - в загальному вкладку нечхтке шдмнокина 0.

Кожне твердаення (A,i,a) в залежност! .вхд значения f . задав *жлив1сть (i=II) чи необх1Днхсть (f=N) а поди А. Кожне твердження. задаеться деяким суб'ектом.

Для .дошльшн шдмнокини А£П (в загальному виххадку нечетко!) j ч&[031] Еведено функцП, области зизначення котрих е О

Р Ь (U) Л а' ^ > а'

11, HA(U) < а,

- N , , Г 1_а> Ми) < а>

I. №) =\

' . I 1, ц;(и) i а,

це р.А(и) - функц!я належност! неч1тко! множини А.

Нех&й дояка множина нечхтких тверджень, заданих на и.

По&на^имо -херез P0SS(M(fi)) неч1тку множину, функхЦя належностх яко! задаеться наотутшим виразом

1 min Г Inf {F^e(u)|(A,fta)GM(Q)}t 1].

Для того, щоб иечггка множина ' P0SS(M(fl)) задавала розхюды можливостi JT(u), проводиться нормування P0SS(M(n>) у випадку -ii НЕнормованост:.

Сзначеняя 2. Ыожлив1сть дов1льно! элементарно* хгодп ucn в1Дносно множини нечхтких тверджень НЦП) визначаеться наступили виразом

E(U|M(Q)) = lT(u|Nor(POSS(M(Q))))

Наведене Еице означения встановлюе зв'язок мхж мнохикоы нечхтких тверджень i . в1доов{длтхы розпод1лом можливост!. В подальшому прйг/скаеться, що мношша тверджень M(fl)- нормована.

Досл1д::эш властхгвост! иэч!ткшс тверджень, доведено ряд штухтквно очевидное властивостей, як! тидтверджують природн!с?ь та доцхлънХстъ введения властивостей. Введен] формалхзми слутать базою для наступних нобудов в розд!лах 2.3.

В багатьох випадках множина неч i тхих тверднэнь володХз певнок> структурою. Розглянуто вкладок, коли мношта тверджень задав розгодхл мокливоствй на сукупност1 розбитт1в fS^}^ базово* множини П. Ця еитуацХя. е типовою в 1нформаидЯних системах, при представленн! неловкоi хнформацГХ,

Нехай {2 деяка множина розбиттХв множини П, i на кожшй множин! 2 заданий розподхл можливоотх и(с^), де o'eSv. Кожен розподХл можливостх y-joj, 1=1,2,... ,п мокна розглядати, як деяку мэонину твардаень М1 (П)= {(А.П,^ (А)) | AeSt>. ТодХ сукутпсть розпод!Л1в мокливостей {(i) ", задав множину тверджень йц(й) на ¡лнонин! П. Тобто

IA (П) = и К1 (0) И1 v = i

Доведена наступив теорема, яка мае широке застосування в аналхзх та обробщ нечхтних ХнформацХШшх вгдношенъ.

Теорема I. Якщо для дов1льно1 Шдмножини {Е 1

m

довХльних о sS юнуе ue п о. таке, що VS^S (3=1,2,... ,m)

• ' 1j j = » 1

Эс^е^ тзке/ що ueo^ i и^(ок)=1, то

1) VS. (Ы ,2,...,n) i VaeS II(a (М^ПП^о >,

2) ViS }.m c{2 } n i VoeS

и I"1 ii = l .. ij

ж n о |M (Q))= min n(o.|Mu(n)J= -min Сци(о )],

j = lJ ^ ) = I.....m ' j ъ i ..... rn '

3) V(S. E .T0 для VDj (Dj - неч1тка множина, задана на розбитт1 2. )

Я( л В.|М^.(П))= min [П(В|К^(П)1 =

min sup min Гг.(а), (х (о)], j = t.....m oeSt j 1 "

де г (• ) - функция налехностХ нечхтко! множини D;.

У кругам? роздШ даеться зислачення ноч1таого 1иформацХйного ыдаоиення, ввэдеш floro hs4ítkí нормальнГ .фор®. Вказаний зь'зок Mise нечхткши нормальними формата, даеться оементячна штерпретэц/я кечхткого кортежа. Псвудозана функцхя можливих розиирвнь POSS, доведен! VI вдастивост!. Досл1да;ен1 питания взаемозв'язнсстт твэрджвнь задают на рХзних атрибутах. Значке увага придхлена неч1тким в1дношокням представлении в 215®, приведено доведения ряду властивостей цех вхднонень. Дослхдауеться питания побудови оберненого воображения POSS"1.

Кехай О- мяожина об'ектХв реально!' д1Ясност1 або' деякох i'í час тине, яку надалт будемо назявати предметною области. Шд об'актами предметно* облает! розумтться íi анементи або i'x взаемозв'язки. Групп под 1<$шх об'ектХв утворювдть класи с.б'ект1в С ,0 ,,.,0к. ОО'ектк волод!ють Властивостяш, якг назив'аються атрибутами 1 спхвв1дносять деяке значения i3 мкошкн зпачекь даного атрибута з- кожиим об'ектом в Miaci оО'екттв. Множила значень атрибута А позначаеться через В (A) i пршускагться, що Р(А) м1стить элемент в, який характеризуя випадок незастосоЕНостх атрибута. Нехай Rt ,Rz,.. ,Fk- мнокини атрибутов, як i характеризуют в!дпов1дно класи об'екИв 0, ,Ог,..,Ок. Незначимо через VI(о,А) в!добракення, яке ставить у в1дпов1,сшсть кояному об'екту о значения атрибута А.

У випадку неповног хнформацхх значения атрибута, що характеризуй деякий об'ект, ноже бута невхдемим, не повн!стю в i домим (вхдома т1льки деяка шдшотдша област1 значень атрибута) чи невизначеним (вхдома функция розподхлу можлизоетт на множинх значень). В загальному випадку може бути вХдома фуншця сум!оного розподхлу можливост! декхлькох значень атриОут1В для дек!лькох об'зктхв. Наприхлад, вiдолю, що значения атрибута для дек1лькох об'екпв cniвпадав. KpíM того, множили об'ектХв 01",02,..,0 ножуть бути такеж не повшетю визнэчен!, вхдома' можлиз!сть чи необх1дн1сть налешостг дов!льного об'екта довольному класу.

Нехай 0*,Ог,..,Ок- деяк! мнокини об'ектхв предметно* област1, для яких справедливо, що оеО* тодх i тХльки тодх, коли

г знания суб'екта IlioeOJ про стан предаетно!' >0 v облает! J

s/чввидно, що со*, i у вияадку повноти хнформац'П' 0*--=0t. Тому, якщо шформацхя неповна, будемо представляти 1нформац1.ю кро об'екти множини О* вводячи додатковий атрибут STATUS., яотй характеризуй належнгсть об'екта до 0i.

В роботi пролонуеться використати атрибут STATUS для представленья можлквостi налекностг О , та мокливостх того, то об'ект, икий представляться даним ксртекем не налегать О.. Позначимо через VI (о .RuSTATUS)- кортек t на атрибутах RuSTATUS, що визначаэться наступним чином:

I) YAeK t£AJ=Vl(o,A);

{Т ,ямцо оеО (True) 1

F ,якщо ogOt (False)

Нехай ы- в1дн0ш0ння 3i схемою RuSTATUS, яке визначаеться наступним чином

w = (VI (o,R uSTATUS) | оеО* >.

Вхдношення и вiдоме т1льки у випадку повно! 1нформац11. Будемо його назквати зовнйшни втдношеиням, а VI(о,RuSTATUS)- зовншньм кортежем. Недовну 1Вформацхю будемо представляли неч1тким 1Нформац1йним в1дношенням г (вяутрШшы вхдношенням), при дьому со. будемо називати розшкренням неч1ткого вгдношення г t позначати ext(r). Надал! будемо вживати термХн чхтке вхдношення, коли йде мова про звичайне хнфорлац1йне вХдношення реляцхйннх баз дангас.

Оаначення 3. Нечике 1Кфоры£ц1йне вхдношення г 3i схемою й- це деяка мнокина твердаёнь заданих на множил! Q(R), де Q(R>- мнохина всемоасливих вхдаошень si схемою RuSTATUS,- на кожному з яких виконуеться функциональна залежнхстъ R STATUS, дв D(STATUSMT.F).

Означения 4. Функдхя можлизих розшфень - це функция POSS, яка для кокного REU i reRelT(R) визначяе розшдал мокливост! заданий на Q(R) такий, що для довольного ueO(H) цу(и) = П<Шг).

ВведенХ нэч1тк1 нормальнх форми (КННФ, ОТ®, 2ННФ) неч]ткого вшхошення.

Означенна 5, Якщо H64iTK6 вхдношення г 3i схемою R= AtA2...An представлено у виглядх множини нечггких в!дображень атрибута AtAz___AnuSTATUS в D(RuSTATUS), то будемо говорити, що нечхтке

в!дношеняя г знаходиться в по- кортезн!Я неч!тк{Я нормальней Форш (КННФ).

Означения 6. Кеч1тке вгдношення г представлена в КШФ будемо ¡юзивати замкнеиии, • якщо для довольного оеО* (3Ïer) (Ç (t )=о) . В противному вкладку неч1тке в1дношоння - незамкнене.

Запропоновано метод побудови функцп можливих розширень для кеч i тких вхдношенъ предетавденлх в КННФ, доведен! наступи! твердження:

- якщо неч!тке в!дношення г - нормоване, тодх кожей кортеж ter також нормований;

- якщо 1снуе ненормований кортеж ter, тод1 нечхтк» в!дношення г тмсож ненормоаане ;

- якщо нечхтке в!даошення г знаходяться в КННФ i заданий корте» tsD(R), тод!

n(teext(r)! г) < max (t,T) ). ter

Якщо нечхтке вхдношення г представлене в КННФ, то дов1льний кортеж ter задав розподхл можливост1 значень агрибут1в RuSTATUS об'екта |(t). Проте в багатьох ситуацхях знания суб'екта про значения атрабут!з об'екта Ç(t) е невзаемозв'язаними. Тобто мо«лив1сть довхльного твердження про значения довмьного атрибуту AeR, нэ заложить в!д значень !нших атрибутов RuSTATUSXA. В цьому випадчу просттие (як з точки зору наглядност!, так i обробки) вказуввти можлив1 значения кожного атрибута для об'екта окреко. В зв'ягку з цим зьедемо поняття домена атрибута. ,

Оаначення 7. Домекои атрибута А називаетьея множила всеможлиЕих таердхень допустммих в базх даких про значения атрибута.

Домен атрибута А позначаеться don(A). Легко бачити, що поняття домена атрибута ч природним розширенням цього поняття в чхтких релязийних базах даяих. Тобто, ямдо в!дношення ' ч!тке, то дов!льне твердження про значения атрибута е елементом множини D(А > i поняття мнокини значень та домена сшвпадають (D(A)=dom(A)). Якщо в.Оазх даних допускаеться представления неч!тких тверджень про значения атрибута а, то доб1льний елемэит aedom(A) буде нечеткою пiдмножкною D(A) i буде характеризуватися функцтею розпсд!лу моклиБОСтей (,ta. Тому розглядаються домени атрибутгв, як! с множиною всеможливчх нечхтких множич заданих на D(A), тобто

(Юш(А) = 10,1

Означензя 8. Якщо неч!тке вхдношення г 31 схемою Е=А1Аг...Аг1 прэдстэвл&не у вкглядт множит* • вадобраквнь . атрибута А4А2 ... .А^иБТАПК в йот(А4)Хйога(А2 )X... Хйэт(Ап)Хйот (ЭТАТОБ) , то будемо говорити, що нвч!ткб В1дношення г представлена- в пера1й нэчхткхй ьормальи1й форм! (1ННФ).

Розглянуто функцх! С^^ та , як1 задають перетворення нечхткого в!дношення представленсго в 1ННФ в нечггке вхдношення в КННФ т навпаки. Доведена наступна тэорема.

Теорема 2. Нехай г та в - дав1льн1 неч1тк! "в1дношення представлен! в1Дпов}дао в 1ННФ та'КННФ. Тод1 I) РОЙЗ^^г)) = РОББ(?);

2} (I) < в; ^

3) г = С^(С1^к(г)), якщо неч!тке в1дношення ? - кормоване;

4) 3 г 0^(0^,(8)).

Неч!тк1 в!дношення, як1 представлен! в КННФ та 1ННФ, викликають ряд складностей при Хх обробЦ1. В основному Ц1 ' складност! пов'язан! з немскливХстю !дентиф!кувати кортеж!, ям представляють !нформац!ю про один ! той же об'ект. Тому розглянут! нечхткх в!дношення представлен! в 2-й неч!тк1й нормальшй форм!, як! зн!мають цю проблему, проте дещо зменшують семантичну виразн!сть нечхткого в!дноиэння.' Перевакно на практиц! 1снуютъ оомекення вхдкосно того, де у неяркому вхдношенн! мокуть появлятись неч1тк! даш. Типовий випадок- заборона неч!ткостей в л»б1й компонент! первинного ключа.

Означеняя 9. Якщо-дач!тке вхдноиеннл г зх схемою Н=А1Аг...Ао представлена у вигляд! множини вхдображень атрибут1в А А ...А иЭТАТОБ в В(К)Хйот(Ни5ТАТЦ5\К), що для дов!льних двох

12 Г|

вхдобразкень ^ ! 1; 1^Г.К]?! ^[КЗ, то будемо говорити, що нечхтке в!дношення г представлена в другхй нечхткхй норньлыпЯ форм! (2ННФ) з! схемою (й,К).

Очевидно, щс довхльне неч!тке в!дношення г представлена в 2ННФ знаходиться такок в 1ННФ. Якщо К- ключ множини об'ектхв 0*, то !нформац!я про об'екти О* неч!тким в!дношенням г, яке знаходиться в ЧБШ 31 схемою (И,К). 0ск!льки значения ключових атрибутов

кортежа' ter однозначно назначать оО'ект о=£($)г.то pisHi кортек1 представляють хнформащю про pi3Hi об'екти. Тсбто (VÏe?) (Vt2er)

якщо ■ ФункцХя 71:0(r)xtO,1>SuSTA:i!DS->

D(iO,nRuSTAT'?S) однозначно^ визначае фучкцхю VI'; D(K)x Ш,1)Ви5ГАТШ-» D(f.0,1)HuSTjmJS) х- (VtEKleD(K) ) (VAîRuSTAÎTJS) , якщо VI' (t[X],A)=a, то a e значениям атрибута A на об'гктх, -який визначаеться кортежей tIK] задании на ключоеях ■ атрибутах. Розширимо область вивнзчэння функцп VI' на повну ккожину D(K)-Якщо tfKîêD(К) î не iCHye osO*, що tCKJ=Vl(o,K), то VAeRuSÏACTSVK Vl*(tCKl,A)=e. Приведена розширення' VI' повнХстю узгоджуеться Хз семантикою елемента s. Вхдахтимо, що значения функцП VI' на D(K)X(RuSTATUS\K) повнхстю визначае ext(r). Справедливе також зворотне твердження, тобто ext(r) визначае VI'. Справедливi наступи! твердження.

Леиэ I.. Нехай г- нвчхткв вХдношення представлене в 2HHS 3i схемою (Н,К)J Якщо ножен кортеж яэчхткого в!дношэння г нормовэний, то нечхтке вгдяошення г також нормоване.

Теорема 3. Н&хей задано нечте вХдношення г представлена вг

2НН25 3i схемою (R,K), послхдовшсть ftjfKH тамножини

Г ïl Г Ч1 =1

поел ровностей А' ' , а' 1 для 1=1,2,..П), де t [KJeD(K),

I 1 Jj=1 I 1 Jj=1

A^eRuSmUS, dJedomiAj ) (t=t ,2,... ,m; J=t ,2,.. )- Для довхльних 1<i ,1 <m tt [ШЦ [Kl i Vieil,...m), У^.Л^е C1,. ..,!>'

A VA.*. Тодт, якщо для кожного tJKl (1=1,2,.. ,га) icHye ïer, що t СКЗ= t ÎKJ, то

ml. . „.

П ( л л' Vl'(t. [K],Ai')=4' I г ) = 1=1 Л=1 1 1

= mln mln max [щ VI' (t [Kl ,A? )=al г

1=1 ,'2,...га 3=1,2,...1 aeD(A>)

де Цд] - функцХя налекност! иеч1тко"1" множини й' .

Показано, що хенуе обернене воображения до функцп P0SS, яке позначаеться POSS"1 t воображав довХльний розподО можливостХ заданий на ÎJ(R) в замкнута нечхтке вхдношэння представлене в 2НН5.•

P0S3'"(B) >{t| (3weQ(R)) [((i.B(tó)>0)A(3teu) [(tCK3«tCKÎ )л

'л (VCeRSTATUSVK) (VceD(C) ) (|^[CJ (c)=H(Vl ' (t Ш„С)=с| B)]j ]•>

де В- нечетка мноюша визначена. на fl(R), яка задана своею функЩею налетаосп Показано, що дош дов1дьного замкнутого нормованого нечхткого втдаш.ення, представленого в 2ЯНФ, справедлив! вирази

г = POSS'^FOSSC?))

В 3 POSSESS'1 (В)) Введен! обмеиення на B94ítkí дан! (FE- залежное«). Ознаяення ÏO. Нэхай г- нечгтке в!дношення, представлене в 1ННФ, si схемою , H Д,У£И i Нечгтке обменення !снування

(?Е~залежн1сть) X-)(a)Y задов!льняе в!дношвння г, якщо для когоого кортежа ter Sp(t(X))<a*Sp(t(Y)), де для довыьно'1 множили атрибут ib Z

Sp(t(Z))= min Sp(tCAÏ).-A&Z

В цьому означенн! Sp- Mipa спэциф!чноот1,_ яка запропонована Ягером i для скхнчвного випадку, коли елемвнти D(A) вгорядковаш по спаданию ¡^д] мае виг ляд

~ ' р 1 • ; 1 г »

Sp(ttA3) = J —- da = HtAl^^ttAl^«)]' 0 ¡a' •>

де a=sup{a|Fa#0>, |D(A)|=n i по визначенню ^ttAJ^m-í^0-

Наведено акстми виводу FE-залежностей. FEO. Зб1льшння: Якщо а4<аг, тс i3 Хт(а4)У випливае Xi(a )Y. FS1. Рефлектавн!ть: Х>И')Х. FE2. Попавнешм: 1з Xi(a)Y випливае XZ-j(a)Y.

FE3. Ддитивн!сть; 1з Х->(а4)У, ' X-»(ïia)Z випливае Xt(u3)YZ, де a3maxt,aítaz).

FE4-. Проективн1Сть : 1з ,Xi(a)YZ випливае Xi(a)Y.

FE5. Трвнзищвгпсть: 1з XifaJY, Y-)(ct2)Z випливае Xi(aa2)Z.

FE6. Псввдотранзитивнтсть: 1з Xi(a )Y, У?,-,(аг)Г вишжвге XZ-»(as)Z, де a3=max(aa2,a2).

Доведена справедливЮть i повнота система аксЮм виводу (FE0-FE6).

TpeTifl роздгл присвоений питанию побудови нечгтко! реляц!йно!' алгебри. Введен! поняття природного тюашщаты, адекватноот! i обмеженост! реляц!йних onepaïopiB на вкладок неч!тких в!дношень. Розглянуто зв'язок реляцхйних оператор:« те залежностей даних, що п!дтримуються на cxeMi рэляц!Йно!' Яази даних. Основна увага нридглена неч!тким в^дношенням представленю,; в 2НКФ, для яких гснуе вгдобрагення POSS"1, що дае змогу природам чином узагальнити gchobhí релящйн! оператори. Введено ряд реляфйних onepaTopie, як! не мяють аналогу в традиц!йн!й реляцгйнгй алгебр!. Досл!джен! властивост! введения оператор!в, ïx зв'язок ■ is авичайними реляц1йними операторами.

П!дх!д, що розглядаеться в дксертацП, в деяк!й Mipí аналогi4Hïffl гпдходам до визначення релящйно! алгебри на нечгтких вхдношеннях, дсмени атрибут!в яких е множикою всеможливих Шдмновин D(A), тобто dom(A)=2®^. Щ пдаоди детально розглянут! ^ в роботах Кодда , .Ппського, 1мел!неького , Ыскапа.. В!дзначимо, що у вищезгаданих роботах приймаеться, що POSS - це воображения Reit(Я) ■+ P.el(R). Як видно !з другого розд1лу, в дан!й робот! зроблений в!дступ втд траддацгйного визнэчення функц11 можливих розщиренъ FOSS ! задаеться , що P0SS - • це воображения Rel(R)-»C5(R). Очевидно, що традивдйний шдоад е частковим видадком наведеного, ооктльки дов!льаий розподхл можливостей, заданий на O(R), однозначно визначае розпод1л можливостей, заданий на Rel(R). СЗернене твердження не BipHe.

Для визначення реляшйних опбратор!в на неч!тких в!даошеннях резшреко кожний укарний оператор на' П(Я), 6iHapmtít на n(Ri)xn(RJ). Розширення оператора 7 лозначаеться 7':

Означения II. Пехай заданий оператор 7 на Re i i 7' на П. 7'-природне розширення 7 при виконанн1 наступних углов:

1) якщо 7 - унарнзй оператор, то для доильного иеП

*H°SMIUS«T (T.W) = 7(®ROSÏATÛS=T(u1)

i для дов!льного reRel

7'(POSS(r)) = P0SS(7(r));

2) якщо 7 - б!нарний оператор, то для довьчьних ui(usefl

VSTATÜS^W = KR°STATUS=T(u.> ? STmS*T(V í ^ля дов!льгох rifr2e Reí

POSS(rJ 7' POSS(r?) = POSS (rt 7 ra).

Зформульоваш умови узгодженост! узагальненого реляцихно! Оператора 7 визнвчайого на Reí) 13 звпчайнш реляц!йним операторе 7 шзначеяим на Reí.

* Означения 12. Яехай заданий оператор 7 на Reí 1 7 на Reit, "j природнэ роззхрення 7 при зикокаши настушшх умов;.

1) якщо 7. 7 - унарн1 оператсри, то 7(г)=7(г) для дов!льног reRel для якого 7(г) визначенкй;

2) якщо 7,- 7 - ÖiiiapHi опврзтори, "ео г4 т~г2 = г 7 г2 для дов!лънжх г4,ггене1 для яких г4 7 Г2 ^значений.

. Наступие означення описуе даальну поведШку узагалькеног оператора.

Означення 13. Нехай задан: оперзтори 7 на Reí 17' на Q i 7 н Reit. Оператор 7 е точяни узагальненням 7 Ыдносно розшрвння 7 при виконаьят наступних умов:

4 J) якщо 7 - унаркий оператор, те для довольного геНеЗ1

7' (P03SC?)) = P0SS(7(r));

2) Якщо 7 - бшарний оператор, то для дов!лышх r^i^eKelt

POSS(г ) 7' POSS(rz) = POSS (?f 7 ?2).

Тут 7'(POSS(r)) i POSSírJ 7' POSS(r2) - H94ítkí множим функцП налвкност! яких задаються наступними виразамл

jj^ív) = max { U~(u) I ueQ(R),v=7' (u) ">,

= max t mln (p~ (u),|j~ (u)) 1 uj6n(R),u2eQ(R),'7=ui7,u2>, 12 -P P V ^

де цу,; fxp , - функц!'i нвлвшосп нечетких множин P0S3(r),

* 2

POSGÍr,), POSS<?2).

На жаль, нэ завади у(POSS(г)) або POSS^) 7' POSS(r2) мокут бути представлен! у шглядд FOSS(q),' для деякого q. В такю внпздках^узагальнення вябираетъея тэтам чином, щоО воно mí стилс 7'(POSS(г)) або P0S3(г4) 7' POSS(r2) з няйменшими "доповяеннями". Означення 14. Кехай задан! оператори 7 на Reí, 7' на П i 7 нг

ielt. Оператор j адекватний 7 bijhocho розширення 7* при виконенш ¡аступних умов:

1) якщо 7 - унарний оператор, то для дсв1льного reRelt

7' (1?0SS (г)) с P0SS(7(rfl;

2) чкщо 7 - сИнарний оператор, то для дсвгльяих eRelt

POSS(?i) 7' P0SS(?2) с P0SS(?1 7 гг).

Оператор 7 обиеяеняЯ для 7 втдноско розширення 7' при виконаия! наступких умов:

1) якщо 7 - унарний оператор, тс для дозпаного reRelt не хснуе такого qeReit, що

7'(PGSS(r)) £ POSS(q) с P0SS(7(?));

2) якщо 7 - бшаркий оператор, то для довгльнкх ?lt?2eRelt не i снуе такого qpRei 1, що

у PORS(?,> с POSS(q) С P0SS(?1 7 ?„).

Очевидно,']«':! якщо 7 е точне узагальнення 7 в1дносно 7', то 7 -. адекватний i обложений для 7 вхдаосно 7'.

Розглянуто узагальнення реляцтйних ошратор1в на вхдношення, якт представлен! в 2ННФ. В цьому випадку, як показано в роздШ 2, icHye функц!я РОЗЗ"*, яка однозначно визначае" втдображення i3 мнокини в Reit (R,К). Зг1дно uiei Фуякцп визначаеться

узагальнення довзльного рэляц1йного оператора 7 для якого задана розширення 7'.

Означенна 15. Нехай заданий оператор 7.на Rel i його розширезяя 7' на П. Узагальнення 7 оператора 7 вхдносяо, 7' для в¿дношень,представление в 2ННФ, визначаеться наступними er; t вв i дноше ннями

1) якщо 7 - унарний оператор, то для доб!льного .ieRe.lt Ш.К)

7(г) = P0SS"4 (7'(POSS(r));___ .

2) Якщо 7 - бтнарний оператор, то для дов!льши г, ,?2eRelf (П,К)

rt 7 г2= PQSS"1 (POSS (?t) 7' P0SS (?2)).

Теорема 4, Нехай 7 - узагальнення оператора 7 вхдносно 7' для в!дкошень, представлених в 2ННФ. Тодх, якщо 7'- природне розширення 7, то 7- природне розширення, адекватний i обмежэний'

оператору j вхдаосно т'для иормовэнкх повеих нечптшх в1дношень.

Наведен! визначення наступних нечНких реляхийнмх операторов-, об'еднання, перетин, р!зниця, доповнення, виб!р, проекщя, з'еднання. -Показано» що для кожного з вищенэведених нечетких операторов справедлив! умови попередньо! тэореми, а значить i справедлив! насл!дки nie! теореми. Введено два нових релящйних оператора-KEY i LEVEI. для обробки нечшшх значень.

Чатвертий роздал 1фисвячений розширекню • мови ман!пулюваннл даними SQI на вшадок неч1тких в!дношень. OratcaHi ochobhi синтаксичн! конструкцн мови, обгрунтована дсшльн!сть ряду нововведень, вказаний зв'язок is реляцгйноад алгеброю.

Найпростший блок SELECT нови SQL е композшцею д'екатового добутку, вибору та npoenuii. Блок'SELECT в FSQL дещо мтняеться^ Иого загальний вигляд записуеться наступним чином

SELECT <сшсок-атркбут1В-1> [KEY <список-атрибут1В-2>] PROM ССПИСОК В1ДН0ШйНЬ> С JOIN CONDITION <умови-з'еднапня>J i WHERE <неч1тка-умова>] [LEVEL <умова-р!вня> ]

Зупинимося на осаовних ида!нйостях SELECT SQL та SELECT FSQL.

I. Результатом блоку SELECT FSQL e нечи-ке вщюшеннл, представлена в 2ННФ, 'з! схемою (<список-атрибутiB-I>, <список-" атрибутiB-2>). Речення KEY можв Oyти олущене, в цьому випадку ключов! атрибути вибираються по замовчуванню.

Z. <умови-з'еднання> е кок'юнкц}ею атомiв наступного виду

<назва-в1да.-I>.сназва-атриб.-I>=<назва-в!дн.-2>.<назва-атриС.-2>,

де <назва-в!дн.-1>,' <назва-в1да.-2>. нелекать списку втдношень речення FROM. 3 допомогою рачения JOIN CONDITION задашься пари атрибутов, якт з точки зору уя!версальност1 релящйно! схеми е однаковими. У випадку оперування чггкими водаошеянями в mobi SQL умови з'еднання включались в речення WHERE. Легко перев1рити, що включеня <умови-з'гднанвя> в речення ШШЕ шляхом кон'юнкцп 1з нечеткою умовою не водображае адекватно процеси обробки неповно! 1Нформац!!. Тут проел1дковувться аналогтя з неч!Ткою реляцхйнпю

та

геброю, де оператори природного з'еднання та екв!- з'еднання на жуть бути виражен! в загальному виладку через оператор ■з' еднання.

1. <не?1тка-умова> будуеться аналог!чно до з&мбЯво!' бул1воько! 'сви мови SQL'3 единою вХдацншотю, шо при побудов! ночггко!' юви можэмо використовувати неч1тк1 onepauii нор!вняння, кожна з сих характеризуемся фугпацею належностг на втдоовгдних Пверсумг'х.

i. Речения LSVEL нгдловгда? оператору ТХШ. нечетко! реляцхйно1' ¿■ебри. Умова р!вня записуеться у виг ляд! ГОс або К0с, де Э-5яка з одеращЯ порхвняння =, >, <, <, ^ ! cet0.1l.

Шдсумовуючи вищесказзне, наведемо для загшту заданого блоком ELECT, екв1валентний вираэ нечПяо! реляшйно! алгебри

1^®'<умова_р i БНЯ>К®чс1мсок-атрибу т!в-2>° <неч t тка-умова > с список-атрибут iB~I >rt <умони_£чилання> — ^юви-з^еднання/"'

е посл!довн!сть г^,..., г. задав список вгдношэнь речения PROM.

Розглянуто питания обчислення запитtв , як! вклтыоть агрегуючт ункцт! (COUNT, SW, MOT, MAX, AV5); операцГГ порхвнянн множин =, IN, CONTAINS): речения GROUP BY, HAVING; ключов! олова ANY, • Lb; предикат EXIST; оператори UNION, INTRSSECT, MINUS.

S п'ятоыу роздал! описана реалхзащя досл1дного прототипу СКБД _ <пя :^9н!пулювання неповною !нформэц!ею -нэ базi промислово! СКБД ВАКЕ етмейства. Приводиться оста моей представления даних, ¡изначенкя лгнгвгстичних зм!нтсс, нечетких модификаторов, 'озлянуто питания представления нечхткого з!дношеннл через систему гаичайюге вхдношень базово! СКБД, ix обробка. В якост! мови laroiTiB вибрана мова FSQL, для яко!' реал!зовзно обчислення зашгг!в оданих основними синтаксичними конструкц!ями мовй шляхом ix 'рансформац!! в екв!валентний вираз реляШйно i алгебри.

ФукцЮнзльна схема дсслтдного протипу СКБД представлена на жс.1. '

Рис.1.

У висновку зформульован! основа! результат .¡зиертацхйно! робота.

В додвтку наведанI документа, як! пхдтв^рдаують впровадаэння результат 1в дасертавдйша. дослтдаень.

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

В дисертэц!! проведен! доаНдкення, пов'язаШ з побудовою розпмрено! ралятЦйно! моделх для представления та сбробки непсвно'! шформэцх! -в базах дяних. Проведан! робота охошшють широкий спектр дослгдкень, починаючи з теоретичного обгрунтування деяких прикладних пнтань теорИ мокливоет! ! закхнчуючи розробкою мови манхпулвдання кеч!ткими данями КО! та основними 1деями реалхзаци • дослхдного прототипу СКВД. .

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

покоявип основа! сп1зв!Еао«еЕня м!х нориалысдш' форкеки, доведан! 32 гтасттосП.

2. Розроблент метода 0Ц1Нкв нечетких заггатХв на яз'лткгас базах дааих в рашсах теори" можливостей.

3. Введен! сбмеявная на нечхтк! данг (ре- залешост!), наведена система аксхом хх виводу, а такс» доведена IX повнота.

4. Побудована нечгаа реляшйна алгебра на зхднозакнях, представлзних в 2ННЭ. ДослХдаено влэстивост1 нечетких релящйЕах оператор! в та патанюг викорисгання галеиносгей даних. для зменшеиня невизкачеяностх результату реляц!йнох ргюрзцИ.

5. Побудована мсвэ машлулювання неч1ткимн данимя УВОЬ, дослгдаено зв'язок оснсвних конструкций мови !з виразвми неч!тко! реляцтйно! алгебри.

6. Розрсблвн! принщгаи, метода тз алгоритма побудови прсгрэмного комплексу дослхдяого прототипу СН5Д для мая!пулювання Н9ч1ткими даними.

7. Зроблений пор1шяльний аналХз ¿шш методов до представлення нечхтко'Х ¿нформац1)[ в реляцхйних базах давих .

ОсновыI результата дисертацп викладевХ в роботах:

1. Кицмей Т.В. Представления неч!ткох Изфромац!!' з базах даких релящйного типу. - Депон.в ДИТБ Украхни 27.04.93, А 848-Ук93,15 с.

2. Кицмей Т.В. Представление нечеткой инфо;)мацю1 в базах данных реляционного типа.- Тез.док. на семинаре "Ноше информационные технологии и инструментально- технологические' средства поддержки принятия решений" псс. Кацивели, 21- 26 дэк.Киев, №-т кибернетики им. В. М. Глумова АН Украины, 1992.

3. Ккцмей Т.В. Обмежешш па нечгтк! дан:.- В!сник Льа!вського . полIтехнIчного Iпетитуту, збхрник "Кокп'втеряа технгкз", 5 с' (в

друцх)•

4. Кицмей Т.В. Нечхтка 1нформац!л з раляцхйних Сазах даних.-Депов. в ДНТБ УкраХни 13.03.93, » 1738-УК93, 42 с.

5. Кицкай Т.В. Нечгтка реляшйна алгебра.- Депон. в ДНТБ Украхни 13.08.95, » 173Э-УК93, 37 С.

& Кицмей Т.В. Нечхтка мо а манхпулювання даними РБОЬ.- Девон. : ДНТБ Укрэ1ни 13.08.93, & 1741-Ук93, 18 с.

7. Квдмей Т.В. Дослхдний прототип СКБД на основ! нечгтко релядгйк): иодел!.- Дэпон. в ДНТБ Украти 13.08.93, й 174С-Ук93 14 с. ■ • •

8. Кицмей Т.В. Представление нечеткой информации в бг-.за: . даккнх реляционного тшхз.~ Тез.док. на II Международном семинар«

"Теоретические и прикладные проблемы моделирования предметнш областей в системах баз данных и знаний" /Под. ред. Игнатенко Б.К. - Киев: Совсер1, Ый, 6 с.

9. Квдыей Т.В. Обметания на неч1ткх дзн1. Тези доповШ на 1-Е м!кпародн1й конференц!! з !нформацхйних технологи I систем, жов. 1993 р.,- м. Льв1в, 4 с.

Пхдп. до даует f.it.93 . Формат 60х641/16 Памр друк. Офг.мвук, Уковн.друк.арк. /еГ Умовн.фаро.-вгдо. <з Уыавн.видав,ара. л.?/ Тираа feg прим. Sa», ¿ьэ . Ьезплатно

ДУЛИ 290646 Ьвхв-Р, Ст.Бандевп. 12

Дхльниця оперативного друку ДУЛП Льбхв, иуд, Городоць&а, 286