Алгоритмізація основних етапів інформаційного моделювання предметної області

Размещено на http://www.allbest.ru/

НАЦІОНАЛЬНА АКАДЕМИЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МАТЕМАТИЧНИХ МАШИН І СИСТЕМ

УДК 681.3

Автореферат дисертації

на здобуття наукового ступеню кандидата технічних наук

АЛГОРИТМІЗАЦІЯ ОСНОВНИХ ЕТАПІВ ІНФОРМАЦІЙНОГО МОДЕЛЮВАННЯ ПРЕДМЕТНОЇ ОБЛАСТІ

05.13.06 - Автоматизовані системи управління і прогресивні інформаційні технології

Шаталова Юлія Георгіївна

Київ-2003

Дисертацією є рукопис.

Робота виконана в Севастопольському національному технічному університеті Міністерства освіти і науки України

Науковий керівник - доктор технічних наук, професор,

Скатков Олександр Володимирович,

Севастопольський національний технічний університет,

завідувач кафедрою кібернетики та обчислювальної техніки.

Офіційні опоненти:

доктор технічних наук, професор,

Литвинов Віталій Васильович,

Інститут проблем математичних машин і систем НАН України,

завідувач відділу інтегрованих автоматизованих систем спеціального призначення;

кандидат технічних наук,

Вакуленко Оксана Сергіївна,

Національний технічний університет України "КПІ",

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

Провідна установа: Інститут кібернетики ім. В. М. Глушкова Національної академії наук України, відділ теорії математичних машин і систем, м. Київ. Захист відбудеться “_4_” червня_ 2003 р. у 14_ годині на засіданні спеціалізованої вченої ради Д 26.204.01 при Інституті проблем математичних машин і систем Національної академії наук України за адресою: 03187, м. Київ - 164, пр. Академіка Глушкова 42.

З дисертацією можна ознайомитися в бібліотеці Інституту проблем математичних машин і систем НАН України.

Автореферат розісланий “16” _квітня___ 2003 р.

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

спеціалізованої вченої ради Ходак В.І.

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

булевий матричний множина функціональний

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

Розробка інформаційної моделі організації - складний та трудомісткий процес, тому останнім часом на Україні, і, особливо, за кордоном велика увага приділяється теорії та практичним, навіть комерційним розробкам, що дозволяють автоматизувати процес створення інформаційних систем (ІС). Великий розвиток дістали CASE - засоби (Computer Aided Software Engineering). В основі сучасних ІС підприємства лежить, як правило, база даних підприємства або системи баз даних.

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

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

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

Питанням теорії інформаційного моделювання присвячені сотні робіт вітчизняних та закордонних вчених (Дрогаля Т.Г., Калиниченко Л.А., Рубана В.Я., Стогнія А.А., Савинкова В.М., Цаленко М.Ш., Дейта К., Майерса Д., Тіорі Т., Ульмана Дж., Хаббарда Дж. та ін.). Однак питання техніки та технології власне конструювання бази даних організації, особливо з орієнтацією на автоматизоване проектування, у доступній літературі освітлені недостатньо. Наявні на ринку комерційні CASE - засоби, в основному закордонних фірм, у супровідних документах за цілком зрозумілими мотивами не розкривають механіку реалізації закладених в них найважливіших механізмів.

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

Зв'язок роботи з науковими програмами, планами, темами. В цій роботі представлені результати, отримані автором при виконанні програми науково-дослідних робіт у Севастопольському національному технічному університеті, а також за затвердженими Бюро Відділення загальної біології НАНУ держбюджетними темами: на 1996-1998 р. - “Удосконалення методології та створення на її основі комп'ютерних визначників для гідробіології і суміжних областей, дослідження ефективності їх застосування в наукових дослідженнях та освіті” (протокол №1 від 9.01.96, № держ. реєстрації 0196U022109, шифр теми 3.3.5.1) і на 1999-2002 р. - Розділ: “Методологічне узагальнення за оцінкою можливостей сучасних інформаційних технологій для задач збору, систематизації та збереження знань про біорізноманітність морських екосистем”, що входить до теми “Структурно-функціональні основи біорізноманітності морських співтовариств” (протокол №2 від 19.01.99, № держ. реєстрації 0199U001388, шифр теми 3.3.4.2), котра виконувалась в Інституті біології південних морів Національної академії наук України.

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

Для досягнення поставленої мети в дисертаційній роботі потрібно вирішити такі задачі:

Формалізувати побудову концептуальної моделі предметної області у вигляді діаграми “сутність-зв'язок” (ЕR-діаграми), яка опирається на об'єднання представлень користувачів.

Розробити метод побудови концептуальної моделі великого, що нараховує десятки підрозділів і виконує сотні функцій, підприємства, на основі “Єдиного скрізного плану-графіка розробки і постановки на виробництво виробів нової техніки (ЄСПГ)”.

Розробити алгоритм переходу від концептуальної моделі у вигляді діаграми “сутність-зв'язок” до реляційної моделі даних.

Обґрунтувати перехід від множини функціональних залежностей до характеристичної булевої функції.

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

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

Погодити одержані в даній роботі методи і процедури зі стандартом, що одержав широке поширення, SSADM (Structure system analyze and design modeling).

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

Об'єкт дослідження. Наукові і методологічні основи побудови інформаційних моделей предметних галузей.

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

Методи дослідження. При вирішенні задач 1-4 використовувалися методи теорії моделювання, теорії реляційних баз даних, при вирішенні задач 5-8 використовувалися методи дискретної математики, апарат булевих функцій, технологія програмування.

Наукова новизна одержаних результатів. Були отримані такі нові наукові результати:

розроблено метод виявлення інформаційних потреб великого підприємства на основі “Єдиного скрізного плану-графіка (ЕСПГ)”, який відрізняється тим, що на основі системного підходу дозволяє досягти більшої систематичності і методичної цілісності і сприяє більшому ступеню адекватності інформаційної моделі, яка створюється;

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

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

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

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

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

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

Результати роботи продемонстрували свої позитивні сторони в навчальному процесі при проведенні лабораторних та практичних занять за курсами “Комп'ютеризація підприємств” і “Системи баз даних” для студентів спеціальності 7.091501- “Комп'ютерні системи і мережі” у Севастопольському національному технічному університеті, відповідний акт впровадження представлений в додатку до дисертації.

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

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

1). Міжнародна наукова конференція: “Інтелектуалізація обробки інформації” ІОІ' 2000. м. Алушта, 2000 р.

2). Міжнародна наукова конференція молодих вчених. “Понт Євксинський 2000”, Севастополь, 2000 р.

3). Міжнародна наукова конференція ІНФОТЕХ-2000, СевНТУ, м. Севастополь, 2000 р.

4). 4-я міжнародна конференція “Автоматизація проектування дискретних систем”, (CAD DD'2001), ИТК НАН Бєларусі, Мінськ, 2001.

5). Міжнародний симпозіум “Інформаційно-пошукові системи в зоології та ботаніці”, Зоологічний інститут РАНЕЙ, Санкт-Петербург, 1999 р.

6). Науковий семінар кафедри Кібернетики й обчислювальної техніки СевНТУ.

Публікації. За результатами виконаних досліджень опубліковано 5 робіт у збірниках наукових праць, 1 стаття у науковому журналі, 1 -- в матеріалах конференції, 3 - тезиси докладів на конференціях. З приведених публікацій 4 роботи опубліковані в віданнях, передбачених ВАК України.

Структура і об'єм дисертації. Дисертація складається з вступу, трьох розділів, висновку, списку використаних джерел, що містить 151 найменування, і п'яти додатків. Основний текст дисертації містить 150 сторінок. Робота ілюстрована 38 рисунками і 7 таблицями.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі дається обґрунтування необхідності побудови інформаційної моделі підприємства. Виявляються основні складові цього процесу. Вказується, що для реалізації основних складових процесу управління складними об'єктами створюються системи їх моделювання, обробки інформації, котрі називаються інформаційними системами (ІС).

Проаналізовано можливості й особливості двох найбільш розповсюджених методологій проектування і реалізації програмного забезпечення (ПЗ) та побудови функціональних моделей об'єктів якої-небудь предметної області: структурного й об'єктно - орієнтованого підходів. Виявлено переваги та недоліки кожного з них. Незважаючи на те, що об'єктно - орієнтований підхід є перспективним і отримує все більше поширення, багато інструментальних засобів підтримки розробки структурних моделей і моделювання процесів організацій (САSЕ-засоби) сьогодні продовжують використовувати структурний підхід.

Відзначено, що у другій половині 90-х років була розроблена Уніфікована мова моделювання UML (Unified Modeling Language). Мова UML прийнята на озброєння всіма найбільшими компаніями - виробниками ПЗ (IBM, Microsoft, Hewlett - Packard, Oracle та ін.) За задумкою творців UML повинна бути мовою визначення, проектування та документування програмних систем.

Ще один підхід відображено у представленому в 1998 році урядовим центром інформаційних систем Великобританії стандарті SSADM (Structure system analyze and design modeling). Цей стандарт використовує звичайну для структурного підходу модель даних “сутність - зв'язок”, але доповнює її концепцією та технікою моделювання “поводження сутності”, що є кроком в сторону об'єктно - орієнтованого підходу.

Показано, що в світі існують десятки фірм і компаній, що роблять CASE - засоби. Деякі з них підтримують повний життєвий цикл ІС. Наприклад, CASE - засоби Silverrun + JAM підтримують методологію DATARUN. Більшість CASE - засобів орієнтовано на реалізацію окремих етапів процесу проектування ПЗ, тому при їх використанні необхідно враховувати можливість інтеграції конкретного САSЕ- засобу з іншими засобами (можливо власними), котрі використовуються або заплановані до використання в організації.

На світовому ринку програмних продуктів на даний час пропонується понад 300 різних CASE - засобів. Їх ціни належать до широкого діапазону від кількох сотень до декількох тисяч доларів. Але, як показує закордонний досвід, реальні витрати на впровадження САSЕ- засобів звичайно набагато перевищують витрати на їх придбання; з іншого боку, зрозуміло, що САSЕ- засоби зможуть забезпечити можливості для одержання істотної вигоди тільки після завершення процесу їх впровадження. Однак, незважаючи на всі рекламовані потенційні можливості САSЕ - засобів, існує багато прикладів невдач при їх впровадженні.

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

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

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

В другому розділі показано, що інформаційне моделювання організації на концептуальному рівні найбільш доцільно здійснювати за допомогою побудови діаграми “сутність-зв'язок” (ER-діаграми), запропонованої П. Ченом.

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

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

2. Виявляємо елементи даних, які можна розглядати як сутності. Як і попередній етап, етап виділення сутностей важко формалізувати -- необхідно аналізувати семантику кожного елементу даних -- тому пропонується наступна послідовність дій:

1). Серед елементів даних вибираємо іменники, що мають атрибути, явно до них відносні. Для цього будуємо квадратну таблицю (В), назвемо її таблицею сумісності, у якій кожному елементу даних зі списку, отриманого в п.1, відповідає рядок і стовпець. Елемент b_ij таблиці приймає значення 1 у таму і тільки тому випадку, якщо елемент даних, відповідний j-му стовпцю наявним чином є атрибутом елемента, що відповідає i-ої рядку. Приклад таблиці (В) представлено на рис.1.

2). Складаємо список елементів, яким у таблиці (В) відповідають ненульові рядки. Ці елементи обрані як сутності. Додаємо їм як атрибути ті елементи, яким у розглянутому рядку відповідає одиниці. Отримані набори утворюють вихідну множину сутностей і їх атрибутів. В ході подальшого процесу цей список може поповнюватися.

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

4. З таблиці (В) виключаємо рядки і стовпці, що відповідають уже розглянутим елементам даних. У цій таблиці залишаться елементи, з яких можуть бути отримані додаткові сутності і додаткові атрибути. Оскільки з аналізу представлень користувачів, елементам - кандидатам у сутності не вдається вказати атрибути, то це будуть сутності з одним атрибутом, який унікально ідентифікує сутність. Перевагою запропонованого методу є можливість його автоматизації шляхом розроблення відповідної програми, тобто створення CASE-засобу. Показано, що у випадку великих організацій приходимо до концепції розподілених баз даних: на основі аналізу процесів, які виконуються в організації, виділяються функціональні області; виявлення й аналіз елементів даних функціональної області дають можливість побудови предметної бази даних підприємства.

Запропоновано та продемонстровано на прикладі великої організації - КБ радіоелектронного профілю метод побудови концептуальних моделей функціональних областей для підприємств такого масштабу. Метод заснований на використанні Єдиного Скрізного Плану - Графіка (ЄСПГ) розробки і постановки на виробництво виробів нової техніки. Єдиною умовою застосування методу є наявність на підприємстві документа, подібного ЕСПГ.

	судно	вантажопідйомність	особливості	порт	контейнер№	дата прибуття	дата відправлення	дата відплиття	дата доставки	порт призначення	порт відправлення	агент	вантажоодержувач	зміст	Категорія розвантаження	розмір	накладна№	контейнер	ім'я судна	накладна	порт назва
судно	-	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. Таблиця сумісності (В)

У третьому розділі, насамперед, обґрунтовується доцільність вибору реляційної моделі даних для моделювання предметної області. Розроблено алгоритм переходу від діаграми “сутність-зв'язок” до відносин реляційної бази даних. Програма, котра реалізує цей алгоритм, представлена в додатку З. Зазначено найважливіші задачі, що виникають при проектуванні бази даних. Аналізується одне з найважливіших понять теорії реляційних моделей - функціональна залежність (ФЗ). Апарат ФЗ є ефективним інструментом проектування якісної бази даних, позбавленої надмірності й аномалій. Однак найважливішим засобом маніпулювання ФЗ є апарат логічного висновку, широко використовуваний у системах штучного інтелекту. Цей апарат досить складний у використанні для рішення розглянутої в дисертації задачі. У роботі розвинуто інший шлях вирішення проблеми, який заснований на можливості зіставити множину ФЗ булевої функції.

Нехай А₁, А₂,..., А_n -- атрибути відношення R, F -множина ФЗ, котрі виявлені у відношенні R. ХY -- деяка функціональна залежність у F. Зіставимо кожному атрибуту А_i, i {1, 2,..., n} булеву змінну х_i; всій множині атрибутів, що входять у Х, зіставимо кон'юнкцію х відповідних змінних x_i , а атрибутам, що надходять до Y, -- кон'юнкцію y. Тоді функціональній залежності ХY може бути зіставлений імплікативний зв'язок хy, який можна інтерпретувати таким чином: “якщо атрибути з Х приймають деякі значення, то і атрибути з Y повинні приймати відповідні значення”. Замість імплікативного зв'язку без збитків для строгості можна зіставити кон'юнкцію, що є інверсією імплікації і яку будемо називати характеристикою функціональної залежності XY. Характеристичною функцією множини функціональних залежностей F назвемо булеву функцію Ф, що є диз'юнкцією характеристик усіх залежностей, що належать F.

Сформульовано та доведено теореми, які обґрунтовують коректність переходу від системи функціональних залежностей до булевої функції. Цей результат дозволяє використовувати добре розроблений апарат булевих функцій при перетвореннях функціональних залежностей, які необхідні при побудови схеми реляційної бази даних.

Теорема 1. Якщо дві множини функціональних залежностей F та G еквівалентні (F ~ G), то їхні характеристичні функції рівні.

Теорема 2. Мінімальне й оптимальне покриття множини функціональних залежностей можуть бути отримані з найкоротшого незвідного покриття, шляхом застосування правила об'єднання до залежностей з однаковими лівими частинами.

Наслідок. Характеристики усіх функціональних залежностей, виведених з F за аксіомами Армстронга, можуть бути отримані з характеристичної функції множини F.

Теорема 3. Знаходження мінімального покриття множини функціональних залежностей може бути зведене до покриття множини одиничних елементів діаграми Карно характеристичної функції цієї множини мінімальною сукупністю характеристик ФЗ.

Доказ теорем приведено у розділі 3.3 дисертаційної роботи.

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

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

Б. Мінімізація числа ФЗ і числа атрибутних символів. Для побудови оптимальної бази даних найбільший інтерес представляють, так звані, мінімальне й оптимальне покриття.

Визначення. Множина функціональних залежностей F мінімальна, якщо вона містить не більше ФЗ, чим будь-яка еквівалентна множина функціональних залежностей.

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

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

У монографії Д. Мейера “Теорія реляційних баз даних”, відзначається: “На жаль, очевидно, не існує алгоритму знаходження мінімального покриття для множини ФЗ, що має поліноміальну часову складність. Ця проблема належить до класу NP-повних задач, для яких ще не знайдені алгоритми з поліноміальним часом”.

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

В. Наслідок з теореми 2 створює основу для формальної процедури доказу виводимості деякої залежності з заданої множини функціональних залежностей S. Для цього досить з'ясувати, чи є множина одиничних елементів характеристики цієї залежності підмножиною одиничних елементів характеристичної функції множини S. Ця процедура застосовується для обґрунтування правильності інтуїтивно обраного ключа. Однак для побудови CASE-засобу потрібні чітко обкреслені процедури. Тому в роботі розроблена подібна процедура.

Г. Знаходження всіх потенційних ключів відносини. Нехай маємо відношення R зі схемою R(A₁, A₂, …, A_n) і нехай задано деяку множину F функціональних залежностей, виявлених у процесі аналізу атрибутів. З визначення ключа випливає, що якщо набір атрибутів Y₁ є ключем, то в R мають місце наступні функціональні залежності: Y₁ A₁ , Y₁ A₂ , …, Y₁ A_n

Размещено на http://www.allbest.ru/

Якщо атрибутам A₁, A₂, …, A_n зіставити відповідно булеві змінні x₁, x₂, …, x_n, а набору атрибутів Y₁ -- кон'юнкцію відповідних булевих змінних y₁, то на підставі теореми 1 можна стверджувати, що в діаграмі Карно характеристичної функції для F знайдуться конфігурації (інтервали), які відповідають кон'юнкціям

Размещено на http://www.allbest.ru/

Якщо в R(A₁, A₂, …, A_n) m можливих ключів y₁, y₂, …, y_m, то для кожного з них будемо мати сукупність кон'юнкцій, аналогічну (1). У результаті дійдемо висновку, що на діаграмі Карно в цьому випадку, поряд з іншими, знайдуться інтервали, що відповідають наступним кон'юнкціям:

Помітимо, що в (2) y₁, y₂, …, y_m - невідомі, які відповідають кон'юнкціям із змінних х₁, х₂, …, х_n. Задача знаходження можливих ключів зводиться до знаходження цих кон'юнкцій, що, як уже відзначалося, легко виконати, використовуючи матричне представлення.

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

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

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

Показано, що завдяки використання запропонованого методу знаходження потенційних ключів, процедура приведення до НФБК (нормалізація) може бути виконана чисто механічно. Однак, за проектувальником залишається найбільш складна робота: алгоритмічно отримані схеми нормалізованих відносин, що утворюють базу, потребують аналізу з погляду зручності їх семантичної інтерпретації. Цей процес виконується методом проб та помилок: варто переглянути кілька можливих послідовностей декомпозицій, проаналізувати їх, зіставити між собою і вибрати оптимальний варіант. Поряд зі згаданим вище критерієм семантичної прозорості одержуваних відносин (таблиць), важливу роль грає число відносин у нормалізованій базі даних.

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

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

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

У додатку представлено акти впровадження результатів дисертації, ЄСПГ КБ радіоелектронного профілю; результати виявлення функціональних областей, процедур, функцій по ЄСПГ; блок-схема алгоритму переходу від діаграми “сутність-зв'язок” до відносин реляційної бази даних, приклади роботи цього алгоритму; програми, що реалізують розроблені в дисертації алгоритми.

ВИСНОВКИ

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

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

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

На основі системного підходу розроблений метод визначення інформаційних потреб великого підприємства на основі “Єдиного скрізного плану-графіка розробки і постановки на виробництво виробів нової техніки (ЄСПГ)”, що відрізняється тим, що забезпечує високий ступінь адекватності інформаційної моделі, яка створюється.

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

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

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

Дано алгоритм переходу від концептуального рівня опису предметної області до логічного - від ER-діаграми - до попередніх відносин реляційної бази даних. Остаточна логічна схема реляційної бази даних отримується у процесі нормалізації.

На нетривіальному прикладі показано, яким чином можна нормалізувати відносини шляхом їх приведення до нормальної форми Бойса-Кодда (НФБК) за допомогою використання отриманих результатів.

Представлено методику контролю та тестування проекту реляційної бази даних.

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

Положення дисертації використовуються при читанні лекцій і проведенні практичних занять за курсом “Системи баз даних” в Севастопольському національному технічному університеті.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ

Бутаков Є.А, Шаталова Ю.Г. Візуально-матричний метод у логічному проектуванні реляційних баз даних.// Логічне проектування. - Зб. науков. праць. - ІТК НАН Бєларусі. - Мінськ. - Вип. 3, 1998.- с.125-131.

Шаталова Ю.Г. Об'єднання представлень користувачів методом побудови діаграми “сутність-зв'язок” // Вісник СевДТУ. - Вип. 26: Інформатика, електроніка, зв'язок. Зб. науков. праць. - Севастополь, 2000.-с.134-140.

Шаталова Ю.Г. Евристичний метод оптимізації множини функціональних залежностей при проектуванні реляційних баз даних.// Штучний інтелект, №2. - Інститут проблем штучного інтелекту НАНУ.- Донецьк, 2000.- с. 252-257.

Шаталова Ю.Г. Проектування бази даних “Планктон Чорного моря” з використанням ER-діаграм // Екологія моря. - Вип. 53. Зб. науков. праць ІнБПМ НАНУ.- Севастополь, 2000.- с.102-105.

Шаталова Ю.Г. Аналіз інформаційних потреб при проектуванні баз даних великих промислових підприємств // Вісник СевДТУ. - Вип. 31: Інформатика, електроніка, зв'язок. Зб. науков. праць. - Севастополь, 2001-с.52-58.

Бутаков Є.А, Шаталова Ю.Г. Налагодження і тестування реляційних баз даних // Праці 4-й міжнародної конференції “Автоматизація проектування дискретних систем”, (CAD DD'2001), том 3.- ІТК НАН Бєларусі. - Мінськ, 2001.-с.140-148.

Бутаков Е. А., Шаталова Ю. Г. Управління знаннями і безперервна освіта // Вісник СевДТУ. - Вип. 34: Педагогіка. Зб. науков. праць. - Севастополь, 2001.-с.68-73.

Шаталова Ю.Г. Евристичний метод оптимізації безлічі функціональних залежностей при проектуванні реляційних баз даних // Міжнародна наукова конференція: “Інтелектуалізація обробки інформації” ІОІ' 2000. - Тези доповідей. - Сімферополь, 2000.- с. 77.

Гребєнщикова И. Н, Шаталова Ю. Г. Виявлення інформаційних потреб при побудові концептуальної моделі предметної області // Міжнародна наукова конференція: “Інтелектуалізація обробки інформації” ІОІ' 2000. Тези доповідей. - Сімферополь, 2000. - с. 25.

Шаталова Ю. Г. Проектування бази даних “Планктон Чорного моря” з використанням ER-діаграм. // Міжнародна наукова конференція молодих вчених. “Понт Євксинський 2000.”- Тези доповідей. - Севастополь, 2000.-с. 70-71.

АНОТАЦІЯ

Шаталова Ю.Г. Алгоритмізація основних етапів інформаційного моделювання предметної області. - Рукопис.

Дисертація на здобуття вченого ступеню кандидата технічних наук за спеціальністю 05.13.06 “Автоматизовані системи управління і прогресивні інформаційні технології”, Інститут проблем математичних машин і систем НАН України, Київ - 2003 р.

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

Ключові слова: функціональна залежність, діаграма “сутність-зв'язок”, реляційна модель, потенційні ключі, нормалізація бази даних.

АННОТАЦИЯ

Шаталова Ю.Г. Алгоритмизация основных этапов информационного моделирования предметной области. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 “Автоматизированные системы управления и прогрессивные информационные технологии”, Институт проблем математических машин и систем НАН Украины, Киев - 2003 г.

Диссертация посвящена разработке методического, алгоритмического и программного обеспечения процесса разработки информационной модели организации в виде системы реляционных баз данных. В работе представлены методы и алгоритмы, позволяющие автоматизировать процесс проектирования реляционной базы данных. Проанализированы возможности и особенности двух наиболее распространенных методологий проектирования и реализации программного обеспечения (ПО) и построения функциональных моделей объектов какой-либо предметной области: структурного и объектно-ориентированного подходов. Выявлены достоинства и недостатки каждого из них. Несмотря на то, что объектно-ориентированный подход является перспективным и получающим все большее распространение, многие инструментальные средства поддержки разработки структурных моделей и моделирования процессов организаций (CASE-средства) сегодня продолжают использовать структурный подход. Еще один подход, интегрирующий перечисленные выше подходы, отражен в представленном в 1998 году правительственным центром информационных систем Великобритании стандарта SSADM (Structure system analyze and design modeling). Этот стандарт использует обычную для структурного подхода модель данных “сущность - связь”, но дополняет ее концепцией и техникой моделирования “поведения сущности”, что является шагом в сторону объектно-ориентированного подхода.

В данной диссертационной работе продолжены исследования в области методологии проектирования доминирующих в настоящее время в большинстве приложений реляционных баз данных. За основу принят традиционный трехэтапный подход: концептуальное, логическое и физическое проектирование. Вновь полученные результаты направлены на систематизацию, формализацию и алгоритмизацию цепочки процедур последовательно выполняемых в процессе проектирования реляционной базы данных. В частности, предложен метод построения концептуальной модели путем объединения представлений пользователей, решающий задачи выявления сущностей, связей и распределения атрибутов между ними. В качестве концептуальной модели выбрана предложенная П. Ченом диаграмма “сущность-связь”. В случае крупных предприятий достаточно сложной является задача выявления информационных потребностей пользователей. В диссертации предложен метод выявления информационных потребностей, основанный на изучении Единого сквозного плана-графика (ЕСПГ) подготовки и постановки на производство изделий новой техники. По ЕСПГ выявляются функциональные области (ФО) предприятия, а также все элементы данных, используемых в каждой из ФО.

Разработан алгоритм перехода от диаграммы “сущность-связь” к отношениям реляционной базы данных. Программа, реализующая этот алгоритм, представлена в приложении З к диссертации. Указаны наиболее важные задачи, возникающие при проектировании базы данных. Анализируется одно из важнейших понятий теории реляционных моделей - функциональная зависимость (ФЗ). Аппарат ФЗ является эффективным инструментом проектирования качественной базы данных: лишенной избыточности и аномалий. Анализ и преобразование множества ФЗ используется при приведении схемы реляционной базы данных к нормальной форме Бойса - Кодда (НФБК) или к третьей нормальной форме (3НФ). Из теории реляционных баз данных известно, что база данных, находящаяся в 3НФ или НФБК лишена аномалий и избыточности.

Предложен метод манипулирования функциональными зависимостями, основанный на матричном представлении булевых функций. Суть метода заключается в возможности сопоставить каждой функциональной зависимости булеву функцию отрицание импликации, а множеству функциональных зависимостей - дизъюнктивную функцию. Дизъюнктивная функция называется характеристической функцией множества функциональных зависимостей. Используется матричное представление характеристической функции. Предложенный метод позволяет решать задачи, возникающие при логическом проектировании базы данных. Метод легко программируется и достаточно нагляден. Разработан алгоритм поиска всех потенциальных ключей отношения, основанный на предложенном методе манипулирования функциональными зависимостями и использующийся при приведении базы данных к НФБК. Разработаны программы, реализующие предложенные алгоритмы и методы. Предложена методика контроля и тестирования проекта базы данных.

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

SUMMARY

Shatalova J. G. The algorithmization of the basic stages of informative modelling a reality domain. - Manuscript.

The dissertation in competition of the scientific degree of the candidate of the engineering science on the speciality 05.13.06 "Automated control systems and progressive information technologies", the Institute of the Problem the Mathematics Machines and the System NAS of the Ukraine, Kiev - 2003.

The methodical, the algorithmic and the programming aspects of the process of the development of an informative model of organization is researched. As a modelling instrument the system of relational databases is used. Some methods and algorithms allowing to automate a process of the design of a database are submitted. The method of the manipulation of functional dependencies is presented. It used the matrix representation of boolean functions. The essence of the method consists in an opportunity to represent the functional dependencies by boolean function. The method allows to solve some tasks arising in the design of a database. The method is easily programmed. The algorithm of the search of all potential keys of the relation and algorithm of transition from the diagram "entity - relationship" to the relations of a relational database are developed. The programs realizing offered algorithms and methods are developed. The technique of the testing of a project of a database is offered.

Key words: functional dependence, diagram "entity - relationship", relational model, potential keys, normalization of a database.

Размещено на Allbest.ru