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

Науково-виробниче об’вдгіаіаія "МІсіксистеїютехніка"

5 ІіОГі ізао

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

МДЛЮТА ТЕТЯНА ОЛЕКСІЇВНА

КЕТОДИ І ЗАСОБИ РОБОТИ З НЕЛОВКИМИ І НЕЧІТКИМИ

значеннями в сжтаих ічаїяцвапіх баз ' т<

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

Автореферат дисертації на зйобушя вченого спупеня канСигаяа технічних наук

Київ 1993

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

на засіданні Спеціалізованої Ради Д 166.01.01 в науково-виробничому об'єднанні."Міськсистемотехніка" за адресою:

252004, м. Київ, вул. Червоноармійська 23-6.

З дисертацією могна ознайомитись в бібліотеці НВО "Міськсистемотехніка".

Офіційні опоненти: д.т.н.,проф. Б.В. Ігнатенко

к.т.н., с.н.с. Н.Д. Ващенко

Провідна організація - Інститут програмних систем науково-технічного комплексу "Інститут кібернетики ім. В.М. Глушкова" АН України (м.Київ)

Захист відбудеться

Вчений секретар Спеціалізованої Ради Д 166.01.01 .

Гіадук В.П.

АНОТАЦІЯ

. Дисертація присвячена вирішенню однієї з проблем підвищення семантичної виразності реляційних баз даних - предг :р'енню і обробці в реляційних базах даних неповної, неточної або ‘мдсутньої інформації! Ця проблема має. важливе значення в- зв'язку з поширенням систем штучного інтелекту і експертних . систем, інтелектуалізацією систем обробки даних і інформаційних систем, цо в • свою чергу приводить до зближення і спільного використання "інтелектуальних" систем і систем обробки даних, зокрема, систем управління базами даних. Серед можливих шляхів зближення систем штучного інтелекту і систем управління базами даних - розширення можливостей традиційних баз даних засобами представлення і обробки знань. Оскільки системи штучного інтелекту,- експертні системи' вимагають можливостей по обробці неточної і нечіткої інформації, то ці можливості повинні бути реалізовані і в.системах управління базами даних. В дисертаційній роботі проаналізовані існуючі підходи до розширення реляційних моделей бЕЗ даних можливостями обробки неповної і нечіткої інформації; В результаті аналізу дається відповідь на запитання: " В чому х полягав, розширення реляційної моделі баз даних для' обробки, неповної та'неточної інформації? ". Розширення реляційної моделі починається не на рівні реляційної алгебра, а полягає у розширенні визначення домена, введенні в нього нечітких значень. В результаті введення в домен нечітких значень виникає необхідність розширення поняття відношення і, відповідно, пезного розширення реляційної алгебри. При практичному використанні розширення реляційної моделі полягає „ у введенні в СУБД нового типу данях, який вимагав застосування до себе нових операцій.

На захист виносяться наступні результати досліджень;

І. Розширення реляційної моделі баз даних для обробки в них неповної інформації. .

2..- Методика розширення традиційних реляційних систем управління базами даних введенням в' них нового типу даних для

представлення і обробки неповної та неточної інформації.

" 3. Програмно- алгоритмічна реалізація методики на програмних макетах та моделях в середовщі СУБД реляційного тину, а також її практична апробація та впровадження в інформаційних системах» побудованих на оснгзі реляційних баз даних.

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

Розповсюдження систем штучного інтелекту і експертних систем вимагає їх використання у сукупності з системами управління базами даних для збереження в останніх, даних і знань. СУБД повинні мати можливості для відображення знань і, зокрема, неповних 1 неточних даних.

Об'єкт дослідження. Поширеною моделлю баз даних є реляційнз модель. Поряд з багатьма перевагами над іншими моделями вона має такий недолік, як обмежена семантична1 виразність. Зокрема, в реляційних базах даних ускладнена обробка неповних, неточних або не існуючих даних. Об'єктом дослідження е реляційна модель даних і її розширення для представлення неповністю визначених даних.

Предмет дослідження. Аналіз можливостей обробки в реляційних базах даних неповних даних проводиться дослідниками з кінця 70-х років. Більшість запропонованих і проаналізованих підходів давала некоректні розширення реляційної моделі, В роботах не було чітко визначено, в чому саме полягає розширення, і яким чином воно має здійснюватись. ■ В результаті проведених дисертантом Досліджень та зроблених узагальнень можна ■ стверджувати,* що розширення можливостей реляційної моделі баз даних для обробки неповної інформації полягає у розширенні визначення домена введенням в нього неповних даних. При розширенні можливостей традиційних СУБД реляційного типу це полягає у введенні, в СУБД нового типу, даних* який дозволяє відображати неповноту інформації» разом з ошраціями над цим типом даних. Введення неповноти - даних на рівні домена вимагає відповідного розширення реляційної алгебри,. Розширення реляційно алгебри і- методика введення нового-тину даних в СУБД реляційного типу для обробки неповної/інформації 1 е предметом дослідження.

Актуальність дроблена та історія проблеми. Перші пропозиції щодо розширення реляційної моделі' баз даних для обробки неповних даних були сформульовані Коддом в кінці 70-х років, який ввів в базу невідоме значення /null value/. Модель Кодда не була коректною, В подальших дослідженнях Гранта, Ліпського, Біскапа, Ззнюло пропонувались різні шляхи по розширенню реляційної моделі для обробки невідомих' значень, але практично есі підходи даваль некоректне розширення моделі. Тобто, в рамках введеної семантики невизначеного значення,/обласі визначення/ результат операцій був різним в залежності від порядку обробки неповних відношень: інтерпретація неповного відношення відповідно до його семантики, і застосування реляційних операцій до повних баз даних, і навпаки, застосування розширених реляційних операцій до неповного відношення і інтерпретація результату.В подальшому з'явились дослідження по введенню в реляційну модель неповних, неточних І нечітких даних Буклеса, Петрі, Вонга, Прада, Земанковоі. Пропонувались різні підходи до моделювання таких, даних: теорія ймовірностей, багатозначна' логіка, різні емпіричні оцінки. Неповнота даних вводилась в реляційну модель на різних рівнях- на рівні запиту до традиційної реляційної бази даних, на рівні кортежів, коли існує невизначеність щодо цілого кортежу, належить' він базі, чи ні. Проведений дисертантом аналіз показав, що найбільші виразні можливості забезпечує введення невизначеності на рівні -значень атрибутів бази. Серед засобів моделювання невизначеностей дисертант виділяє емпіричні оцінки, які не вимагають великої попередньої роботи по їх визначенню, і які найбільше ■ відповідають застосуванню баз даних ® ''інтелектуалізованих" інформаційних системах. Серед емпіричних оцінок найбільш розробленою & теорія можливостей 1 нечітких множин. В останні роки з'явились роботи по реалізації розширень існуючих систем обробки даних -можливостями обробки неповної інформації і по створенню окремих систем, які включають такі можливості. З'явились роботи, присвячені вирішенню конкретних прикладних задач, в яких реалізовано потрібний для вирішення задачі, обмежений набір можливостей по обробці►неповних даних. В

т ' - -

даний час актуальною є, розробка загальної методики введення нового типу нечітких данйх неіснуючі СУБД реляційного типу, що дозволяло би реалізувати більшість можливих випадків виникнення неповноти або нечіткості даних. ( .

Методи дослідження. Методом дослідження е об'ектно-орієнтований підхід, який використовується при формуванні нового типу даних і введенні ійого в ісдачі СУБД реляційного типу. Для моделювання неповноти -і-неточності даних використовується теорія можливостей і нечітких імножин, яка є добре розробленою і дозволяв моделювати переважну Оільшість. можливих ситуацій з неповнотою Інформації.

Ціль . дисертації. , Дослідження, виконані в дисертації, орієнтовані на розширення мокливостей існуючих СУБД реляційного типу засобами обробки і нечіткої і неповної Інформації. Ціль дасертації-аналіз та дослідження можливих варіантів розширення реляційноі моделі баз даних для представления і обробки/неповної та нечіткої інформації в. базах даних реляційного тішу. Розробка методики такого розширення і її реалізація в вигляді програмних макетів та програмно- (алгоритмічних моделей, які дозволяють відпрацювати запропоновані дисертантом підходи на практиці. В дисертації автором викладені, обгрунтовані і винесені на захист наступні основні результати:

Теоретичні: •

аналіз та дослідження розширень реляційної моделі бази даних для обробки неповної та неточної Інформації та введення в СУБД реляційного класу нового типу даних, який дозволяє представляти і обробляти недовизначені дані.

Прикладні: .

розробка методики введення нового типу даних для представлення неповної інформації в існуючі СУБД реляційного типу

і реалізація методики на програмних /Макетах та програмно-алгоритмічних моделях в середовищі реляційної СУБД .

Наукова новизна. В дослідженнях, які проводились по розширенню реляційної моделі баз даних для обробки неповшх і неточних даних, не був визначений зміст "розширення", що приводе....•

б

до некоректного розширення алгебри. Наукова новизна даної дисертаційної роботи полягає в аналізі змісту поняття "розширення" реляційної моделі для обробки неповних даних, розширенні реляційної моделі, яке починається на рівні доменів і розповсюджується на рівень реляційної алгебри, можливістю обробки неповних даних в рамках запропонованої моделі. Це твердження виступає методологічною базою для розробки "розширеної" Сі'ЕД реляційного типу. Вперше запропонована методика розширення можливостей існуючої СУБД реляційного типу для обробки неповної I неточної інформації. .

Практична цінність. Дисертація була виконана в руслі досліджень, які проводились дисертантом’в період з 1987 по 1992 p.p. в Львівському політехнічному Інституті в ЦДЛ- 45 /Обчислювальний центр / і на кафедрі "Автоматизовані система управління" по замовленню ДКНТ, Міністерства освіти -України, Фізико- механічного інституту АН України, виробничих об'єднань "Ювелірпром", ’’Світоч", Дрогобицького автокранового заводу.

Результати дисертації.впроваджені на Львівському ювелірному заводі, Одеському ювелірному заводі, Львівському ВО "Світоч", Дрогобицькому автокрановому заводі, Львівському політехнічному інституті в процесі виконання цільових замовлень цих організацій в рамках господарських договорів та в учбовому процесі під час викладання курсу "Бази та банки даних і знань".

Рекомендації по використанню. Запропонована методика може бути викошстана для розширення функціональних можливостей існуючих СУБД реляційного типу засобами обробки нечіткої і неповної інформації.

Апробація. Основні результати досліджень доповідались автором на міжнародних, всесоюзних та республіканських конференціях і семінарах:

-міжнародній конференці ї• з математичних основ баз даних /Берлін, 1989/; ■ .

- міжнародній науковій конференції з інтелектуальних систем управління /Варна, 1989/;

- всесоюзній конференції "Системи баз даних і знань"

/Калінін, 1989/; .

- міжнародні^ конференції "Системи б?з даних і знань" /Львів,

І991/;

- республіканській конференції "Проблемно- , орієнтовані діалогові системи" /Батумі, 1988/;

- 'спеціальних ..семінарах в Львівському політехнічному

інституті, НВО "Міськсистемотехніка", інституті кібернетики їм. В.М. Глушкова АН України. ’ . •

■ Матеріали і результати дисертації опубліковані .на Україні і за кордоном. Загальна кількість публікацій по темі дисертації- 10.

Структура дисертації. Дисертація складається з вступу, чотирьох глав, заключення і додатків. Об'єм дисертації*- стор., тексту- стор., ілюстрацій- . Список використаної дисертантом літератури складає 60 першоджерел. В заклвченні сформульовані основні результати, висновки і погляди автора на розвиток досліджень в області моделей база даних і знань реляційного типу. В додатку наводяться програмні макети та програмно-алгоритмічні моделі' з' реалізації розширення функціональних можливостей СУБД реляційного типу для обробки неповної інформації.

ЗМІСТ РОБОТИ

У вступі проаналізовані підходи до рішення проблема представлення неповної та неточної інформації в реляціііннх\оазах даних.. їх можна умовно розділити на дві групи: ті, що розглядають випадки повної відсутності інформації про значення атрибута ,,т.з. невідомі значення /сюди ж можна віднести інтервали можливих значень/, і підходи, в яких розглядаються способи представлення і обробки частково невизначаниі значень. Цей поділ відображає також хронологічний розвиток досліджень.

Введемо основні позначення і визначення, які використовуються в дисертації. Характеристики, що описують об'єкти реального світу, називаються атрибутами /позначаються А, В,.../, їх '.множина позначається и. Кожний атрибут приймає значення з деякої множини,• яка називається доменом атрибута /позначається В/, .функція іШ: А1->Б1 задає відповідність між множиною атрибутів і доменами' Під

атрибутом розуміється пара <А^, -В^>. Відношенням називається властивість, яка виділяє певну підмножину з декартового добутку доменів: г s Кортежем називається впорядкована

послідовність <d1, dg в як;й d-^ £ D^. Кожному відношенню

можна поставити у відповідність предикат, який приймає значення "істина'-, коли виконується відношення, і приймає значення "хиба" в інших випадках. Множину предикатів на відношеннях позначимо £. Тоді визначаємо реляційну модель як четвірку < U, D, DOM, Е >, а реляційну базу даних як п'ятірку < и, D, DOM, 2, А >, де Q-множина операцій на множині атрибутів і доменів.

Що означає "неповнота" .і "нечіткгсть" інформації в базах даних? Реляційна база даних- це представлення певної реальної ігоедметноі області /ПО/. Вважаєм, що ПО описується п'ятіркою < U®, іР, DOM0, 2°, сР >» Існує наша система уявлень про П0-представлення ПО /ППО/, яка описується п'ятіркою < U1, D1, DOM1,

2 , П1>, отриманою з ПО відображенням (р1. В результаті деякого відображення ф2 будується реляційна база даних < U2, D2, DOM2, 21-, Я? >, яка використовується, як представлення ПО. Реляційна база даних фактично є результатом суперпозиції двох відображень <р1 і фг. У випадках, коли можна вважати, що ІШи співпадає з ПО, ми отримуємо реляційну базу даних, яку називаєм "традиційною". Але коли ППО неповністю відповідає ПО, ми отримуємо реляційну базу даних, яка, в свою чергу, відображає це неповне знання про ПО. Ь дисертаційній роботі розглядається випадок, коли нема повних знань про - систему відношень 2, тобто- нема повної інформації про властивість ПО, яка формує відношення. Неповнота інформації може зустрічатись на різних рівнях: невідомо, чи властивість притаманна ПО- невизначеність на рівні відношення, відомо, що властивість притаманна ПО, але невідомо, чи притаманна даному об'єкту-невизначеність на рівні кортежів, відомо, що властивість притаманна ПО і об'єкту, але невідомо, як вона на об’єкті проявляється- невизначеність на рівні значень атрибутів. В дисертаційній роботі розглянуто останні два випадки невизначеності.

Тобто, одна з причин виникнення неповноти або неточності

інформації в Сазі даних /як і в довільному, зв'язаному чи не зв'язаному з комп'ютерними технологіями відображенню ПО/- неточні, суб'єктивні представлення про реальність.

Друга причина виникнення неповноти або неточності інформацп-використання розмитих категорій, наприклад, МОЛОДИЙ, ВЕЛИКИП. Використання таких категорій може бути наслідком першої причини, а може бути викликано необхідністю спрощення моделі для забезпечення її прозорості. Тобто, навіть якщо є повна інформація про предметну область, відображення ф1 сформує представлення предметної області

з неповнотою інформації внаслідок абстрагування і узагальнення.

Ці дві причини /які є взаємозв'язані/ приводять до необхідності використовувати дані, які не можуть бути представлені, як точні, чітко визначені значення.

В першому розділі розглянуті'підходи до обробки невідомих значень.Вперше розширення реляційної алгебри на відношення з невідомими значеннями .було запропоновано Коддом. Для обробки < невідомих значень він використовував тризначну логіку з третім значенням істиності "невідомо" /позначається w/. Підхід грунтується на принципі заміни невизначеностей, який визначає умови, при яких логічний вираз приймає значення ш. Запит до бази має два результати: TRUE- результат./кортежі, на яких умова запиту дає значення "істина", і MAYBE- результат /кортежі, на яких умова запиту дає значення ш/.

В публікаціях по реляційних б^зах даних наводиться ряд прикладів некоректності запропонованого підходу /деякі теоретико-мно^инні операції, над відношеннями, тавтологія в умові запиту і т.п./ Це викликано тим, що підхід не є. достатньо обгрунтованим: в ньому відсутнє формальне визначення семантики невідомого значення, є протиріччя в логічних основах підходу .

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

. Ірант вводить поняття області визначення невідомого значення, яка задає множину правильних підстановок невідомого значення. Вводиться трете значення істиності- ''невідомо". Особливість підходу Гранта заключається в тому, що він залишається в рамках двозначної логіки. Для цього кожному предикату Р ставиться у відповідність два предиката- Рт і Рм /TRUE- і MAYBE- предикати відповідно/, де Рт приймає значення "істина" тоді і тільки тоді, коли Р є істиним для всіх вірних підстановок для невизначеностей в Р, а Рм є істиним тоді і тільки тоді, коли Р є істиним хоча б для одвіеї вірної підстановки для невизначеностей в Р. На підставі цих загальних положень вираховуються Рт і Рм для різних предикатів на значеннях атрибутів, атрибутах, таблицях, а також даються визначення розширених реляційних операцій. Отримана модедь досліджується на коректність. Виявилось, що результати, які отримуються в результаті застосування введених операцій, в загальному випадку не можуть бути отримані при знаходжені спочатку всіх можливих розширень тих таблиць, що обробляються, а потім застосуванням звичайних операторів. Розширена модель Гранта також не е коректною.

Велике дослідження можливостей коректного розширення реляційної моделі на бази даних з невідомими значеннями проведене Ліпським та Імелінським. Як критерій коректності розширеної моделі було запропоновано поняття репрезентативної системи. Репрезентативною системою називається трійка < Т, Rep, 0 >, де Т-мнокина неповних відношень, Rep- відображення, яке ставить у відповідність кожному неповному відношенню деяку множину відношень, П- множина реляційних операторів, які використовуються. Для Q- виразів 1 слід було б чекати, щоб виконувалось ;Rep(f(T)) = X(Rep(T)). Ця вимога виявилась дуже сильною і автори вводять більш іуіабу Q- еквивалентність таким чином, щоб Rep(I(T)) апроксимувало ї(Йер(Т)). Тоді .приведена • вище трійка буде репрезентативною системо»,.якщо для любого неповного відношення R буде виконуватись Rep(f(R)) =Ql(Hep(T)). Показано, що для неповних відношень Кодда репрезентативна .система може включати тільки дві операції-проекЦію 1 об'вдаання. Однією з причин того, що на неповних

відношеннях Кодда не може коректно виконуватись з'єднання, е те, що неможливо відобразити нерівність двох невідомих значень. Показано, що введення в відношення додаткової інформації про нерівність невідомих значень між собою /вибір невідомих значень-- з

• деякої нескінченної множини невідомих значень/ може суттєво

■розширити набір коректно виконуваних розширених алгебраїчних операцій. В репрезентативну' систему для _ таких відношень включаються операції проекції, вибору з додатковою умовою,-об'єднання і з'єднання. '

Біскап також використовує в своїх роботах поняття репрезентативної системи, але вводить ЙОГО ВІДМІННИМ ВІД ЛіПСЬКОГО\ способом. Фактично, підхід Бискапа можна вважати обгрунтуванням підходу Кодда і. MAYBE- результатів.' В цьому випадку допускається можливість і достовірність цілих кортежів, для чого вводиться додатковий атрибут STATUS,чяккй може приймати два значення raid /ш- кортеж можливо належить результату, й- кортеж достовірно належить результату/. В рамках розширення реляційної алгебри Біскапа всі оіфвмі реляційш операції виконуються коректно, але підхід не розповсюджується на реляційні вирази, як у Ліпського.

В роботах Занюло було показано, що ряд логічних і теоретико-множинних проблем може бути вирішений за допомогою більш примітивної інтерпретації невідомого значення. Невідоме значення трактується, як повна відсутність інформації, що не дозволяє зробити висновок чи є це значення '’невідомим", чи "неіснуючим". Розширення реляційної алгебри по Заніоло не вимагає суттєвого ускладнення механізмів обробки запитів. Однак, на думку дисертанта, така інтерпретація є досить штучною і не дозволяє побачити ряд проблем. Крім того, в роботі Келлера показано, що Заніоло не вдалось вирішити теоретико-множинні проблеми розширеної моделі, і, крім того, отримано більш загальний результат, який полягає в слідуючому: не можна побудувати розширення реляційної

* алгебри, яке грунтується на ідеї поповнення невідомого значення, для якого виконувались би всі теоретико- множинні властивості.

В роботі Вассіліу розглядається моделювання неповноти інформації за допомогою денотаційної семантики, причому

враховується також інтерпретація відсутнього значення, як "неіснуючого". Множина значень і'стиності розширюється слідуючим чином: Т° = ї о { bot, top >, де Т = { "істина", "хиба” ). ‘\„>мент bot апроксимуе будь- який елемент Т і його інтерпретують, як "значення невідоме", елемент top апроксимуеться будь- яким елементом з І і інтерпретується, як "значення не існує". Підхід відрізняється від вйкористання чотиризначної логіки.. Коректно обробляються запити, в яких умова є тавтологією.

Проаналізовані підходи до обробки невідомих значень в реляційних базах даних відрізняються визначенням семантики невідомого значення, але всі базуються на ідеї поповнення невідомого значення з області 'його визначення. Запропоновані розширення реляційних операцій, які не є коректними. З точки зору дисертанта недоліки запропонованих моделей витікають з того, що при ■ виконанні реляційних операцій до ■ невідомих, значень застосовуються ті ж оператори, що і до значень бази, які визначаються традиційними типами даних /числа, символи і т.п./. Невідомі значення треба, розглядати, як дані іншого типу, і застосовувати до них відповідні, визначені для них оператори.

В другому розділі проаналізовані підходи по представленню в базах даних неповної або частково визначеної інформації. Для моделювання частково визначеної інформації використовуються теорія ймовірностей, нечіткі множини, багатозначні логіки.

Серед підходів, які використовують ймовірнісне представлення неповноти даних, особливе місце займає підхід Вонга, який-розглядає невизначеність ніби "над" базою даних. В базу заносяться тільки точні дані. Крім того, існують апріорні ймовірнісні розподіли, які зв'язують атрибути з іншими характеристиками предметної області /які теж можуть зберігатись в базі/. На підставі відомих апріорних розподілів ймовірностей відбувається попередня статистична обробка запитів, потім перетворений запит адресується до основної бази даних. Підхід можна використовувати в тих випадках, ' коли неповні . дані моделюються за допомогою ймовірнісних розподілів і при проектуванні бази даних можна розділити точні і ймовірнісні дані.- ■

В ряді робіт ймовірнісні розподіли вводяться на рівень кортежів- в базу додається атрибут, значення якого, визначають ймовірність того, що відповідний кортеж належить до відношений.

Використання ймовірнісних методів ускладнюється необхідністю обробляти' великі об'єми даних при визначенні розподілів. Крім того, теорія ймовірностей є дуже нормативною для' того, щоб використовуватись для моделювання невизначеностей деякої природа /наприклад, лінгвістичних невизначеностей/. Більше розповсюдження отримали методи моделювання неповної інформації за допомогою емпіричних оцінок, в першу чергу- за допомогою нечіткостей. існують підходи, які зберігають однорідність бази даних. Найпростішим способом введення нечіткостей в базу даних е використання їх на рівні кортежів аналогічно ймовірнісним розподілам. Це не вимагає суттєвого ускладнення механізмів обробки даних. Такий підхід можна використовувати і у випадку, коли невизначеність’ зустрічається тільки в запитах при використанні нечітких понять аоо нечітких відношень /наприклад, вибрати з бази всіх молодих осіб, або вибрати всіх осіб з близькими інтересами/. Тоді дані зберігаються в звичайному вигляді, а окремі відношення визначають нечіткі поняття /наприклад, мОЛСдпЛ/ або котріЩЕ близькості між значеннями атрибута /наприклад, ІНТЕРЕСИ/. В ряді робіт детально розроблено використання нечіткого відношення "близькості" або "подібності" замість відношення рівності.

Найбільші можливості для представлення неповноти даних мають неоднорідні бази даних, коли невизначеність вводиться на рівень значень у відношеннях. Такий підхід дає можливість відображати в базах наступні випадки неповноти даних:

- значення знаходиться в інтервалі або є одним з дискретної множини значень, в тому числі сюди відноситься невідоме значення;

- значення не існує;

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

Детально розроблено використання для представлення неповноти даних теорії можливостей і апарата нечітких множин Заде. Значення

атрибутів мають двоїсту оцінку- можливість і необхідність виникнення саме цього значення для даного кортех;а. Результат обробки кожного запиту буде включати два відношення: кортежі, які "можливо" належать результату, і кортежі, які "необхідно" належать результату.В ряді робіт для моделювання неповноти використовується багатозначна логіка.

Класифікацію проаналізованих підходів можна представити схематично:

НЕПОВНІ ДАНІ

ЗаЙЙГ

КОРТЕЖ

спосіб моделювання

ймовірність

рівень неповноти

ЗНАЧЕННЯ АТРИБУТА спосіб моделювання

ЕМПІРИЧНІ

ОЦІНКИ

ЙМОВІРНІСТЬ

ЕМПІРИЧНІ

ОЦІНКИ БАГАТОЗНАЧНІ ЛОГІКИ

Виникнення неповноти інформації на рівні запиту або кортежу не вимагає суттєвого ускладнення обробки запиту до бази, але не. може охопити всі випадки неповноти ‘даних. Найбільші виразні можливості забезпечу? введення неповноти інформації на рівень значень атрибутів бази. Серед проаналізованих підходів до моделювання неповноти інформації дисертант виділяє емпіричні оцінки.

В третьому розділі дається обгрунтування вибору інструментарію для моделювання неповноти і .нечіткості даних і формулюється суть поняття "розширення" реляційної моделі для частково визначених даних.На думку дисертаната одним з найбільш цікавих з точки зору практичного використання може бути підхід, який спирається на апарат теорії можливостей . Він дозволяє ■ змоделювати більшість випадків неповноти даних, включаючи неіснуючі значення, і нечіткі запити до бази. Серед робіт, в яких описується реалізація використання в реляційних базах даних неповних даних і обробки

нечітких запитів, переважають підходи, які 'спираються на апарат теорії можливостей або на його аналоги. Такого підходу вимагали і розробки, викликані реальними задачами і. потребами. З нашої точки зору саме такий підхід, може бути корисним при використанні реляційних баз даних в "інтелектуалізованих" інформаційних системах або при стикуванні їх з цими системами, оскільки з його допомогою.добре відображаються саме емпіричні, експертні оцінки і судження, і він.природньо інтегрується з методами представлення знань в "інтелектуалізованих" інформаційних системах. Крім того, в теорії можливостей люба подія отримує двоїсту оцінку: необхідність цієї події і її можливість; що дозволяє .більш адекватно і повно оцінювати нечіткі дані. Саме ця особливість теорії можливостей не використовувалась в проаналізованих нами публікаціях по розширенню реляційних моделей баз даних.

• Мірою мозкливості П на множині 0 буде функція P(U—> to, 13. де Р(U) - множина підмножин W, така, що П(о)=0, II(U)=1, v А,В е Р(U), П(А В) = тах(П(А), П(В)). Як наслідок v А P(W), тах(П(А), П(5))=1. . ' • -

■ Коли 'заданий розподіл можливостей rc:W—Я0,1], міра можливості визначається наступним чином: v к = F(W>, П(А> = sut>

3t(W). . .

На основі можливості будується міра необхідності v A«=P(W), N(A)=1-Iit5). ' ■ . ' .

Для N виконується v AeP(W), mln (N.(A), КШ)=0, v A-sP(W),

N(A) = Inf. [i-3t(w)i. —

weW ■

Визначення можливості та. необхідності можуть бути розширені

на використання нечітких множин.

Інформація про значення атрибута А буде визначатись розподілами, можливостей я^д) Для кортежа t на D(А) и Се>, де е -додатковий елемент, який відповідає випадку, коли для даного об'єкта значення не існує, тобто я^д) : И(А) и (є)—>10,1 і.

• Результат операцій на розширеній базі даних буде складатися з кортежів, обов'язково задовільняючих результату операції та можливо задовільняючих результату /відповідає TRUE і

ііаїйїі-результату/, де їх ступінь належності буде відповідати мірі необхідності та можливості відповідно. Визначені формули для оцінювання атомарних і складних нечітких умов при обробці запитів.

Для демонстрації приведених положень в якості прикладу використаємо відношення ОСОБИ: .

ОСОБИ ІМ'Я ВІК РІСТ КОЛІР ВОЛОССЯ

ІВАНЧУК 25 180 0.9/блондин + І/русявий

ПЕТРЕНКО [20-251 високий - . .

. СИДІР молодий 190 русявий

Для охоплення всіх можливих ситуацій виникнення нечіткостей при роботі з РБД треба забезпечити можливість представлення і обробки:'

- нечітких і неповних даних /невідомі значення, інтервали значень, нечіткі підмножини, неіснуючі значення/;

- нечітких операторів /наприклад, оператори подібності,

близькості/; ■

- лінгвістичних змінних, тобто ідентифікаторів нечітких підмножин, на доменах атрибутів /наприклад, МОЛОДИЙ/;

* - .модифікаторів нечітких операторів і лінгвістичних змінних /наприклад, ДУЗЕ МОЛОДКИ, НАБАГАТО СТАНШЯ/;

- матриць близькості на значеннях . домена /наприклад,

близькість кольорів волосся, яка використовувалась би в запитах з умовою тішу ПОДІБНИЙ ДО блондина/.

. Крім того, бажано було б дати можливість користувачу

формувати власні- нечіткі поняття, нечіткі оператори і нечіткі

мо,цифікатори. Ні в одній з розглянутих наїли робіт ці можливості не були розроблені повністю. ■ ' •

, В дисертаційній роботі запропонована методика розширення традиційної реляційноі моделі даних для представлення' і обробки неповних даних і нечітких запитів, яка спираєтеся на апарат теорії можливостей для представлення нечіткостей 1 дозволяв змйделювати всі перераховані вище випадки нечіткостей . і невідомих та неіснуючих значень.

В чому полягає "розширення" традиційної моделі реляційної бази даних при спробі реалізувати роботу з нечіткостями? Можна стверджувати, що основні положення реляційноі алгебри, визначення реляційних операцій достатньо загальні і не накладають обмежень на зміст бази.даних і запити до неї. Традиційно використовувався обмежений набір типів елементів доменів атрибутів бази, обмеженим

■ був набір, операторів, які використовувались при формуванні умов для реляційних операцій. Фактично розширення реляційноі моделі-полягає у розширенні визначення домена, включенні в нього

неповністю визначених -значень. На рівні СУБД це означатиме

введення нового типу даних< який дозволяє задавати в базі даних неповністю визначені дані, і операцій над цим типом Даних. Цей тип даних будем називати нечітким. .

- Введення неточних даних в реляційну базу даних на рівні

значень атрибутів тягне за собою необхідність введення неповноти інформації на рівні кортежів, тобто, необхідність подальшого розширення визначення відношення, і, відповідно, розширення

реляційної алгабри. ,

. Тобто,’ розширення реляційної моделі почалося з розширення визначення домена і розповсюдилось на визначення відношення і, відповідно, на реляційну алгебру над розширеними відношеннями. Крім множини атрибутів, які входять в схему відношення, в розширеному відношенні розглядаються два додаткові атрибута РОБ і Ж), домени яких е - одиничним Інтервалом, і які відповідають можливості та необхідності включення кортежів у відношення: -

' и* = 0 и РОБ и КЕС

. = = .Ш> 11 , .

В розширеному відношенні И виділяємо дві частини:

інформаційну, . яка . визначається схемою відношення, і характеристичну, яка визначається додатковими атрибутами РОБ ї N110. . • • .

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

ч<?їжпачоное"і даних, а використання двоїстої міри невизначеності забезпечуй найбільш адекватну оцінку результатів обробки запитів до бази.

В четвертому розділі описується методика ВЕЄДЄННЯ в реляційну модель бази даних нового типу даних для обробки неповних і неточних даних. ' •

Ми пропонуємо методику формування такого типу даних, який в подальшому іменується НЕЧІТКІСТЬ, засобами СУБД реляційного типу. При включенні в систему нового типу даних пропонується скористатись можливостями об'єктно- орієнтованого підходу, якщо вони передбачені в системі, або змоделювати його засобами інструментальної системи. Введення нового тішу даних в систему включає .наступні етапи.

Реєстрація нового типу даних. Задания нового тішу даних НЕЧІТКІСТЬ полягає в реєстрації його в системі, а також у визначенні набору операторів і Функцій, які можуть застосовуватись до даних нового тішу. Для систем, в яких не передбачено включення нових типів даних , реєстрація може_проводитись штучно. Наприклад, створюється відношення НЕЧІТКІСТЬ: '

АТРИБУТ ДОМЕН ДОВЖИНА ТОЧНІСТЬ

ВІК N 3 0

РІСТ N ' 3 0

КОЛ.ВОЛ. С іо -

В АТРИБУТ заносяться назви атрибутів, домени яких будуть визначатись на новому типі даних, в ДШЕН- базовий домен, на якому будуть визначатись нечіткі дані /Л- числовий, С- символьний/.

Внутрішнє і зовніинв представлення даних нового типу. Зовнішнє представлення даних типу НЕЧІТКІСТЬ є символьним. Треба визначити внутрішнє представлення даних цього, типу, яке б забезпечувало можливість їх обробки.В основу "вибраного підходу покладено функцію розподілу можливостей над доменом В атрибута: я(й), й е б, за допомогою якої моделюються нечіткі поняття і нечіткі оператори. Для практичних застосувань іі зручно представляти функцією трапеціедальної форми, наприклад, нечітке поняття МОЛОДИЛ над доменом атрибуту ВІК буде характеризуватись

наступним розподілом можливостей:

суде

16 18 23 26 •

записуватись четвіркою < 18, 23, 2, 3 >, де перше число відповідає

початку інтервалу, на якому, функція приймає значення І, друге

число- кінцю цього 'інтервалу, трете і четверте- відхилення від

першої і другої точок- відповідно, на яких функція приймає

ненульове значення. Таке • представлення функції розподілу

можливостей є цілком достатнім для більшості застосувань, оскільки

невеликі зміни форми функції /яка представляє, як правило,

суб'єктивну оцінку події або явища і не може вважатись абсолютно

точною/ не впливають .сильно на результат запиту. Невідоме значення

представляється спеціальною функцією розподілу я1 (й) = 1 VI е Б.

Неіснуюче значення представляється функцією Яц((і) = 0 уі е в.

Розроблені програмно- алгоритмічніпроцедури перетворення даних з

внутрішнього • представлення в зовнішнє і навпаки. Для атрибутів,

.для яких базовим е домен скалярів, використовується явне задання

'РОЗПОДІЛУ МОЖЛ"ВОСТЄЙ.

Константи нового типу даних. У випадку визначення на новому типі даних констант, останні теж мають бути зареєстровані в системі. Для нечітких даних константами виступають виділені назви нечітких множин, наприклад, МОЛОДИЙ. Вони заносяться у відношення КОНСТАНТИ, яке має наступну структуру:

КОНСТАНТИ

АТРИБУТ НАЗВА | ТІ Т2 ТЗ Т4

ВІК МОЛОДИЙ | 18 23 2 3

де в колонку' НАЗВА заносяться зафіксовані, назви нечітких множин відповідного атрибуту, а ТІ- Т4 трапецієдальний розподіл можливостей; внутрішнього представлення константи.

Оператори. Для нового типу даних задаються оператори, які можуть застосовуватись до них,зокрема, арифметичні оператори : оператори порівняння /для нечітких даних над базовими числовими

доменами/, оператори близькості /для нечітких даних над скалярними 'базовими доменами/, і інші, які користувач захоче визначити• над нечіткими даними. Арифметичні оператори реалізовані у вигаді стандартних процедур і можуть бути включені в систему. Оператори порівняння і близькості, як і нечіткі константи, моделюються ?а допомогою трапеціедальних розподілів, але розподіли залежать від аргументів операторів. Оператори визначаються за допомогою таблиці■ ОПЕРАТОРИ:

НАЗВА | ТІ Т2 ТЗ Т4 АРГУМ ВИРАЗ

БІЛЬШЕ 1 0 2 0 1.5 2 |аі - а2|

де ОПЕРАТОР- назва оператору, ТІ- Т4- четвірка розподілу, АРГУМ-кількість аргументів оператора, ВИРАЗ- результуючий вираз від аргументів, від якого залежить розподіл.

Модифікатори операторів і нечітких нноген. Інколи виникає необхідність використовувати складні оператори або константи, наприклад, ДУЖЕ молода, НАБАГАТО СТАРШІМ, І т.п. їх мозкна задавати звичайним чином. У випадку, коли одна .частина оператора або константи 'виступає модифікатором другої, тобто змінює функціонально • її розподіл можливостей, то модифікатор для зручності задаємо окремо у відношенні МОДИФІКАТОРИ: .

МОДИФІКАТОРИ НАЗВА ФУНКЦІЯ

ДУЖЕ Г

де НАЗВА визначає назву модифікатора, а ФУНКЦІЯ- назву функції від розподілу оператора або константи, якій передуе модифікатор.

Матриці близькості. Для обробки запитів, в умови який включений атрибут над нечіткім доменом з базовим - скалярним доменом, потрібна інформація про близькість значень домена міа собою. Матриця близькості на значеннях атрибута задається, відношенням МАТРИЦЯ:

МАТРИЦЯ АТРИБУТ ЗНАЧЕННЯ І ЗНАЧЕННЯ 2 БЛИЗЬКІСТЬ.

. КОЛІР ВОЛ. БЛОНДИН ' русявий 0.9

де АТРКЬіі' визначає атрибут на якому задається матриця близькості, ЗНАЧЕННЯ І і ЗНАЧЕНій 2- значення з домену цього атрибуту, між якими визначається близькість.

Обробка даних типу НЕЧІТКІСТЬ. Методика була реалізована на С^БД СІіррег, в якій не передбачено введення нових типів даних. Для обробки запитів до бази були написані процедури, які реалізують основні реляційні операції над нечіткими даними. Для зручності цим операціям були дані окремі назви: ■ іїгіСШСТІОи, УШІОй, ї'ЛЛМ, КЕііЕСї /префікс ¥ відповідає англійському терміну нечіткий- Гиигу/.Ш процедури обробляються препроцесором СІіррег. Для обробки умови, яка може зустрічатись при заданні операції, був написаний синтаксичний аналізатор. Умова ''визначається наступною граматикою: ■ '

<умова> -> <.терм> <з'едаувач> <умова>

. <умова> -> <терм>

<терм> -> <умова> .

<.терм> -> <нечітка множина>

<терм> -> <ім'я атрибуту> <операція> <константа> |

<лм'я атрибуту> <операція.' <ім'я атрибуту>

•.нечітка множинз> -> <модифікатор> <нечітка константа> ■.нечітка множина> -> <нечітка константа> ’ - -

<.з*єднувач> -> НОТ -|АШ | ОН <модифікатор> -> з відношення МОДИФІКАТОРИ <нечітка константа;' -> з відношення КОНСТАНТИ’

<операція> -> <.звичайна операція-4 \ <нечітка операція;-<звичайна операція/ -> -- І < | > | <= І ! ><•'

<нечітка операція> -> з відношення ОПЕРАТОРИ.

Після того, як користувач задасть всі необхідні для обробки нечіткостей дані /для чого створені відповідні засоби/, він може формувати запити до розширеної реляціиної бази даних.

Розроблені програмні макети та програмно- алгоритмічні моделі розширення можливостей реляційної СУВД можливостями оброоки неповної та неточної Інформації і методика формування в С.уьд нового типу даних НЕЧІТКІСТЬ забезпечують гнучкість при настройці на предметну область і на користувача. Розробка сула впроваджена

>;а ряді підприємств з програмній, пакетах та АРМах по планово-економічній та бухгалтерській діяльності, де користувач в інтерактивному режимі має можливість формувати нечіткі запити до бази даних з оперативною, нормативно- довідковою та архівною інформацією по обліку виробничої діяльності підприємства.

ЗАКЛЮЧЕНИЯ .

Аналіз досліджень в області розширення реляційної моделі баз даних для обробки неповної інформації виявляє відсутність чіткого формулювання змісту відповідного "розширення" моделі. Робота націлена на обгрунтування тези, що розширення моделі відбувається на рівні доменів і розповсюджується на рівень реляційної алгебри. При розширенні можливостей СУБД обробкою неповної інформації це приводить до введення нового типу даних в СУБД.

Пропонується методика розширення реляційної моделі існуючих СУБД реляційного типу новім типом даних, який відповідає неповним, неточним, нечітким даним. Результати роботи дозволять використовувати існуючі СУБД реляційного тішу в -системах баз-даних і знань, експертних системах і ішжх "інтелектуалізованих" інформаційних системах. '

Результати дисертації опубліковані в основних роботах:

1. Малюта Т.А., Пасичник В.В. Реализация диалогового проектирования реляционных баз данных с использованием реляционной БД // Материалы респ. конф. "Проблемно- ориентированные диалоговые системы", 25- 28 окт. 1988г. - Батуми, 1988. - с.140-145.

2. Малюта Т.А., Пасичник В.В. Расширение средств реляционной СУБД

для обработки размытых значений данных // Тез. докл. Всасоюз. науч.- практ. школы семинара "Программное обеспечение ЭВМ: индивидуальная технология, интеллектуализация разработки и применение", 5- ю дек. 1388 г. - Ростов- на--Дону, 1988. - с. 7476. ■ . • . ■

3. Брона И.И., Малюта Т.А., Пасичник В.В. Реляционные базы данных с нечеткими значениями // Реляционные. базы данных с' нелеткими значениями. - Новосибирск, 1989. - с. I- 53.-'- (Препр./АН СССР. ВЦ

СО: 846.

4. Stognly A.A.. Kalyuta Т.A., Paslt3Chnlk V.7. Keans Гог

management oJC relation fuzzy data bases- ray to merging of systems of data bases and knowledge bases // Lecture Notes In Computer science. - Berlin: Springer; Tokyo: Verlag, 1989. - К 364. -p.337- 347. " •

5. Калита T.A., Пасичник В.В. Интеллектуализация реляционных баз данных путём введения в них возможностей работы с неполной и неточной информацией // Conference on Intelligent management systems./ Bulgarian academy of science. - Varna, 1989. - p.96-103.

6. Pasltschnlk V.V., MalyutaT.A. Use of abstract data types to manipulate the Incomplete and Imprecise Information In relational databases // 12-th International Seminar on Database Management Systems. - Suzdal, 1989.- Books 2.- p.132- 139.

7. Брона И.И., Пасичник В.В., Малюта Т.А. Неопределенные и неполные значения в реляционные базах дянныт // Материалы 4-ой Всесоюз. кояф. "Банки данных и знаний", Калинин, нояб. 1983. -с.1-18.

8. Мальта Т.А. Использование в базах данных нечетких данных-средство слияния баз данных и баз знаний // Вестник Львовского политехнического института, N 248, аз- во "Свит", 1990. - с.81-85.

9. Вастеов В.Л., Копчак О.И., Малота Т.Д., Пасичник В.В.Разработка автоматизированной системы го научному направлению "Однородные вычислительные среды и систолические структуры" // Отчет по НИР, ЛПИ, 1989, per.N 01860053898.

10. Копчак О.И., Малота Т.А., Пасичник В.В. Исследование и разработка системы обработки данных на базе ШВЫ профессданвльного класса с ориентацией на СУБД реляционного типа // Отчет по НИР, ЛПИ, 1991, per.N 0I890040I4I.

Підп. до друку- // сз 93 . Формат 60x84і/16. Папір друк. !е 2, Друк. офс. Умови.друк.арк. І* Умови.фарб.-в{д&, ч.5~ Обл.-вид.арк. -/.з/

Тирад <оо прим. Вам. 79 . Безплатно

ЛПІ 290646і Львів-ІЗ. Ст.Бандери, 12

Дільниця оперативного друку ЛПІ Львів, вул. Городоцька, 286