Розробка механізму розширеного запиту за зразком у застосуваннях баз даних

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

Національна академія наук України

Інститут кібернетики імені В.М.Глушкова

ТУЛЬЧИНСЬКИЙ Петро Григорович

УДК 681.3

РОЗРОБКА МЕХАНІЗМУ РОЗШИРЕНОГО ЗАПИТУ ЗА ЗРАЗКОМ

У ЗАСТОСУВАННЯХ БАЗ ДАНИХ

01.05.03 - математичне та програмне забезпечення

обчислювальних машин і систем

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

кандидата фізико-математичних наук

Київ - 2003



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

Робота виконана в Інституті кібернетики ім. В.М.Глушкова Національної академії наук України.

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

ПЕРЕВОЗЧИКОВА Ольга Леонідівна,

Інститут кібернетики ім. В.М.Глушкова НАН України,

завідувач відділом

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

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

ЛАВРІЩЕВА Катерина Михайлівна,

Інститут програмних систем НАН України,

завідувач відділом,

кандидат фізико-математичних наук, доцент

ГОРОХОВСЬКИЙ Семен Самуїлович,

Національний університет „Києво-Могилянська академія”,

директор Інформаційно-комп'ютерного центру

Провідна установа:

Київський національний університет імені Тараса Шевченка (м.Київ)

Захист відбудеться 17.10. 2003 р. о 14 годині на засіданні

спеціалізованої вченої ради Д 26. 194. 02 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою: 03680, МСП, Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві Інституту.

Автореферат розісланий 15.09. 2003 р.

Учений секретар спеціалізованої вченої ради Синявський В.Ф.



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

розробка база данні автоматизація

Актуальність теми. Останнє десятиріччя відзначено суттєвими досягненнями в розробленні програмного забезпечення завдяки RAD-методології та об'єктно-орієнтованим CASE-системам. Методологія швидкої розробки застосувань RAD (Rapid Application Development) ґрунтується на проектуванні програмного забезпечення за спіральною моделлю життєвого циклу. Вартість цієї методології полягає в скорочених строках створення діючого прототипу програмного забезпечення та в економії витрат на його розробку. Розвиток RAD пов'язаний з розробкою нових принципів автоматичного проектування застосувань у CASE-системах. Так, за рахунок внесення семантики у модель даних використання об'єктно-орієнтованого підходу на етапі концептуального моделювання вивело на новий рівень технологію автоматичного проектування застосувань. Зазначимо, що RAD-методологія доцільна насамперед для систем, що складаються з відносно невеликих та слабо зв'язаних клієнтських застосувань, кожне з яких працює з простою підсхемою даних. Те саме стосується сучасних CASE-систем, якщо розглядати їх як засоби генерації вихідного коду програм. Проте частка “простих” застосувань значно упала й продовжує скорочуватися навіть серед ідеальних для CASE-систем офісних систем. Щодо таких сфер, як CAD, ГІС, САПР, системи документообігу, складності, які виникаючі на етапах проектування і супроводження, нерідко переважують користь від реалізації. Отже, удосконалення механізмів генерації та реінжиніринґу застосувань є важливим напрямком розвитку інформаційних технологій на найближче майбутнє.

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконувалася за планом наукових досліджень у рамках бюджетних науково-дослідницьких тем Інституту кібернетики імені В.М.Глушкова НАН України “Розробка методів конструювання і адаптації інтерфейсів користувача у професійних програмних системах” (ДР 0196U005086), “Розробка методів інтерфейсу користувача з сукупністю раціональних агентів” (ДР 0199U001032), “Розробка інструментарію прототипування застосувань за алгебро-граматичними специфікаціями моделі предметної області” (ДНТП 06.02).

Мета і задачі дослідження. Мета роботи полягає у вдосконаленні механізмів підтримки семантичних зв'язків даних в СASE-системах і генераторах застосувань баз даних. Для досягнення поставленої мети в роботі вирішені наступні задачі:

- аналіз відомих CASE-систем, RAD-систем, логічних і концептуальних моделей даних;

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

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

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

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

Об'єктом дослідження є механізми і технології генерації та реінжиніринґу застосувань, предметом дослідження - удосконалення користувальних засобів генерації застосувань складно структурованих БД.

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

Наукова новизна роботи полягає у досягненні таких результатів:

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

- уперше запропонований формалізм структурованої семантичної мережі для подання семантики предметної області стосовно завдань генерації застосувань БД;

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

- розроблений алгоритм виконання графових запитів;

- запропонована візуальна мова ER-QBE формулювання графових запитів, що ґрунтується на принципі запиту за зразком, і розроблений алгоритм її трансляції у мову запитів СКБД;

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

- запропонована технологія розробки застосувань БД на основі графового прототипу.

Практичне значення отриманих результатів.

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

2. Розроблено графічну мову ER-QBE формування графових запитів. ER-QBE, як і традиційні засоби запиту за зразком (Query-by-Example), доступна кінцевому користувачу.

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

Технологія генерації застосувань на основі механізму графових запитів реалізована у вигляді набору штатних засобів СКБД “МікроПошук”, пройшла апробацію у реалізації ланки комерційних застосувань, зокрема:

* геофізична вітрина даних “ГеоПошук”, що промислово експлуатується в понад 20 організаціях України й Західного Сибіру для обробки даних геофізичного дослідження свердловин на рівнях від окремої свердловини до родовища й групи родовищ. Серед користувачів системи “ГеоПошук” геофізичні підрозділи відомих компаній “Сибнефть”, “Роснефть”, “ТНК”, ВАТ “КНГФ”, що обслуговує “Лукойл”. В Україні „ГеоПошук” використовується Стрийською, Полтавською, Сумською та Івано-Франківською геофізичними експедиціями та іншими організаціями. Як курс методології комп'ютеризованої обробки геофізичної інформації “ГеоПошуку” викладають на геологічному факультеті Київського Національного університету імені Т.Г. Шевченка, в Івано-Франківському Національному університеті нафти і газу;

* система “ТопоСвязь” - для розрахунків цифрових мереж електрозв'язку та комутованої міжміської телефонної мережі України;

* діагностичний комплекс АСММО - для масових медичних обстежень населення;

* система “Фактор” - для експертного аналізу і прогнозування при обґрунтуванні управлінських рішень. Вона ґрунтується на інтеграції методу прогнозного графа, запропонованого В.М.Глушковим, з методом аналізу ієрархій Т.Сааті;

* система РТС-ШЕЛЬФ - для комплексного проектування технологічних схем облаштування нафто-, газо- і газоконденсатних родовищ на шельфі Азово-Чорноморського узбережжя України;

* система РТС-МЕТАН - для проектування еколого-безпечних схем утилізації шахтного метану на газо-вугільних родовищах Донбасу. Використовувалась для проектування схем дегазації відомої донецької шахти ім.А.Засядько, шахти Західно-Донбаської № 6-42 Павлоградского району Дніпропетровської області, шахти Горська Державної холдингової компанії “Первомайськвугілля” Луганської області.

Особистий внесок здобувача. У працях, що написані у співавторстві, дисертанту належить: [1] - особисто розроблена технологія прототипування застосувань, описані особливості стосовно реалізації у середовищі реляційно-мережної СКБД “МікроПошук”; [2] - особисто розроблено розширення QBE у формі графових запитів, запропоновано та описано формалізм інформаційного графа, розроблено механізм пошуку на інформаційному графі; [4] - особисто проведено аналіз особливостей організації інформаційних сховищ в геології, розроблені вимоги, принципи побудови і архітектура геофізичної вітрини даних „ГеоПошук”, запропоновано та розроблено механізм керування геофізичною вітриною даних; [5] - особисто запропоновані структуровані семантичні мережі як модель складно структурованих даних, отримані результати щодо повноти та потужності механізму графових запитів.

Апробація результатів роботи. Основні результати роботи доповідалися на 6-й міжнародній конференції “Знання-Діалог-Рішення” (KDS-97), на 7-й міжнародній конференції “Знання-Діалог-Рішення” (KDS-98), на трьох міжнародних конференціях з програмування УкрПРОГ'98, УкрПРОГ'2000, УкрПРОГ'2002.

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

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



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

У вступі обґрунтована актуальність теми, сформульована мета роботи, визначені наукова новизна і практичне значення.

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

Зазначені найважливіші досягнення в галузі CASE-систем, що служать підґрунтям для запропонованих в дисертації механізмів генерації застосувань і запитів БД:

* такі засоби концептуального моделювання як ER-WIN, PowerBuilder отримали широке розповсюдження завдяки простоті й виразності ER-діаграм;

* успіх RAD-методології пов'язаний із скороченням терміну створення діючого прототипу програмного забезпечення (ПЗ) та з економією витрат на його розробку;

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

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

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

У другому розділі дисертації розглядається проблема подання неоднорідної семантично-зв'язної інформації при генерації прикладного ПО. Запропонований механізм графових запитів ґрунтується на МПрО у вигляді спеціального випадку семантичних мереж - структурованої семантичної мережі (ССМ), що введена і досліджена як засіб концептуального моделювання, який узагальнює і таким чином дозволяє абстрагуватися від особливостей популярних моделей - діаграм “сутність-зв'язок” (ERD) і об'єктних діаграм (UML). З узагальненням концептуальної моделі до ССМ вдалося формалізувати вимоги до семантично-зв'язного фрагмента МПрО, запропонувати спосіб його опису й візуалізації у вигляді графового запиту та інформаційного графа відповідно. Графовий запит досліджений як мовний конструкт над ССМ, проаналізовані його потужність й обмеження з позицій концептуального та логічного рівня БД. Доведена повнота графових запитів у двох змістах (семантичному й мовному). Запропонований інтерфейс користувача графових запитів у вигляді графічної мови запиту за зразком - ER-QBE. Розроблені алгоритми інтерпретації графового запиту та трансляції ER-QBE у SQL-подібну мову запитів широкого класу СКБД, зокрема об'єктно-реляційних і об'єктно-орієнтованих. Можливості графових запитів проаналізовані і проілюстровані прикладами.

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

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

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

ССМ разом з кістяком утворює БД. Серед внутрішніх обмежень ССМ такі:

* обов'язкове існування кістяка й приналежність кожної вершини-екземпляра щонайменше одному класу;

* заборона об'єднання вершин-екземплярів, якщо немає дуги між відповідними вершинами-класами;

* однозначне позначення вершини ідентифікатором.

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

Далі показано, як ССМ відображаються на UML та ER моделі. Щодо цієї узагальненої концептуальної моделі виконуються графові запити.

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

Подання фрагмента ССМ як ІГ дає можливість задавати фрагмент ССМ, накладаючи умови відбору маршрутів кожного типу. Таку специфікацію фрагмента ССМ у вигляді кортежу маршрутів з обмеженнями названо графовим запитом (ГЗ). ГЗ подається лісом дерев, вершини й дуги яких відповідають класам і відношенням схеми ССМ. ІГ є результатом виконання ГЗ на всій ССМ. Обмеження ГЗ можна зв'язати з його кінцевими вершинами. Але для узагальнення, а також щоб підвищити зручність виконання ГЗ шляхом покрокового звуження області пошуку, припускається зв'язування обмежень з довільними вершинами та дугами ГЗ. Підтримується рекурсивне описання фрагмента ССМ завдяки “згортанню” ієрархічного ГЗ у компактніший орграф загального виду.

Використання ГЗ/ІГ вирішує дві задачі: структурну декомпозицію ССМ і відбір корисних даних. У традиційному підході до розробки застосувань відбір даних найчастіше упереджує переупорядковування структур даних або включає його до себе (коли використовуються погляди або у RAD). У нашому підході структурна декомпозиція упереджує відбір даних.

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

Далі у дисертації наведені приклади ГЗ/ІГ для фрагмента схеми БД системи розрахунків мереж електрозв'язку "Топосвязь". ІГ розглядається з різних боків як засіб добування, подання й пошуку інформації, як візуальний компонент системи генерації застосувань.

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

ER-QBE як мова специфікації графових запитів. Для успішного використання механізму графових запитів щодо генерації коду велике значення має простота і зручність його застосування. Для формування ГЗ запропонований засіб типу QBE (QBF), пристосований до ССМ. Спочатку цей засіб був розроблений для СКБД "МікроПошук" щодо ER-моделі і звідти отримав назву ER-QBE. Подальші дослідження показали, що підхід, на якому ґрунтується ER-QBE, придатний для ширшого класу моделей. Зберігаючи початкову назву, ER-QBE розглядається як універсальна мова опису ГЗ.

Якщо розглядати ГЗ як аналогію з традиційним SQL-подібним запитом, ІГ виступає аналогом цільового відношення, поданого як таблиця чи форма. В QBE(QBF) користувачем заповнюється вихідна таблиця (форма), за якою автоматично виконуються операції маніпулювання даними БД. На відміну від QBE(QBF), ER-QBE - це не одна форма, а орграф форм. Редактор ER-QBE забезпечує користувача засобами створення й модифікації цього орграфа форм, а потім транслює ГЗ в мову вміщуючої СКБД.

Наведена таблиця порівняння властивостей ER-QBE з QBE(QBF), опис мови ER-QBE та можливості редактора запитів ER-QBE.

Формалізація і обгрунтування. Для дослідження ГЗ перейдемо від наочного подання ССМ графами до продуктивнішого подання - граматиками.

Задамо непусту скінченну множину кореневих вершин ССМ T0 ? E. Введемо множину нетермінальних символів NE та взаємно однозначне відображення

n: E ? NE.

Розглянемо граматику

Г=(N=NE ? A, T=E ? L, A, P=PE ? PE* ? PL ? PL*), в якій кожному екземпляру співставлені термінальний і нетермінальний символи, а кожній кореневій вершині ССМ і кожному твердженню ССМ - продукції наступних типів:

PE={ps1: A ? sS | s ? T0, S = n (s)},

PE*={ps2:A ? s | s ? T0},

PL={pб1:S ? rT | r=(б, s, t ) ? L, S=n(s), T=n(t)},

PL*={pб2:S ? r | r=(б, s, t ) ? L, S=n(s)}.

Назвемо таку праволінійну граматику граматикою ССМ.

Лема 1. Множина ланцюжків мови граматики ССМ тотожна множині шляхів обходу ССМ, що починаються з кореневих вершин ССМ.

Наслідок. ССМ з доданими початковою та кінцевою вершинами є графом переходів скінченного автомата, заданого граматикою ССМ. Загалом це недетермінований граф переходів.

Розглянемо дві граматики ССМ із спільною схемою Г=(N1,T1,A1,P1) та Г2=(N2,T2,A2,P2=PE2?PE2*?PL2?PL*).

Позначимо множину екземплярів ССМ Г1 як E1, множину тверджень - як L1, множину кореневих вершин - як T01 ? E1. Позначимо множину кореневих вершин ССМ Г2 - як T02? E2 , причому

?t,s?T02(f(t)=f(s)?t=s) - тип кожної кореневої вершини ССМ Г2 унікальний,

?r=(?,t,s),q=(?,o,p)?L1 (t=o?r=q) - тип і вхідний екземпляр кожного твердження ССМ Г2 однозначно визначає вихідний екземпляр цього твердження. Нехай кожна продукція Г2 помічена міткою з числа термінальних символів

Г1 :?p?P2 label(p)?T1 , причому

- ? ps1? PE2 label(p s1) ? T01 ? f(s)=f(label(p s1)) - мітка є кореневою вершиною відповідного типу;

- ? p?1? PL2 label(p?1) ? L1 ? r=(?,s,t) ? L2 ? f(r)=f(label(p?1)) - мітка є дугою відповідного типу;

- мітки парних продукцій збігаються: label(px1)=label(px2).

Лема 2. Граматика Г2 безпосередньо зчеплена з граматикою Г1.

Наслідок. Кожному ланцюжку мови граматики Г1 відповідає не більше одного ланцюжка мови граматики Г2.

Назвемо Г2 підсхемою Г1. Назвемо Г2 повною підсхемою граматики ССМ Г1, якщо кожному термінальному ланцюжку мови граматики Г1 відповідає рівно один ланцюжок мови граматики Г2. Назвемо інтерпретацією зворотне перетворення з ланцюжків Г2 у множини співставлених їм ланцюжків Г1.

Лема 3. Довільна граматика ССМ має повну підсхему.

Наслідок. Повна підсхема існує у довільного підграфа ССМ.

Лема 4. Довільна граматика ССМ із скінченною мовою має повну підсхему з скінченною мовою.

Лема 5. Повна підсхема Г2ф довільного фрагмента ССМ Г1ф є підсхемою ССМ Г1, причому її інтерпретація на всій ССМ Г1 призводить до мови, що містить мову фрагмента.

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

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

Названо скороченням підмножину L*(Г)?L(Г) мови Г, що складається з ланцюжків, які не включають повторення символів.

Теорема 1 про повноту підсхеми. Скорочення мови довільної граматики ССМ має повну підсхему із скінченною мовою.

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

Нехай ?SГ2 - мова вміщуючої СКБД для БД зі схемою S, що доповнена синонімами з підсхеми Г2. Позначимо ГЗ G2=(Г2,?), де Г2 ¬- підсхема, а ???SГ2?T2 - множина обмежень, що співставлені терміналам ГЗ. Згідно із способом інтерпретації розрізнюються два типи ІГ: ІГ огляду L*(G2) і ІГ пошуку M(G2). Визначено логічне обмеження, що накладається на правильний ланцюжок ? підсхеми ССМ Г2, як кон'юнкцію обмежень, що співставлені вершинам і дугам ?k.

У дисертації наведений алгоритм трансляції ГЗ у мову вміщуючої СКБД і доведена наступна теорема.

Теорема 2 про повноту ГЗ. Довільний фрагмент CCМ, поданий скінченною множиною маршрутів L?(Г1), яку можна описати скінченною диз'юнкцією обмежень мовою вміщуючої СКБД, подається певним ГЗ: G2=(Г2,?) : M(G2) ? L?(Г1).

Наведений алгоритм трансляції ГЗ у мову вміщуючої СКБД дозволяє обмежуватися посиланнями на предків поточної вершини і таким чином обґрунтовує повноту мови ER-QBE.

Використання підсхеми з нескінченною мовою в деяких випадках дозволяє підвищити потужність ГЗ щодо мови вміщуючої СКБД. Наприклад, логіка предикатів першого порядку не підтримує обмежень за шляхом у загальному випадку, однак деякі конкретні реалізації СКБД, наприклад, Oracle, підтримують необхідну в цьому випадку рекурсію. Незалежно від можливостей вміщуючої СКБД, ГЗ забезпечує подання й перевірку обмежень за шляхом завдяки використанню циклів. Відповідна граматика ССМ має нескінченну мову. Щоб у разі нескінченної мови підсхеми пошук закінчувався за скінченну кількість кроків, необхідно виконувати інтерпретацію ГЗ “вшир”: спочатку перевіряти умови для ланцюжків довжини 1, потім - довжини 2 і т.д.

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

Далі у дисертації детально розглянуті алгоритми та приклади семантичного пошуку за допомогою ГЗ.

У третьому розділі дисертації спочатку описані організація СКБД “МікроПошук” і реалізація технології автоматизованої розробки застосувань за допомогою штатних засобів ER-QBE/ГП СКБД “МікроПошук”. Розглянуто деякі найзначніші застосування СКБД “МікроПошук”, для реалізації яких використовувався механізм ГП. Описані ГП цих застосувань.

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



ВИСНОВКИ

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

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

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

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

3. Розроблений та досліджений механізм графових запитів для добування зі складно структурованої БД мережі семантично зв'язаних фрагментів.

4. Запропонована графічна мова ER-QBE для специфікації графових запитів за зразком. Доведена її повнота та розроблений алгоритм трансляції ER-QBE в SQL-подібну мову вміщуючої СКБД.

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



СПИСОК ОСНОВНИХ ПУБЛІКАЦІЙ ЗА ТЕМОЮ ДИСЕРТАЦІЇ:

1. Инструментарий прототипирования прикладных систем по модели предметной области / В.О. Гречко, О.Л. Перевозчикова, В.Г. Тульчинский, П.Г. Тульчинский // Упр. системы и машины. - 1998. - №1. - С. 78-92.

2. Grechko V., Tulchinsky P., Tulchinsky V. From QBE to graph queries // Informatica. - 1998. - 9, N1. - P. 51-64.

3. Тульчинский П.Г. Организация интерактивной среды анализа геофизических данных // Упр. системы и машины. - 1999. - N1. - С. 28-38.

4. Гречко В.О., Тульчинский В.Г., Тульчинский П.Г. Информационные хранилища в промысловой геофизике // Проблемы программирования. - 2000. - №1-2. - С.435-444.

5. Тульчинский В.Г., Тульчинский П.Г. Графовый прототип приложения // Проблемы программирования. - 2002. - №1-2. - С.489-498.



Тульчинський П.Г. Розробка механізму розширеного запиту за зразком у застосуваннях баз даних. - Рукопис.

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

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

Ключові слова: розробка застосувань, реінжиніринґ, QBE, сутність-зв'язок, ER-модель, об'єктно-орієнтоване проектування, UML-специфікація, семантична мережа.

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

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем.

В диссертации рассмотрены вопросы автоматизации разработки многокомпонентных и распределенных приложений баз данных, которые обрабатывают сложно структурированную информацию. Усовершенствованы механизмы поддержки семантических связей данных в СASE-системах и генераторах приложений баз данных.

Первый раздел посвящен обзору CASE-систем, средств генерации приложений и некоторых современных моделей баз данных: расширений реляционной модели, объектно-реляционных, объектных, объектно-ориентированных моделей, многомерных и динамических моделей. Выделены важнейшие достижения в области CASE-систем, которые служат фундаментом для предложенных в диссертации механизмов генерации приложений и запросов БД.

Во втором разделе рассмотрена проблема представления неоднородной семантически связной информации при генерации прикладного программного обеспечения. Предложен механизм графовых запросов, который основывается на модели предметной области в виде специального случая семантических сетей - структурированных семантических сетей. Структурированные семантические сети введены и исследованы как средство концептуального моделирования. Формализованы требования к семантически-связному фрагменту модели предметной области, предложен способ его описания и визуализации в виде графового запроса и информационного графа соответственно. Графовый запрос исследован как языковой конструкт над структурированными семантическими сетями, проанализированы его мощность и ограничения с позиций концептуального и логического уровня БД. Доказана полнота графовых запросов в двух смыслах (семантическом и языковом). Предложен интерфейс пользователя графовых запросов в виде графического языка запроса по образцу ER-QBE. Разработаны алгоритмы интерпретации графового запроса и трансляции ER-QBE в SQL-подобный язык запросов широкого класса СУБД, в частности объектно-реляционных и объектно-ориентированных. Возможности графовых запросов проанализированы и проиллюстрированы примерами. На основе графовых запросов построен формализм и средство автоматического проектирования приложений - графовый прототип, ориентированный на развитие приложений по спиральной модели жизненного цикла благодаря простоте генерации на первом этапе и возможности отладки, а также общей гибкости и применению визуальных формализмов.

В третьем разделе диссертации описаны организация СУБД "МикроПоиск" и реализация технологии автоматизированной разработки приложений с помощью штатных средств ER-QBE СУБД "МикроПоиск". Рассмотрены некоторые наиболее значительные приложения СУБД "МикроПоиск", для реализации которых использовался механизм графового прототипа. Описаны графовые прототипы этих приложений.

Ключевые слова: разработка приложений, реинжиниринг, QBE, сущность-связь, ER-модель, объектно-ориентированное проектирование, UML-спецификация, семантическая сеть.

Tulchinsky P.G. Development of extended query by example in databases applications. - Manuscript.

Candidate of physics and mathematics sciences thesis in specialty 01.05.03 - the mathematical background and software of computers and systems.

The questions of automating the multi-component and distributed database applications development are examined in the thesis for the case of complicated data structures. The methods of specification, extraction, representation, visualization and processing the semantically related networks of entities or objects are proposed. Visual language for the network specification by example is developed. Its completeness is proved. The algorithm for translation the language in an SQL-like language of nesting DBMS is proposed. Complex specification of graph application prototype and the graph prototype based application development/reengineering technique are developed on its base. The technique is implemented and tested in the process of development of multiple applications.

Keywords: application development, reengineering, QBE, entity-relationship,

ER-model, object-oriented design, UML-specification, semantic network.

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

...