Mapping of the relational algebra to the description logic
This paper is dedicated to the data integration problem. In article we discuss the problem of mapping the relational data model to the description logic. With the help of the previously created binary relational data model we created the mappings of the relational algebra to the description logic. W...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/285 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-285 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/4e/bfb769f0b126df4ad15e4e1d1eb5d54e.pdf |
| spelling |
pp_isofts_kiev_ua-article-2852024-04-28T11:37:24Z Mapping of the relational algebra to the description logic Отображение реляционной алгебры в дескриптивную логику Відображення реляційної алгебри в дескриптивную логіку Chystiakova, І.S. binary relational data model; relational algebra; description logic; data mapping; ALC; RDM; RM2; RA UDC 004.62 бинарная реляционная модель данных; реляционная алгебра; дескриптивная логика; отображение данных; ALC; RDM; RM2; RA УДК 004.62 бінарна реляційна модель даних; реляційна алгебра; дескриптивна логіка; відображення даних; ALC; RDM; RM2; RA УДК 004.62 This paper is dedicated to the data integration problem. In article we discuss the problem of mapping the relational data model to the description logic. With the help of the previously created binary relational data model we created the mappings of the relational algebra to the description logic. We used the ALC description logic and its basic extensions (on which SHIQ, SHION and SHOIQ logic is based) to create mappings. We used previously published results in this work which are the binary relational data model definition, the binary relational data structure definition, the mapping of the ALC logic to the relational data model, the mapping of the basic extensions of the ALC logic to the relational data model and mapping the ALC axiomatic to the relational data model.Problems in programming 2018; 2-3: 214-225 Работа посвящена проблеме интеграции данных, а именно отображению реляционной модели данных в дескриптивную логику. С помощью бинарной реляционной модели данных, описание которой было приведено в ранее опубликованных исследованиях, рассматривается механизм создания отображений операций реляционной алгебры в дескриптивную логику. При создании механизмов отображений в работе используется дескриптивная логика ALC и некоторые её расширения. В работе используются ранее опубликованные результаты, а именно: определение и структура бинарной реляционной модели данных, отображения дескриптивной логики ALC, её аксиоматики и расширений в бинарную реляционную модель данных.Problems in programming 2018; 2-3: 214-225 Робота присвячена проблемі інтеграції даних, а саме відображенню реляційної моделі даних в дескриптивну логіку. За допомогою бінарної реляційної моделі даних, опис якої було наведено у раніше опублікованих дослідженнях, розглядається механізм створення відображень операцій реляційної алгебри у дескриптивну логіку. Для створення механізмів відображення в роботі використовується дескриптивна логіка ALC та деякі її розширення. У роботі використовуються раніше опубліковані результати, а саме: визначення та структура бінарної реляційної моделі даних, відображення дескриптивної логіки ALC, її аксіоматики та розширень у бінарну реляційну модель даних.Problems in programming 2018; 2-3: 214-225 Інститут програмних систем НАН України 2018-11-05 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/285 10.15407/pp2018.02.214 PROBLEMS IN PROGRAMMING; No 2-3 (2018); 214-225 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2018); 214-225 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2018); 214-225 1727-4907 10.15407/pp2018.02 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/285/279 Copyright (c) 2018 PROBLEMS OF PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T11:37:24Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
binary relational data model relational algebra description logic data mapping ALC RDM RM2 RA UDC 004.62 |
| spellingShingle |
binary relational data model relational algebra description logic data mapping ALC RDM RM2 RA UDC 004.62 Chystiakova, І.S. Mapping of the relational algebra to the description logic |
| topic_facet |
binary relational data model relational algebra description logic data mapping ALC RDM RM2 RA UDC 004.62 бинарная реляционная модель данных реляционная алгебра дескриптивная логика отображение данных ALC RDM RM2 RA УДК 004.62 бінарна реляційна модель даних реляційна алгебра дескриптивна логіка відображення даних ALC RDM RM2 RA УДК 004.62 |
| format |
Article |
| author |
Chystiakova, І.S. |
| author_facet |
Chystiakova, І.S. |
| author_sort |
Chystiakova, І.S. |
| title |
Mapping of the relational algebra to the description logic |
| title_short |
Mapping of the relational algebra to the description logic |
| title_full |
Mapping of the relational algebra to the description logic |
| title_fullStr |
Mapping of the relational algebra to the description logic |
| title_full_unstemmed |
Mapping of the relational algebra to the description logic |
| title_sort |
mapping of the relational algebra to the description logic |
| title_alt |
Отображение реляционной алгебры в дескриптивную логику Відображення реляційної алгебри в дескриптивную логіку |
| description |
This paper is dedicated to the data integration problem. In article we discuss the problem of mapping the relational data model to the description logic. With the help of the previously created binary relational data model we created the mappings of the relational algebra to the description logic. We used the ALC description logic and its basic extensions (on which SHIQ, SHION and SHOIQ logic is based) to create mappings. We used previously published results in this work which are the binary relational data model definition, the binary relational data structure definition, the mapping of the ALC logic to the relational data model, the mapping of the basic extensions of the ALC logic to the relational data model and mapping the ALC axiomatic to the relational data model.Problems in programming 2018; 2-3: 214-225 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/285 |
| work_keys_str_mv |
AT chystiakovaís mappingoftherelationalalgebratothedescriptionlogic AT chystiakovaís otobraženierelâcionnojalgebryvdeskriptivnuûlogiku AT chystiakovaís vídobražennârelâcíjnoíalgebrivdeskriptivnuûlogíku |
| first_indexed |
2024-09-16T04:08:27Z |
| last_indexed |
2024-09-16T04:08:27Z |
| _version_ |
1818568430948712448 |
| fulltext |
Моделі та засоби систем баз даних і знань
© И.С. Чистякова, 2018
214 ISSN 1727-4907. Проблеми програмування. 2018. № 2–3. Спеціальний випуск
УДК 004.62
ОТОБРАЖЕНИЕ РЕЛЯЦИОННОЙ АЛГЕБРЫ
В ДЕСКРИПТИВНУЮ ЛОГИКУ
И.С. Чистякова
Работа посвящена проблеме интеграции данных, а именно отображению реляционной модели данных в дескриптивную логику.
С помощью бинарной реляционной модели данных, описание которой было приведено в ранее опубликованных исследованиях,
рассматривается механизм создания отображений операций реляционной алгебры в дескриптивную логику. При создании
механизмов отображений в работе используется дескриптивная логика ALC и некоторые её расширения. В работе используются
ранее опубликованные результаты, а именно: определение и структура бинарной реляционной модели данных, отображения
дескриптивной логики ALC, её аксиоматики и расширений в бинарную реляционную модель данных.
Ключевые слова: бинарная реляционная модель данных, реляционная алгебра, дескриптивная логика, отображение данных,
ALC, RDM, RM2, RA.
Робота присвячена проблемі інтеграції даних, а саме відображенню реляційної моделі даних в дескриптивну логіку. За
допомогою бінарної реляційної моделі даних, опис якої було наведено у раніше опублікованих дослідженнях, розглядається
механізм створення відображень операцій реляційної алгебри у дескриптивну логіку. Для створення механізмів відображення в
роботі використовується дескриптивна логіка ALC та деякі її розширення. У роботі використовуються раніше опубліковані
результати, а саме: визначення та структура бінарної реляційної моделі даних, відображення дескриптивної логіки ALC, її
аксіоматики та розширень у бінарну реляційну модель даних.
Ключові слова: бінарна реляційна модель даних, реляційна алгебра, дескриптивна логіка, відображення даних, ALC, RDM,
RM2, RA.
This paper is dedicated to the data integration problem. In article we discuss the problem of mapping the relational data model to the
description logic. With the help of the previously created binary relational data model we created the mappings of the relati onal algebra
to the description logic. We used the ALC description logic and its basic extensions (on which SHIQ, SHION and SHOIQ logic is based)
to create mappings. We used previously published results in this work which are the binary relational data model definition, the binary
relational data structure definition, the mapping of the ALC logic to the relational data model, the mapping of the basic extensions of the
ALC logic to the relational data model and mapping the ALC axiomatic to the relational data model.
Key words: binary relational data model, relational algebra, description logic, data mapping, ALC, RDM, RM 2, RA.
Введение
В современном научном пространстве, начиная с середины 70-х годов, существует глобальная
проблема интеграции данных. Именно во второй половине прошлого века начинает формироваться
представление о многоуровневой архитектуре баз данных (БД), о модели данных как инструменте
информационного моделирования реальности и об отображениях между существующими моделями. Ввиду
этого, акцент делался на поддержке глобальной схемы (впоследствии получившей название концептуальной)
и локальных схем, в основе которых лежат различные (или одна и та же) модели данных (МД),
функционирующих в разных узлах системы, которая находится под управлением одной и той же системы
управления базами данных (СУБД). В дальнейшем проблему обобщили, и она стала включать в себя также
создание хранилищ данных, репозиториев информационных ресурсов, веб-приложений. Сегодня ключевым
аспектом интеграции данных является интеграция неоднородных данных различных информационных
систем.
Как отмечалось в работе [1], объем информации, существующей в интернет-пространстве, с каждым
днем возрастает в геометрической прогрессии, а её релевантность – в арифметической. Это порождает ряд
проблем, связанных с использованием и хранением данных. В частности выделяют ряд причин [1],
порождающих их гетерогенность, ввиду которых интеграция и совместное использование данных из
множества таких источников является сложной и неизменно актуальной задачей на протяжении последних
десятилетий.
Проблема интеграции данных заключается в таком логическом объединении данных,
принадлежащих разнородным источникам, которое обеспечивает единое представление и оперирование
этими данными. Система интеграции данных (СИД) позволяет освободить пользователя от необходимости
самостоятельно отбирать источники, в которых находится интересующая пользователя информация,
обращаться к каждому источнику по отдельности и вручную сопоставлять и объединять данные из различных
источников.
Работа [2] посвящена подробному изучению комплексной проблемы интеграции данных, согласно
которой можно выделить три основные составляющие данной проблемы:
схемы интеграции данных;
отображения между моделями данных;
способы манипулирования данными.
Моделі та засоби систем баз даних і знань
215
В рамках решения комплексной проблемы интеграции данных ряд исследований [1, 3–7] был посвящен
созданию отображений между моделями, а именно между дескриптивной логикой (DL), которую можно
рассматривать как модель данных [3, 7] и реляционной моделью данных. В данных публикациях была
представлена бинарная реляционная модель данных (RM2) – специальный вариант реляционной модели данных
– промежуточная модель, с помощью которой все компоненты дескриптивной логики ALC (лежащей в основе
множества современных DL), а также её основные расширения и аксиоматику, можно отобразить в
реляционную модель данных.
Однако, эти исследования остаются неполными до тех пор, пока открыт вопрос возможности обратного
отображения РМД в DL. Данная статья восполняет этот пробел и рассматривает вопросы отображения
реляционной структуры данных и операций реляционной алгебры в дескриптивную логику.
Раздел 1 посвящен краткому описанию RM2 и её составляющих. В разделе 2 приводится описание
отображений операций реляционной алгебры (РА) в DL. Завершают текущую публикацию основные выводы и
дальнейшие планы исследований.
Краткое описание бинарной реляционной модели данных
Для решения вопроса установления взаимосвязей между DL и РМД планировалось рассматривать
классическую РМД Кодда [8]. Однако, это порождает ряд проблем, решить которые затруднительно. Например,
неясно каким образом в РМД следует поддерживать гипотезу открытого мира, а также конструкторы концептов
и ролей любой DL. В связи с этим в ряде работ была определена бинарная реляционная модель данных (БРМД),
в которой решаются перечисленные проблемы. Её подробное описание можно найти в работах [1, 7].
Акцентируем внимание лишь на основных определениях.
Бинарная реляционная модель данных (RM2) – это совокупность бинарной реляционной структуры
данных, бинарной реляционной алгебры и ограничений целостности.
Бинарная реляционная структура данных – это совокупность реляционных отношений арности не более
2. Так как в настоящей статье речь идёт только о реляционных отношениях, то для краткости будем
использовать термин «отношение».
Отношение – это пара ( ES R ,R ), где SR – схема (интенсионал) отношения, а ER – экземпляр
(экстенсионал) отношения.
Схема отношения SR – это выражение вида ])D:A [, D:R(A 2211 , где:
R – имя отношения;
1A , 2A – имена атрибутов отношения;
1D , 2D – имена доменов отношения, определяющих области допустимых значений атрибутов (на одном
домене может быть определено множество атрибутов).
Если указание имен доменов не существенно, то схема записывается следующим образом ])A [, R(A 21 .
Имена доменов и имена отношений являются уникальными в реляционной структуре. Имена атрибутов
являются уникальными в схеме отношения, но могут повторяться в различных схемах.
Экземпляр отношения ER это подмножество:
- либо домена, на котором определен атрибут унарного отношения 1
E DR ;
- либо декартового произведения доменов, на которых определены два атрибута бинарного
отношения: 21
E DDR .
Бинарная реляционная алгебра (RA2) – это совокупность операций, определенных на бинарной
реляционной структуре.
Она является замкнутой в том смысле, что результат выполнения любой операции также является
отношением. Можно выделить три вида операций:
1) операции, которые не увеличивают арность результирующего отношения. Они являются полными
аналогами операций классической реляционной алгебры (RA);
2) операции, увеличивающие арность результирующего отношения. Они имеют свои аналоги в RA. В
связи с этим, в бинарной реляционной алгебре вводятся их модификации, результирующие отношения которых
не превышают арности 2;
3) операции, являющиеся новыми по отношению к RA.
Все три типа операций RA2 подробнее будут рассмотрены далее.
Операции, унаследованные из RA
Операции реляционной алгебры делятся на две большие группы: основные и дополнительные.
Моделі та засоби систем баз даних і знань
216
Основные:
1) не увеличивают арность результирующего отношения
- теоретико-множественные:
объединение
пересечение
разность
- проекция
- селекция
- деление
2) увеличивают арность результирующего отношения:
- соединение
- декартово произведение.
Дополнительные:
- переименование
- присвоение
- обобщенная проекция
- внешнее соединение и т. д.
В данной статье мы будем рассматривать отображения только тех операций, которые дублируются в
бинарной реляционной алгебре (RA2). К ним относятся все операции из группы основных и дополнительная
операция переименования.
Рассмотрим каждую в отдельности.
Определение 1. Два отношения со схемами ])A [, (AR 211 и ])B [, (BR 212 являются совместимыми (по
объединению), если имеют одинаковую арность, и пары атрибутов 2,1i),B,(A ii определены на одном и том
же домене.
Над совместимыми отношениями определяются следующие три множественные операции.
1. Объединение ()
}Rr R r |{r = R R 2121 .
2. Пересечение ()
}Rr R r |{r = R R 2121 .
3. Разность ( )
}Rr R r |{r = R R 2121 .
4. Проекция (π). Проекцией бинарного отношения со схемой B)R(A, на атрибут A (или B ),
обозначаемой π (R)A (или π (R)B ), называется отношение, экземпляр которого содержит только
A -компоненты ( B -компоненты) кортежей отношения R :
π R} r | {r[A](R)A ,
π R} r | {r[B](R)B .
Здесь запись r[A] ( r[B] ) обозначает выделение из кортежа r компоненты, принадлежащей значению
атрибута A (В). Схема результирующего отношения наследует имя атрибута A (В), а имя отношения
определяется операцией именования.
Определение 2. Пусть – любой из следующих предикатов сравнения: , , , , . Атрибуты A и В
одного и того же или различных отношений называются -сравнимыми, если для любых пар значений A a и
B b определено выражение а b. Наборы атрибутов )A ,(A = М 21 и )B ,(B = N 21 называются
-сравнимыми, если пары атрибутов )B ,(A ii являются -сравнимыми. В этом случае M N подразумевает
следующее:
2211 В θ A B θ A = N θ М .
Моделі та засоби систем баз даних і знань
217
5. Селекция (σ). Пусть М и N – θ -сравнимые атрибуты или наборы атрибутов отношения R. Селекцией
отношения R по условию М N, обозначаемой σМN(R), называется отношение, экземпляр которого содержит те
кортежи R, на которых истинно условие М N:
σМN(R) = {r | r R ∧ r[M] θ r[N]}.
Один из атрибутов М или N может быть константой С. Например, если константой является N, то
селекция принимает вид:
σМN(R) = {r | r R ∧ r[M] θ С}.
В этом случае селекция также применима к унарным отношениям.
Схема результирующего отношения наследует имена атрибутов отношения R, а имя отношения
определяется операцией именования.
Определение 3. Пусть задано отношение B)R(A, . Образом кортежа Ar π (R)A , записываемым как
)R(IrA , называется такое множество кортежей Br π (R)B , соединение которых с Ar принадлежит R:
)R(IrA = {rB | rB πB(R) ∧ (rA,rB) R}.
6. Деление (). Пусть заданы отношения B)(A,R1 и D)(C,R2 , причем B и C – сравнимы по предикату
равенства. Делением 1R на 2R по B и C, обозначаемым 1R [B÷C)] 2R , называется отношение, которое состоит
из таких кортежей Ar π )(R1A , образы которых )R(Ir 1A содержат все кортежи проекции π )(R2C :
1R [B÷C] 2R = { Ar | Ar π )(R1A ∧ )R(Ir 1A ⊇ π )(R2C }.
Отношение 2R может быть унарным. Если, например, (C)R2 , то:
1R [B÷C] 2R = { Ar | Ar | π )(R1A ∧ )R(Ir 1A ⊇ 2R }.
Схема результирующего отношения наследует имя атрибута A из 1R , а имя отношения определяется
операцией именования.
Деление следующим образом выражается через произведение, разность и проекцию:
1R [B÷C] 2R = π )(R1A πA ((π )(R1A × π )(R2C ) 1R ).
7. Соединение (⋈). В RM данная операция увеличивает арность результата. В связи с этим в 2RM
предлагается модифицированный вариант соединения, суть которого заключается в том, что если
результирующее отношение оказывается арности выше двух, то к нему применяется проекция по одному или
двум атрибутам.
Пусть 1R (B) и )С(R2 – унарные отношения, где В и С – -сравнимые атрибуты.
Определение 4. Соединение отношения 1R с отношением 2R по условию B C, обозначаемое
1R ⋈BC 2R , определяется следующим образом:
1R ⋈BC 2R = {(r1,r2) | r1 1R ∧ r2 2R ∧ r1[B] r2[C]}.
Определение 5. Пусть один или оба отношения имеют арность 2, тогда соединение определяется
следующим образом. Пусть ji A,A – любые два атрибута из множества атрибутов исходных отношений. Пусть
также 1R содержит атрибут mA , а 2R – nA , которые являются -сравнимыми, тогда соединение 1R и 2R по
условию mA nA , обозначаемое через 1R ⋈
AnA
AA
m
ji
],[
2R , определяется следующим образом:
1R ⋈
ik
ji
AA
AA
],[
2R = π 1A,A (R
ji
⋈
nmθAA ).
Моделі та засоби систем баз даних і знань
218
Также допускается многократное соединение унарных и/или бинарных отношений, с последующей
проекцией на два атрибута, то есть:
π 1A,A (R
ji
⋈
2θAA R
nm
⋈…⋈
kθAA R
qp
).
Схема результирующего отношения наследует имена атрибутов отношений 1R и 2R , а имя отношения
определяется операцией именования.
8. (Декартово) произведение ( ). Декартовым произведением унарных отношений 1R и 2R ,
обозначаемым 21 RR , называется бинарное отношение, экземпляр которого содержит все возможные
соединения (конкатенации) кортежей отношений 1R и 2R :
1R 2R = {( 21 r,r ) | 1r 1R ∧ 2r 2R }.
Схема результирующего отношения наследует имена атрибутов отношений 1R и 2R , а имя отношения
определяется операцией именования. Произведение двух бинарных или бинарного и унарного отношений не
допускаются в 2RM .
9. Именование/переименование (ρ). Мы будем использовать следующие три варианта этой операции:
- )E(ρR – отношению, полученному в результате вычисления выражения Е 2RA , присваивается имя R .
- Rρ (A1[,A2])(E) – отношению, полученному в результате вычисления выражения Е 2RA ,
присваивается схема R(A1 [, A2]).
- )E(ρA B – в отношении, полученном в результате вычисления выражения Е 2RA , атрибут А
переименовывается в атрибут В.
Операции, вводимые только в RA2
Определим еще несколько операций, которых нет в RA .
10. Инверсное деление (/). Пусть заданы отношения B)(A,R1 и D)(C,R2 , причем B и C – сравнимы по
предикату равенства. Инверсным делением 1R на 2R по B и C, обозначаемым 1R [B/C)] 2R , называется
отношение, которое состоит из таких кортежей Ar π )R( 1A , образы которых )R(Ir 1A содержатся среди
кортежей проекции π )R( 2C :
1R [B/C] 2R = { Ar | Ar π )R( 1A ∧ )R(Ir 1A ⊆ π )R( 2C }.
Отличие инверсного деления от обычного заключается в том, что в первом случае образы содержатся во
втором операнде, а во втором случае – содержат второй операнд. В работах [9, 10] доказано, что инверсное
деление следующим образом выражается через уже определенные операции:
1R [B/C] 2R = π )R( 1A π 1A R( (π )R( 1A (π )R( 1B π ))R( 2C .
11. Номинал ({}). Суть этой операции – построение унарного или бинарного отношения из заданной
константы или пары констант. В RA такой операции нет, так как эта алгебра вообще не рассматривает вопросы
создания отношений. Мы же включили эту операцию для поддержания одноименного конструктора в DL.
Кроме того, эта операция не выходит за рамки реализаций реляционной модели, так как все реляционные СУБД
предоставляют такую возможность.
Пусть заданы константы a и b. Тогда выражения {a} и b)}{(a, называются номиналами и означают
построение унарного (бинарного) отношения, содержащего единственный кортеж – а или b)(a, . Схема такого
отношения не определена и задается операцией именования.
В работе [4] рассмотрена операция транзитивного замыкания (+), расширяющая стандартный синтаксис
логики DL ALC. В реляционной алгебре такой операции нет. Однако, эта проблема решена в реляционных
СУБД, поддерживающих рекурсивный SQL, где есть возможность выразить транзитивное замыкание.
Подробнее об этом можно познакомиться в работе [6]. В связи с этим мы вводим в 2RA аналогичную операцию
транзитивного замыкания R .
Моделі та засоби систем баз даних і знань
219
12. Транзитивное замыкание (+).
Пусть задано бинарное отношение со схемой B)R(A, . Обозначим операцию транзитивного замыкания
отношения через R . Она определяется следующим образом:
R = {r | ∀ 1r ∀ 2r R ( 1r = ( 11 b,a ) ∧ 2r = ( 22 b,a ) ∧ 1b = 2a → r = ( 1a , 2b )}.
Описание отображений бинарной реляционной модели данных в дескриптивную
логику
При создании бинарной реляционной модели данных мы работали с логикой ALC и её расширениями.
Обоснование такого решения приведено в [1]. Очевидно, что для создания отображений РМД в DL этой логики
будет недостаточно, т.к. необходимо работать с теми же расширениями, и показать их отображение в обратную
сторону. Поэтому, мы остановились на дескриптивной логике SHOIQ, которая включает в свой состав все
основные расширения ALC.
Дескриптивная логика ALC и ее расширение
Перед созданием отображений, следует напомнить основные составляющие дескриптивной логики ALC.
Её синтаксис определяется следующим образом:
⊤ | ⊥ |A | ¬C | C ⊓ D | C ⊔ D |∃R.C |∀R.C,
где А – атомарный концепт, R –атомарная роль, C, D – произвольные концепты.
Семантика ALC задается через понятие интерпретации. Интерпретация – это пара I = (Δ, .I), где Δ –
непустое множество, называемое областью интерпретации, аI – интерпретирующая функция, которая
присваивает каждому атомарному концепту А множество АI ⊆ Δ, а каждой атомарной роли R – бинарное
отношение RI ⊆ Δ × Δ.
Остальные формулы интерпретируются следующим образом:
⊤I = Δ, ⊥I = ∅ , (¬A) I = Δ \ A I,
(C ⊓ D)I = CI ∩ DI,
(C ⊔ D) I = C I ∪ D I,
∃R.C = {a ∊ Δ | ∃ b ∊ Δ ((a, b) ∊ IR ∧ b ∊ CI )},
R.C = {a ∊ Δ | b ∊ Δ ((a, b) ∊ IR → b ∊ CI )}.
Существуют различные расширения ALC. Приведем то из них, которое будет использоваться при
описании отображения RM2 в DL
Номинал. Номинал – это конструктор концепта, который строит концепт из индивида. Если d есть имя
индивида то {d} есть концепт. Семантика номинала следующая: }{d{d} II .
Универсальная роль. Содержательно универсальная роль 𝕌 – это объединение всех возможных ролей, а
формально она интерпретируется следующим образом: 𝕌I = Δ× Δ
Конструкторы ролей. Пусть R и S являются ролями, а C – концепт, тогда ролями также являются
следующие выражения: R (обратная роль), R (дополнение), R ⊓ S (пересечение), R ⊔S (объединение),
SR (композиция), id(C) (идентичность концепта), R (транзитивное замыкание), *R (рефлексивно-
транзитивное замыкание).
Их семантика следующая:
}Re)(d, |ΔΔd){(e,)(R II
,
II R\ΔΔR)( ,
(R ⊓
III SRS) , (R ⊔ III SRS) ,
)}Sd)(c,Rc)Δ((e,c|ΔΔd){(e,S)(R III ,
Моделі та засоби систем баз даних і знань
220
}Ce|ΔΔe){(e,(id(C)) II .
Пусть Δ}e|e){(e,R0 , а nR – R...RR n раз, тогда
1n
nII )(R)(R
,
0n
nII* )(R)(R
.
Правила эквивалентного преобразования
Приведем ряд правил эквивалентного преобразования операций реляционной алгебры, которые мы будем
использовать в дальнейшем. Два выражения реляционной алгебры 1E , 2E эквивалентны, если относительно
любого набора правильно построенной реляционной базы данных они дают отношения с одинаковыми
экземплярами. Эквивалентность будем записывать в виде правил эквивалентности вида 1E ≡ 2E .
Правила эквивалентного преобразования выглядят следующим образом.
1. Коммутативность произведения
1E × 2E ≡ 2E × 1E .
2. Ассоциативность произведения
( 1E × 2E )× 3E ≡ 1E ×( 2E × 3E ).
3. Представление произведения и селекции в виде соединения
σp( 1E × 2E )≡ 1E ⋈ p 2E .
4. Коммутативность селекции.
Пусть p1,p2 – предикаты, тогда
σp1(σp2(E)) ≡ σp2(σp1(E)).
5. Коммутативность соединения
1E ⋈ p 2E ≡ 2E ⋈ p 1E .
6. Ассоциативность соединения
( 1E ⋈ p 2E ) ⋈ q&r 3E ≡ ( 1E ⋈ p&q( 2E ⋈ r 3E ),
где r содержит атрибуты только из 2E и 3E .
7. Поглощение проекций.
При наличии последовательности проекций необходима только самая внешняя, остальные могут быть
опущены
πА(πВ(· · · πС(E)· · ·)) ≡ πА(E).
8. Дистрибутивность проекции и произведения:
а) Если набор атрибутов А принадлежит 1E , то
πА( 1E × 2E ) ≡ πА( 1E ),
б) Если наборы атрибутов А и В принадлежат E1 и E2 соответственно, то
πА,В( 1E × 2E ) ≡ πА( 1E ) × πВ( 2E ).
9. Дистрибутивность проекции и соединения
πА,В( 1E ⋈ p 2E ) ≡ πА( 1E ) ⋈ p πВ( 2E ),
Моделі та засоби систем баз даних і знань
221
если предикат р содержит только атрибуты из (А⋃В), и А (В) содержат только атрибуты из 1E ( 2E ).
Отображение операций бинарной реляционной алгебры в DL ALC и ее расширение
Перейдем к описанию отображений операций бинарной реляционной модели данных в дескриптивную
логику Отметим, что в РА операции селекции и соединения используют широкий набор предикатов, так
называемые θ-предикаты, θ = {=, ≠, <, ≤, >, ≥}. В нашем случае мы рассмотрим только один предикат –
равенства (=) Такую реляционную алгебру мы назовем бинарной реляционной алгеброй с равенством и будем
обозначать так: 2PA .
Пусть заданы следующие унарные и бинарные отношения:
1P (F), 2P (G), 1Q (K,L), 2Q (M,N).
Согласно определению выше, реляционное отношение состоит из интенсионала и экстенсионала.
Отображение унарного отношения в дескриптивную логику происходит исходя их следующих правил:
имя отношения отображается в имя концепта;
экстенсионал отношения отображается в интерпретацию концепта.
Отображение бинарного отношения в дескриптивную логику происходит исходя из следующих правил:
имя отношения отображается в имя роли;
экстенсионал отношения отображается в интерпретацию роли.
Пусть также имеются атомарные концепты C, D и атомарные роли R и S дескриптивной логики.
Отображение между атомарными отношениями, концептами и ролями задается следующим образом:
1P ↔ С, если
E
1P = СI,
2P ↔ D, если
E
2P = DI,
Q1 ↔ R, если
E
1Q = RI,
2Q ↔ S, если
E
2Q = SI.
Здесь верхний индекс Е указывает на экстенсионал отношения, а верхний индекс I – на интерпретацию
концепта или роли.
Теперь рассмотрим отображения операций 2PA .
1. Объединение
Отображение объединения двух концептов выглядит следующим образом:
1P ⋃ 2P ↔ C ⊔ D.
Отображение объединения двух ролей выглядит следующим образом:
1Q ⋃ 2Q ↔ R ⊔ S.
2. Пересечение
Отображение пересечения двух концептов выглядит следующим образом:
1P ⋂ 2P ↔ C ⊓ D.
Отображение пересечения двух ролей выглядит следующим образом:
1Q ⋂ 2Q ↔ R ⊓ S.
3. Разность
Поскольку в РА не используется теоретико-множественная операция дополнения, а в дескриптивной
логике она присутствует в виде дополнения концепта, то отображение интенсионала операции разности
выглядит следующим образом:
1P − 2P ↔ C ⊓ (¬D).
Моделі та засоби систем баз даних і знань
222
1Q − 2Q ↔ R ⊓ (¬S).
4. Проекция
Операция проекции существует только для бинарных отношений. Исходя из определения проекции, мы
получаем в результате совокупность таких а, для которых существует b такой, что пара (a, b) состоит в
отношении R. А это соответствует определению концепта существования на всех области определения. Таким
образом, отображение операции проекции выглядит следующим образом:
π 1KQ (K,L) ↔ ∃R.⊤,
π 1LQ (K,L) ↔ ∃R¯.⊤.
5. Селекция
Операция селекция предполагает отбор строк, удовлетворяющих некоторому условию, которое в свою
очередь задается на атрибутах. В нашем исследовании отображение селекции мы будем рассматривать
только по условию равенства, т.к. в дескриптивных логиках (ALC и некоторых её расширениях) существует
только условие равенства концептов, ролей и индивидов.
Рассмотрим варианты такой селекции для унарных и бинарных отношений. Если один из атрибутов
условия селекции является константой, то операция селекции возможна как для унарных, так и для бинарных
отношений. В этом случае в результате селекции бинарного отношения получается такое а (совокупность
таких а), которое принадлежит множеству, состоящему из константы (перечня констант) условия.
Следует напомнить, что унарное отношение отображается в концепт в дескриптивной логике. В
результате отображения операции селекции по условию равенства мы также получаем концепт. Поскольку, в
дескриптивной логике не существует операции создания концепта из концепта, но существует операция
создания роли из концепта – id(С), которую мы называли идентичность концепта – то отображение
операции селекции для унарного отношения будет происходить следующим образом. Из концепта, который
является интерпретацией унарного отношения, создаётся роль с помощью операции id(C), а затем
выполняется селекция по заданному условию равенства.
Отображение операции селекции, бинарного отношения по условию равенства атрибутов выглядит
следующим образом:
σ 1LK Q (K,L) ↔ id(∃R.⊤) ⊓ R.
Отображение операции селекции, бинарного отношения по условию равенства атрибута константе
выглядит следующим образом:
σ 11L Q (K,L) ↔ id(∃R.{l}) ○ 𝕌 ○ id({l}),
σ 1kK Q (K,L) ↔ id(∃R¯.{k}) ○ 𝕌 ○ id({k}).
Отображение операции селекции, унарного отношения по условию равенства атрибута константе
выглядит следующим образом:
σ 1fF P (F) ↔ ∃(id(R)).{f}.
6. Деление
Операция обычного деления в классической RA выразима через совокупность других операций RA.
Отображение операции обычного деления выглядит следующим образом:
1Q (K,L)[L÷F]Р1(F) = π 1KQ – πK((π 1KQ × 1P ) – 1Q ) ↔ ∃R.⊤ – ∃ ((id(∃R.⊤) ○ 𝕌 ○ id(C)) – R).⊤.
7. Соединение
Рассмотрим следующие варианты операции соединения.
7.1. Соединение двух унарных отношений в результате дают бинарное отношение. Отображение такого
варианта операции соединения выглядит следующим образом:
Р1(F)⋈F=GP2(G) ↔ id(C ⊓ D).
7.2. Соединение унарного и бинарного отношения дают в результате трехарное отношение. Поскольку в
RA2 допустимы только бинарные отношения, то нам необходимо выполнить проекцию на один или два
атрибута, чтобы получить допустимое результирующее отношение. Рассмотрим следующие варианты
соединения:
Моделі та засоби систем баз даних і знань
223
a) πF(Р1(F)⋈F=KQ1(K,L)) = πF(Р1(F) ⋈F=KπKQ1(K,L)) ↔ C ⊓ ∃R.⊤;
b) πK(Р1(F)⋈F=KQ1(K,L)) = πK(Р1(F) ⋈F=KπKQ1(K,L)) ↔ C ⊓ ∃R.⊤;
c) πL(Р1(F)⋈F=KQ1(K,L)) ↔ ∃R¯.(C ⊓ ∃R.⊤);
d) πF,K(Р1(F)⋈F=KQ1(K,L)) ↔ id(C ⊓ ∃R.⊤);
e) πK,L(Р1(F)⋈F=KQ1(K,L)) ↔ R – (id(∃R.⊤ – С) ○ 𝕌 ○ id(∃R¯.⊤);
f) πF,L(Р1(F)⋈F=KQ1(K,L)) – равносильно формуле 7.2.е).
7.3. Соединение двух бинарных отношений даёт четырехарное отношение, которое необходимо, как и в
предыдущем варианте, спроецировать для получения допустимого в RA2 результирующего отношения.
Q1(K,L)⋈L=MQ2(M,N).
Как и выше, характер отображения зависит от варианта проекции результата соединение.
a) Если в результирующей проекции нет атрибута K, то заменяем Q1(K,L) на πLQ1(K,L) и все сводится к
варианту 7.2.
b) Если в результирующей проекции есть атрибут К, то получаем следующие варианты:
πK(Q1(K,L)⋈L=MQ2(M,N)) – заменим Q2(M,N) на πMQ2(M,N), и тем самым, свели к варианту 7.2.c);
πK,L(Q1(K,L)⋈L=MQ2(M,N)) – заменим Q2(M,N) на πM(M,N), и тем самым, свели к варианту 7.2.e);
πK,M(Q1(K,L)⋈L=MQ2(M,N)) –сводится к варианту 7.2.b);
πK,N(Q1(K,L)⋈L=MQ2(M,N)) ↔ R ○ S.
8. Декартово произведение
Рассмотрим следующие варианты операции декартового произведения.
8.1. Произведение двух унарных отношений. Опираясь на [12], отображения для декартового
произведения двух унарных отношений выглядят следующим образом:
Р1 × Р2 ↔ id(C) ○ 𝕌 ○ id(D).
8.2. Произведение унарного и бинарного отношений. Произведение унарного и бинарного отношений
дает трехарное отношение, которое необходимо спроецировать на один или два атрибута, чтобы получить
допустимое результирующее отношение. Рассмотрим возможные варианты проекции.
a) πF(Р1(F) × Q1(K,L)) = πFР1(F) ↔ C;
b) πK(Р1(F) × Q1(K,L)) = πKQ1(K,L) ↔ ∃R.⊤;
c) πL(Р1(F) × Q1(K,L)) = πLQ1 (K,L) ↔ ∃R¯.⊤;
d) πK,L(Р1(F) × Q1(K,L)) = πK,LQ1 (K,L)) ↔ R;
e) πF,K(Р1(F) × Q1(K,L)) = Р1(F) × πK Q1(K,L) ↔ id(C) ○ 𝕌 ○ id(∃R.⊤);
f) πF,L(Р1(F) × Q1(K,L)) = Р1(F) × πLQ1(K,L) ↔ id(C) ○ 𝕌 ○ id(∃R¯.⊤).
8.3. Произведение двух бинарных отношений. Произведение двух бинарных отношений дает
четырехарное отношение, которое, как и в предыдущем случае, необходимо спроецировать на один или два
атрибута, чтобы получить допустимое результирующее отношение. Отметим, что данное отображение
Моделі та засоби систем баз даних і знань
224
следующим образом сводится к предыдущему:
a) проекция на один атрибут сводится к вариантам 8.2.b) или 8.2.c), например:
πN(Q1(K,L) × Q2(M,N)) = πNQ1(M,N) ↔ ∃S¯.⊤;
b) проекция на два атрибута, оба из которых принадлежат одному отношению, сводится к варианту
8.2.d), например:
πM,N(Q1(K,L) × Q2(M,N)) = πM,NQ2(M,N) ↔ S;
c) проекция на два атрибута, которые принадлежат разным отношениям, сводится к вариантам 8.2.e) или
8.2.f) , например:
πL,M(Q1(K,L) × Q2(M,N)) = πLQ1(K,L) × πM Q2(M,N)) ↔ id(∃R¯.⊤) ○ 𝕌 ○ id(∃S.⊤).
Отображение операций RA2, которые отсутствуют в RA
1. Инверсное деление
В работе [3] было показано, что операция инверсного деления выражается через совокупность операций
классической реляционной алгебры. Основываясь на результатах этой работы, механизмы отображения для
операции инверсного деления будут выглядеть следующим образом:
Q1(K,L)[L/F]Р1(F) = πK(Q1) – πK(Q1 ⋂ (πK(Q1) × (πL(Q1) – Р1))) ↔
∃R.⊤ – ∃ (R ⊓ (id(∃R. ⊤) ○ 𝕌 ○ id(∃R¯.⊤ – C))).
2. Номинал
В дескриптивных логиках номинал – это конструктор концепта, который строит концепт из индивида.
Если d есть имя индивида, то {d} есть концепт. В нашу RA2 эта операция введена для поддержания
конструктора номинала. Поэтому, её отображение не представляет особых проблем.
Отображение операции номинала выглядит следующим образом:
{d} ↔ {d}.
3. Транзитивное замыкание
Эта операция также была включена в RA2 для поддержания соответствующего конструктора DL.
Поэтому её отображение сходно с отображением операции номинала.
Отображение операции транзитивного замыкания выглядит следующим образом:
Q1
+ ↔ R+.
Выводы
Основная цель данной работы – установление отображений между дескриптивной логикой и
реляционной моделью данных. Приведено краткое описание бинарной реляционной модели данных, бинарной
реляционной структуры данных, бинарной реляционной алгебры. Рассматриваются механизмы отображения
бинарной реляционной модели данных с равенством в дескриптивную логику ALC и её расширения.
Литература
1. Андон Ф.И., Резниченко В.А., Чистякова И.С. Отображение дескриптивной логики в реляционную модель данных. Кибернетика и
системный анализ. 2017. № 6. C. 160–175.
2. Чистякова И.С. Онтолого-ориентированная интеграция данных в семантическом вебе. Проблеми програмування. 2014. № 2–3.
С. 188–196.
3. Резниченко В.А., Чистякова И.С. Отображение дескриптивной логики ALC в бинарную реляционную структуру данных. Проблеми
програмування. 2015. № 4. С. 13–30.
4. Резниченко В.А., Чистякова И.С. Интеграция семейства расширенных дескриптивных логик с реляционной моделью данных.
Проблеми програмування. 2016. № 2–3. С. 38–47.
5. Чистякова И.С. Интеграция логик с операциями над ролями с реляционной моделью данных. Проблеми програмування. 2016. № 4.
С. 58–65.
6. Чистякова И.С. Интеграция аксиоматики дескриптивных логик с реляционной моделью данных. Проблеми програмування. 2017. № 1.
С. 51–58.
7. Резниченко В.А., Чистякова И.С. Бинарная реляционная модель данных. Проблеми програмування. 2017. № 2. C. 96–105.
8. CODD E.F. Extending the database relational model to capture more meaning. ACM Transactions on Database Systems (TODS). 1979. Vol. 4,
Моделі та засоби систем баз даних і знань
225
Issue 4. P. 397–434.
9. Ziegler P., Dittrich K.R. Data Integration – Problems, Approaches, and Perspectives. Conceptual Modelling in Information Systems Engineering.
2007. P. 39–58.
10. Richard Barker. “Case*Method: Entity Relationship Modelling”. Addison-Wesley. 1990. 240 p.
11. Пасічник В.В., Резніченко В.А. Організація баз даних та знань. К.: Видавнича група BHV, 2006. 384 с.
12. Золин Е.Е. «Дескрипционная логика (годовой спецкурс)» [Электронный ресурс]. URL:http://lpcs.math.msu.su/~zolin/dl/ (дата звернення
01.03.2018).
References
1. Andon, F.I., Reznichenko, V.A., Chystiakova, I.S. (2017) Mapping of description logic to the relational data model. New tools of cybernetics,
informatics, computer engineering, and systems analysis. 53(6). P. 963–977.
2. Chystiakova, I.S. (2014) Ontology-oriented data integration on the Semantic Web (Онтолого-ориентированная интеграция данных в
семантическом вебе). Problems in programming. 2-3. P. 188–196.
3. Reznichenko, V.A. & Chystiakova, I.S. (2015) Mapping of the Description Logics ALC into the Binary Relational Data Structure
(Отображение дескриптивной логики ALC в бинарную реляционную структуру данных). Problems in programming. 4. P. 13–30.
4. Reznichenko, V.A. & Chystiakova, I.S. (2016) Integration of the family of extended description logics to the relational data model (Интеграция
семейства расширенных дескриптивных логик с реляционной моделью данных) Problems in programming. 2-3. P. 38–47.
5. Chystiakova, I.S. (2016) Integration of the description logics with role extensions to the relational data model (Интеграция логик с
операциями над ролями с реляционной моделью данных). Problems in programming. 4. P. 58–65.
6. Chystiakova, I.S. (2017) Integration of the description logics axiomatic into relational data model (Интеграция аксиоматики дескриптивных
логик с реляционной моделью данных). Problems in programming. 1. P. 51–58.
7. Reznichenko, V.A. & Chystiakova, I.S. (2017) Binary relational data model (Бинарная реляционная модель данных). Problems in
programming. 2. P. 96–105.
8. CODD, E.F. (1979) Extending the database relational model to capture more meaning. ACM Transactions on Database Systems (TODS). 4(4).
P. 397–434.
9. Ziegler, P. & Dittrich, K.R. (2007) Data Integration – Problems, Approaches, and Perspectives. Conceptual Modelling in Information Systems
Engineering. P. 39–58.
10. Barker, R. (1990) Case*Method: Entity Relationship Modelling. Addison-Wesley. 240 p.
11. Pasichnyk, V.V. & Reznichenko, V.A. (2006) Database and Knowledge Base Organization (Організація баз даних та знань). BHV. 384 p.
12. Zolin, E.E. (2017) Description logic (one year special course) (Дескрипционная логика (годовой спецкурс)) [Online].Available from:
:http://lpcs.math.msu.su/~zolin/dl/
Об авторе:
Чистякова Инна Сергеевна,
младший научный сотрудник Института программных систем НАН Украины.
Количество научных публикаций в украинских изданиях – 10.
Количество научных публикаций в зарубежных изданиях – 1.
orcid.org/0000-0001-7946-3611.
Место работы автора:
Институт программных систем НАН Украины.
03187, г. Киев, проспект Академика Глушкова, 40.
Тел.: +38(066) 847 7784.
E-mail: inna_islyamova@ukr.net.
|