Бинарная реляционная модель данных

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2017
Автори:	Чистякова, И.С., Резниченко, В.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут програмних систем НАН України 2017
Назва видання:	Проблеми програмування
Теми:	Моделі та засоби систем баз даних і знань
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/144479
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Бинарная реляционная модель данных / И.С. Чистякова, В.А. Резниченко // Проблеми програмування. — 2017. — № 2. — С. 96-105. — Бібліогр.: 10 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-144479
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1444792025-02-09T14:56:04Z Бинарная реляционная модель данных Бінарна реляційна модель даних Binary Relational Data Model Чистякова, И.С. Резниченко, В.А. Моделі та засоби систем баз даних і знань Работа является продолжением исследований, посвященных описанию отображений между дескриптивной логикой и реляционной моделью данных. В работе дано определение бинарной реляционной модели данных, а именно, ее структуры и алгебры. В публикации также рассматривается способ преобразования n-арной реляционной структуры данных в бинарную. В работе используются полученные ранее результаты исследований, а именно структура данных RM2, отображения базовых концептов, аксиоматики и ряда расширении дескриптивной логики ALC в RDM. Робота має відношення до проблеми інтеграції даних у семантичному вебі і є продовженням досліджень, що присвячені опису відображень між дескриптивною логікою (ДЛ) та реляційною моделлю даних. В зв’язку з тим, що ДЛ інтерпретується унарними та бінарними відношеннями, в роботі дано визначення бінарної реляційної моделі даних, а саме – її структури та алгебри. Ця алгебра містить операції класичної реляційної алгебри, які не збільшують арність відношень, модифіковані операції класичної реляційної алгебри, які збільшують арність, та ряд додаткових операцій, які дозволяють інтерпретувати деякі конструктори концептів та ролей ДЛ. В публікації також розглядається спосіб перетворення n-арної реляційної структури в бінарну. У роботі використовуються, попередньо отримані, результати досліджень, а саме – структура даних RM2, відображення базових концептів, аксіоматики та ряду розширень дескриптивної логіки ALC в реляційну модель даних. The paper is related to the problem of data integration in the Semantic Web and is a continuation of the previously published works, which was dedicated to the creation of mappings from the description logic (DL) into binary relational data model. In this paper, we define the binary relational data model, namely, its structure and algebra. This algebra contains classical relational algebra operations that do not increase arity of relations, modified classical relational algebra operations that increase arity, and a number of additional operations that allow interpreting certain concepts and roles of DL. The publication also discusses how to convert the n-ary relational data structure into a binary one. In this paper, the previously obtained research results are used, namely RM2 data structure and mapping of basic concepts, roles, axioms of DL ALC and its extensions into the relational data model. 2017 Article Бинарная реляционная модель данных / И.С. Чистякова, В.А. Резниченко // Проблеми програмування. — 2017. — № 2. — С. 96-105. — Бібліогр.: 10 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/144479 004.62 ru Проблеми програмування application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Моделі та засоби систем баз даних і знань Моделі та засоби систем баз даних і знань
spellingShingle	Моделі та засоби систем баз даних і знань Моделі та засоби систем баз даних і знань Чистякова, И.С. Резниченко, В.А. Бинарная реляционная модель данных Проблеми програмування
description	Работа является продолжением исследований, посвященных описанию отображений между дескриптивной логикой и реляционной моделью данных. В работе дано определение бинарной реляционной модели данных, а именно, ее структуры и алгебры. В публикации также рассматривается способ преобразования n-арной реляционной структуры данных в бинарную. В работе используются полученные ранее результаты исследований, а именно структура данных RM2, отображения базовых концептов, аксиоматики и ряда расширении дескриптивной логики ALC в RDM.
format	Article
author	Чистякова, И.С. Резниченко, В.А.
author_facet	Чистякова, И.С. Резниченко, В.А.
author_sort	Чистякова, И.С.
title	Бинарная реляционная модель данных
title_short	Бинарная реляционная модель данных
title_full	Бинарная реляционная модель данных
title_fullStr	Бинарная реляционная модель данных
title_full_unstemmed	Бинарная реляционная модель данных
title_sort	бинарная реляционная модель данных
publisher	Інститут програмних систем НАН України
publishDate	2017
topic_facet	Моделі та засоби систем баз даних і знань
url	https://nasplib.isofts.kiev.ua/handle/123456789/144479
citation_txt	Бинарная реляционная модель данных / И.С. Чистякова, В.А. Резниченко // Проблеми програмування. — 2017. — № 2. — С. 96-105. — Бібліогр.: 10 назв. — рос.
series	Проблеми програмування
work_keys_str_mv	AT čistâkovais binarnaârelâcionnaâmodelʹdannyh AT rezničenkova binarnaârelâcionnaâmodelʹdannyh AT čistâkovais bínarnarelâcíjnamodelʹdanih AT rezničenkova bínarnarelâcíjnamodelʹdanih AT čistâkovais binaryrelationaldatamodel AT rezničenkova binaryrelationaldatamodel
first_indexed	2025-11-27T01:37:32Z
last_indexed	2025-11-27T01:37:32Z
_version_	1849905595463761920
fulltext	Моделі та засоби систем баз даних і знань © И.С. Чистякова, В.А. Резниченко, 2017 96 ISSN 1727-4907. Проблеми програмування. 2017. № 2 УДК 004.62 И.С. Чистякова, В.А. Резниченко БИНАРНАЯ РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ Работа является продолжением исследований, посвященных описанию отображений между дескриптивной логикой и реляционной моделью данных. В работе дано определение бинарной реляционной модели данных, а именно, ее структуры и алгебры. В публикации также рассматривается способ преобразования n-арной реляционной структуры данных в бинарную. В работе используются полученные ранее результаты исследований, а именно структура данных RM2, отображения базовых концептов, аксиоматики и ряда расширении дескриптивной логики ALC в RDM. Ключевые слова: бинарная реляционная модель данных, бинарная реляционная структура данных, дескриптивная логика, отображение данных, ALC, RDM, RM2. Введение Ежедневный экспоненциальный рост информации на планете продуцирует ряд проблем, связанных с использованием данных в различных информационных си- стемах (ИС). Среди них можно выделить такие. 1. Различные модели организа- ции данных (реляционные, иерархиче- ские, сетевые модели данных, онтологии и т.д.). Такое многообразие способов опери- рования информацией приводит к рассо- гласованию доступа одновременно ко всем источникам информации. 2. Различные физические спосо- бы хранения данных. Следствием этого является отсутствие единого механизма доступа к содержимому для конечного пользователя. 3. Распределенность данных. Источники изолированы друг от друга, каждый из которых подчиняется концеп- ции замкнутого мира. Это создает трудно- сти для введения концептуально новых понятий предметной области (ПО), дубли- рованию данных, одновременному увели- чению объема и уменьшению релевантно- сти искомой информации. 4. Неполнота и противоречи- вость данных. Обуславливается, прежде всего, отсутствием семантической состав- ляющей их описания. 5. Различные способы опериро- вания данными. Каждая модель данных предполагает существование своих соб- ственных средств манипулирования, что порождает их разнообразие, приводящее к гетерогенности данных. Все эти проблемы можно устранить путем интеграции данных, о чем подробно изложено в [1]. Интеграция данных включает объединение данных, находящихся в раз- личных источниках и предоставление дан- ных пользователям в унифицированном виде. Этот процесс становится существен- ным как в коммерческих задачах (когда двум похожим компаниям необходимо объединить их базы данных), так и в науч- ных (комбинирование результатов иссле- дований, расположенных в различных ин- формационных репозиториях) [2]. Интеграция множественных ИС, как правило, ставит своей целью комбини- рование выбранных систем таким образом, чтобы они сформировали унифицирован- ное новое целое и дали пользователю ил- люзию взаимодействия с единственной ИС. Пользователь обеспечен однородным логическим представлением данных, кото- рые физически распределены в гетероген- ных источниках данных. В целом, информационные системы не спроектированы для интеграции. Таким образом, всякий раз, когда необходимо осуществить интегрированный доступ к различным исходным системам, источники и их данные не подходят друг к другу, и должны быть соединены и функционально согласованы [3]. Поскольку целью инте- грации всегда является обеспечение гомо- генного унифицированного представления Моделі та засоби систем баз даних і знань 97 данных различных источников, конкретная задача интеграции зависит от следующих составляющих [3]:  архитектура ИС;  содержание и функциональ- ность компонентов системы;  типы данных (буквенно- цифровые, мультимедиа, структурирован- ные, полу структурированные, неструкту- рированные данные);  требования, связанные с авто- номностью компонентов системы;  предполагаемое использование интегрированной ИС;  требования эффективности;  доступные ресурсы (время, деньги, люди, ноу-хау и т. д.). Ввиду всего вышесказанного, ста- новится очевидной важность решения комплексной проблемы интеграции дан- ных. Проблема интеграции данных за- ключается в таком логическом объеди- нении данных, принадлежащих разнород- ным источникам, которое обеспечивает единое представление и оперирование этими данными. Система интеграции дан- ных позволяет освободить пользователя от необходимости самостоятельно отбирать источники, в которых находится интере- сующая пользователя информация, обра- щаться к каждому источнику по отдельно- сти и вручную сопоставлять и объединять данные из различных источников [1]. На сегодняшний день было выделе- но три составляющих комплексной про- блемы интеграции данных:  выработка схем интеграции данных;  выработка отображений между моделями;  выработка способов манипули- рования. В ряде работ [4–7] был описан ал- горитм отображения дескриптивной логи- ки в бинарную реляционную структуру данных, однако сама бинарная реляцион- ная модель не была определена. В данной статье мы определим бинарную реляцион- ную модель. Тем более как научный, так и практический интерес представляет опи- сание отображения бинарной реляционной модели в дескриптивную логику (ДЛ). Статья организована следующим образом. После введения, в разделе 1 да- ются основные определения, а именно – бинарной реляционной модели данных, бинарной реляционной структуры дан- ных, бинарной реляционной алгебры и ограничений целостности. Здесь будут введены основные обозначения. Раздел 2 посвящен бинарной реляционной алгебре. Раздел 3 рассматривает преобразование n-арной реляционной структуры в бинар- ную. Завершают текущую публикацию основные выводы и дальнейшие планы исследований. Определение RM2 и её составляющих Дадим определение бинарной реля- ционной модели данных. Бинарная реляционная модель данных (RM2) – это совокупность бинар- ной реляционной структуры данных, би- нарной реляционной алгебры и ограниче- ний целостности. Как видно из определения, бинар- ная реляционная модель данных включает в себя следующие компоненты: 1) структурный аспект, представ- ленный бинарной реляционной структурой данных, в которой данные представлены в виде совокупности отношений; 2) аспект манипулирования, пред- ставленный бинарной реляционной алгеб- рой, которая включает в себя операторы манипулирования отношениями; 3) аспект целостности, представ- ленный ограничениями целостности, кото- рым отвечают отношения бинарной реля- ционной структуры данных. Рассмотрим каждый из аспектов в отдельности. Бинарная реляционная структура данных – это совокупность отношений арности не более 2. Так как в рамках данной статьи мы говорим только о реляционных отношени- Моделі та засоби систем баз даних і знань 98 ях, то для краткости будем использовать термин «отношение». Напомним его опре- деление [8]. Реляционное отношение – это пара ( SR , ER ), где SR – схема (интенсионал) отношения, а ER – экземпляр (экстенсио- нал) отношения. Схема отношения RS – это выра- жение вида R( 1A : 1D [, 2A : 2D ]), где R – имя отношения, 1A , 2A – имена атрибутов отношения, 1D , 2D – имена доменов отношения, определяющих обла- сти допустимых значений атрибутов (на одном домене может быть определено множество атрибутов). Примечание: квадратные скобки в определении схемы отношения указывают на факультативность заключенной в них конструкции. Если указание имен доменов не су- щественно, то схема записывается так R( 1A [, 2A ]). Имена доменов являются уникаль- ными в реляционной структуре. Имена отношений являются уникальными в ре- ляционной структуре. Имена атрибутов являются уникальными в схеме отноше- ния, но могут повторяться в различных схемах. Экземпляр отношения RE это подмножество:  либо домена, на котором опре- делен атрибут унарного отношения ER ⊆ 1D ;  либо декартового произведения доменов, на которых определены два ат- рибута бинарного отношения: ER ⊆ 1D  2D . В RM2, как и в классической реля- ционной модели, множество значений i-го столбца экземпляра отношения представ- ляет собой множество значений i-го атри- бута в схеме отношения. Бинарная реляционная алгебра (RA2) – это совокупность операций, опре- деленных на бинарных отношениях. Она является замкнутой в том смысле, что результат выполнения любой операции также является отношением. Можно выделить три вида операций:  операции, которые не увеличи- вают арность результирующего отноше- ния. Они являются полными аналогами операций классической реляционной ал- гебры (RA);  операции, увеличивающие ар- ность результирующего отношения. Они имеют свои аналоги в RA. Учитывая это, в бинарной реляционной алгебре вводятся их модификации, результирующие отно- шения которых не превышают арности 2;  операции, являющиеся новыми по отношению к RA. Все три типа операций RA2 по- дробнее будут рассмотрены в следующем разделе. Целостность данных – (в класси- ческой реляционной модели данных) это механизм поддержания соответствия структуры данных предметной области. Ограничения целостности – это правила, налагающие некоторые ограни- чения на возможное состояние структуры данных. В бинарной реляционной модели данных, аналогично классической RM, определены два базовых требования обес- печения целостности:  целостность сущностей;  целостность связей. Целостность сущностей заключа- ется в том, что каждый экземпляр отноше- ния должен отличаться от любого другого, т. е. любое отношение должно обладать первичным ключом (PK). В RM2 каждый элемент унарного отношения и каждая пара бинарного от- ношения представляют собой PK. Атрибуты, представляющие собой копии ключей родительских отношений, называются внешними ключами (FK). Моделі та засоби систем баз даних і знань 99 Целостность связей заключается в том, что для каждого значения внешнего ключа, появляющегося в дочернем отно- шении, в родительском отношении должен найтись кортеж с таким же значением пер- вичного ключа. Как правило, поддержание целост- ности сущностей и связей обеспечивается средствами системы управления базой данных (СУБД). Описание операций бинарной реляционной алгебры RA2 В предыдущем разделе были опре- делены три вида операций бинарной ре- ляционной алгебры. Рассмотрим их по порядку. Операции, унаследованные из RA К первому виду операций, которые не увеличивают арность результирующего отношения, относятся:  именование;  объединение;  пересечение;  разность;  проекция;  селекция;  деление. Ко второму виду относятся опера- ции декартово произведение и соединение. Как уже было сказано, все эти опе- рации унаследованы из RA, а для декарто- ва произведения и соединения приводятся соответствующие модификации, результи- рующие отношения которых не превыша- ют арности 2. Рассмотрим каждую в отдельности. 1. Именование/переименование (ρ). Результатом применения операции пе- реименования атрибутов является отноше- ние с изменёнными именами атрибутов. Как правило, схема результирующего от- ношения выражения реляционной алгебры не может быть выведена из схем исходных отношений. Оператор именования позво- ляет такую схему задать. Было предложено множество различных вариантов этого оператора. Мы будем использовать следу- ющие три:  ρR(E) – отношению, полу- ченному в результате вычисления выраже- ния Е RA2, присваивается имя R;  ρR(A1[, A2])(E) – отношению, полученному в результате вычисления вы- ражения Е RA2, присваивается схема R(A1 [, A2]);  ρA/B(E) – в отношении, полу- ченном в результате вычисления выраже- ния Е RA2, атрибут А переименовывается в атрибут В. Определение 1. Два отношения со схемами 1R ( 1A [, A2]) и R2(B1 [, B2]) явля- ются совместимыми (по объединению), если имеют одинаковую арность, пары ат- рибутов ( iA , iB ), i=1, 2 определены на од- ном и том же домене. Над совместимыми отношениями определяются следующие три множе- ственные операции. 2. Объединение (⋃). Объединение двух совместимых отношений – это отно- шение, экземпляр которого является объ- единением экземпляров исходных отно- шений: 21 RR  = {r \| r  1R  r  2R }. 3. Пересечение (⋂). Пересечение двух совместимых отношений – это от- ношение, экземпляр которого является пересечением экземпляров исходных от- ношений: 1R ⋂ 2R = {r \| r  1R ∧ r  2R }. 4. Разность (−). Разностью двух совместимых отношений является отно- шение, экземпляр которого содержит все кортежи первого отношения, которых нет среди кортежей второго отношения: 1R − 2R = {r \| r  1R ∧ r  2R }. Схемы результирующих отношений всех трех операций определяются опера- цией именования. 5. Проекция (π). Пусть задано бинарное отношение со схемой R(A,B). Проекцией R на А (или на В), обозна- чаемой πА(R), (πВ(R)), называется отно- шение, экземпляр которого содержит Моделі та засоби систем баз даних і знань 100 только А-компоненты (В-компоненты) кортежей отношения R: πА(R)={r[A] \| r  R}, πB(R)={r[B] \| r  R }. Здесь запись r[A] (r[B]) обозначает выделение из кортежа r компоненты, при- надлежащей значению атрибута А (В). Схема результирующего отношения наследует имя атрибута А (В), а имя от- ношения определяется операцией имено- вания. Определение 2. Пусть  – любой из следующих предикатов сравнения: , ,  , , . Атрибуты А и В одного и того же или различных отношений называются -сравнимыми, если для любых пар значе- ний а  А и b  B определено выражение а  b. Наборы атрибутов М = (A1, A2) и N = (B1, B2) называются -сравнимыми, если пары атрибутов ( iA , iB ) являются -сравнимыми. В этом случае M  N под- разумевает следующее: M  N = A1  B1 ∧ A2  В2. 6. Селекция (σ). Пусть М и 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. Пусть задано от- ношение R(А, B). Образом кортежа rA  πA(R), записываемым как IrA(R), называется такое множество кортежей rB  πB(R), соединение которых с rA при- надлежит R: IrA(R) = {rB \| rB  πB(R) ∧ (rA,rB)  R}. 7. Деление (). Пусть заданы отно- шения 1R (A, B) и 2R (C, D), причем B и C – сравнимы по предикату равенства. Деле- нием 1R на 2R по B и C, обозначаемым 1R [B÷C)]R2, называется отношение, кото- рое состоит из таких кортежей rA  πA( 1R ), образы которых IrA( 1R ) со- держат все кортежи проекции πC(R2): 1R [B÷C] 2R = {rA \| rA  πA( 1R ) ∧ IrA ( 1R ) ⊇ πC( 2R )}. Отношение 2R может быть унар- ным. Если, например, 2R (C), то: 1R [B÷C] 2R = {rA \| rA \| πA( 1R ) ∧ IrA ( 1R ) ⊇ 2R }. Схема результирующего отношения наследует имя атрибута A из 1R , а имя от- ношения определяется операцией имено- вания. Деление следующим образом вы- ражается через произведение и разность: 1R [B÷C]R2 = πA( 1R ) − πA ((πA( 1R ) × × πC(R2)) − 1R ). 8. (Декартово) произведение (). (Декартовым) произведением унарных от- ношений 1R и 2R , обозначаемым 1R 2R , называется бинарное отношение, экземпляр содержащего все возможные соединения (конкатенации) кортежей от- ношений 1R и 2R : 1R  2R = {(r1,r2) \| r1  1R ∧ r2  2R }. Схема результирующего отношения наследует имена атрибутов отношений 1R и 2R , а имя отношения определяется опе- рацией именования. Произведение двух бинарных или бинарного и унарного от- ношений не допускаются в RM2. Моделі та засоби систем баз даних і знань 101 9. Соединение (⋈). В RM данная операция увеличивает арность результата. Учитывая это, в RM2 предлагается моди- фицированный вариант соединения, суть которого заключается в том, что если ре- зультирующее отношение оказывается ар- ности выше двух, то к нему применяется проекция по одному или двум столбцам. Пусть 1R (B) и 2R (C) – унарные отношения, где В и С – -сравнимые атри- буты. Определение 4. Соединение отно- шения 1R с отношением 2R по условию B  C, обозначаемое 1R ⋈BC 2R , определя- ется следующим образом: 1R ⋈BC 2R = {(r1,r2) \| r1  1R ∧ r2  2R ∧ ∧ r1[B]  r2[C]}. Определение 5. Пусть один или оба отношения имеют арность 2, тогда соеди- нение определяется следующим образом. Пусть Аi, Аj – любые два атрибута из мно- жества атрибутов исходных отношений. Пусть также 1R содержит атрибут mA , а 2R – nA , которые являются - сравнимыми, тогда соединение 1R и 2R по условию nm AA  , обозначаемое 1R ⋈ ik ji AA AA  ],[ 2R , определяется следующим образом: 1R ⋈ ik ji AA AA  ],[ R2 = π[Аi,Аj]( 1R ⋈ АmАn 2R ). Схема результирующего отношения наследует имена атрибутов отношений 1R и 2R , а имя отношения определяется опе- рацией именования. Операции, вводимые только в RA2 Определим еще несколько опера- ций, которых нет в RA. 10. Инверсное деление (/). Пусть заданы отношения R1(A, B) и 2R (C, D), причем B и C – сравнимы по предикату равенства. Инверсным делением 1R на 2R по B и C, обозначаемым 1R [B/C)] 2R , называется отношение, состоящее из таких кортежей rA  πA( 1R ), образы которых IrA( 1R ) содержатся среди кортежей проек- ции πC( 2R ): 1R [B/C] 2R = {rA \| rA  πA( 1R ) ∧ IrA ( 1R ) ⊆ πC( 2R )}. Отличие инверсного деления от обычного заключается в том, что в первом случае образы содержатся во втором опе- ранде, а во втором случае – содержат вто- рой операнд. В работе [4] доказано, что инверсное деление следующим образом выражается через уже определенные опе- раторы: 1R [B/C] 2R = πA( 1R ) – πA( 1R ⋂ πA( 1R )   (πB( 1R ) – πC( 2R )). 11. Номинал ({}). Суть этой опера- ции – построение унарного или бинарного отношения из заданной константы или па- ры констант. В RA такой операции нет, так как эта алгебра вообще не включает во- просы создания отношений. Мы включили эту операцию для поддержания одноимен- ного конструктора в DL. Кроме того, эта операция не выходит за рамки реализации реляционной модели, так как все реляци- онные СУБД предоставляют такую воз- можность. Пусть заданы константы a и b. То- гда выражения {а} и {(а, b)} называются номиналами и означают построение унар- ного (бинарного) отношения, содержащего единственный кортеж – а или (а, b). Схема такого отношения не определена и задает- ся операцией именования. В работе [5] были рассмотрены отображения для операций транзитивно- го замыкания(+) и рефлексивно-транзи- тивного замыкания (), расширяющих стандартный синтаксис логики DL ALC. В ней было сказано, что операция транзи- тивного замыкания отображается путем выполнения от 1 до n операций компо- зиций над отображением роли, а операция рефлексивно-транзитивного замыкания отображается путем выполнения от 0 до n операций композиций над отображением роли. Моделі та засоби систем баз даних і знань 102 В реляционной алгебре таких операций нет, поэтому в чистой RA они невыразимы. Однако, эта проблема решена в реляционных СУБД, поддерживающих рекурсивный SQL, где есть возможность применить транзитивное замыкание. Подробнее об этом можно познакомиться в работе [9]. Учитывая это мы вводим в бинарную реляционную модель данных аналогичную операцию транзитивного замыкания/. 12. Транзитивное замыкание (+). Пусть задано бинарное отношение со схемой R(A, B). Обозначим операцию транзитивного замыкания отношения R+. Она определяется следующим образом: R = {r \| ∀ r1∀ r2  R (r1 = (a1,b1) ∧ r2 = = (a2,b2) ∧ b1=a2 → r = (a1,b2)  r}. Рефлексивно-транзитивное замыка- ние следующим образом выражается через операции проекции, соединения, транзи- тивного замыкания и объединения. ((πAR(A, B))⋈А=A(πAR(A, B))) ⋃ R+. Преобразование n-арной реляционной структуры в бинарную Поскольку классическая RM не ограничивается лишь унарными и бинар- ными отношениями, то необходимо рас- смотреть, что собой представляют в RM2 n-арные связи, присутствующие в RM. Суть предлагаемого варианта такого пре- образования заключается в следующем. Во-первых, такое преобразование должно быть эквивалентным по данным. Подразумевается следующее. Совокуп- ность отношений 1R , 2R , …, kR является эквивалентной по данным отношению R, если R равно их естественному соедине- нию: R = 1R 2R … kR . Во-вторых, согласно теореме Хита [10], если в отношении R(A,B,C), где A,B,C в общем случае могут быть набо- рами атрибутов, существует функцио- нальная зависимость A→B, то R = = R[A,B]* R[A,C]. В результате, если атрибут 1A от- ношения R( 1A , 2A , …, nA ) является воз- можным ключом, т. е. он функционально определяет все остальные атрибуты, то R декомпозируемо на следующую совокуп- ность бинарных отношений: R[ 1A , 2A ], R[ 1A , 3A ],…,R[ 1A , nA ], причем R= R[ 1A , 2A ] R[ 1A , 3A ] …* R[ 1A , nA ]. То есть такая декомпозиция является экви- валентной по данным. Таким образом, если в отношении существует простой (не составной) воз- можный ключ, то приведенные выше рас- суждения показывают, как можно произ- водить декомпозицию n-арных отноше- ний в совокупность бинарных. Однако, возможные ключи не обя- зательно являются простыми, поэтому в общем случае этот подход не приводит к созданию только бинарных отношений. Учитывая это мы воспользуемся идеей атрибутов-заменителей (surrogate), кото- рую высказал родоначальник реляцион- ной модели Э.Ф. Кодд в [8], посвященной расширению семантики реляционной мо- дели. Идея заключается в том, что в каж- дом отношении вводится специальный атрибут, который не имеет ни какого от- ношения к моделируемой предметной об- ласти, а вводится только для того, чтобы искусственно уникально идентифициро- вать кортежи отношения, и прежде всего для того, чтобы на него ссылаться во внешних ключах. Такому атрибуту прида- ется статус первичного ключа, а действи- тельному первичному ключу отношения приписываются ограничения UNIQUE, NOT NULL. Идея атрибута-заменителя оказа- лась настолько плодотворной, что она была включена в SQL введением специ- ального объекта базы данных Sequence, который порождает последовательность чисел, используемых в качестве значений атрибута-заменителя. Таким образом, мы Моделі та засоби систем баз даних і знань 103 получаем простой первичный ключ, и проблема декомпозиции отношения на совокупность бинарных отношений реша- ется. Причем, такая декомпозиция, как мы уже отметили, является эквивалентной по данным. Однако она не является эквива- лентной по зависимостям. По крайней ме- ре, теряется информация о реальном пер- вичном ключе, в котором хранится струк- тура функциональных зависимостей нор- мализованного отношения. Решить этот вопрос можно введением бинарного от- ношения, которое содержит имя отноше- ния и список атрибутов, входящих в пер- вичный ключ этого отношения. Ключом этого отношения является эта пара атри- бутов. Аналогично предлагается посту- пить для сохранения информации о дру- гих возможных ограничениях целостно- сти отношения (UNIQUE, FOREIGN KEY). В итоге, сам факт того, на какие отношения декомпозировано исходное отношение, также представляется отдель- ным бинарным отношением. Покажем это на примере. Пусть заданы следующие два от- ношения:  R (A, B, C, D, E) со следую- щими ограничениями целостности: - A, B, C – первичный ключ, - D, E – уникальный ключ, - B, C – внешний ключ.  S (K, L, M, N, O) со следу- ющими ограничениями целостности: - K, L – первичный ключ, - M – уникальный ключ, - N,O – внешний ключ. Вводим в отношения столбцы- заменители Sur: R (Sur, A, B, C, D, E), S (Sur, K, L, M, N, O) и декомпозируем их на бинарные отноше- ния: R (Sur, A, B, C, D, E) → R1(Sur, A), R2(Sur, B), R3(Sur, C), R4(Sur, D), R5(Sur, E). S (Sur, K, L, M, N, O) → S1(Sur, K), S2(Sur, L), S3(Sur, M), S4(Sur, N), S5(Sur, O). Для сохранения информации о де- композиции создаем отношение Decomposition. Decomposition (SRelNm, DRelNm), где.  SrelNm – имя декомпозируемо- го отношения;  DrelNm – имя отношения- результата декомпозиции. Первичный ключ – оба атрибута. Для сохранения информации о пер- вичных ключах создаем отношение PrimaryKey. PrimaryKey (SRelNm, PrKeyNm), где  SRelNm – имя исходного отно- шения;  PrKeyNm – имя атрибута, вхо- дящего в состав первичного ключа. Первичный ключ – оба атрибута. Для сохранения информации о уни- кальных ключах создаем отношение UniqueKey. UniqueKey (SRelNm, UnKeyNm), где:  SRelNm – имя исходного отно- шения;  UnKeyNm – имя атрибута, вхо- дящего в состав уникального ключа. Первичный ключ – оба атрибута. Для сохранения информации о внешних ключах создаем отношение ForeignKey. ForeignKey (SRelNm, FrKeyNm), где.  SRelNm – имя исходного от- ношения;  FrKeyNm – имя атрибута, входящего в состав внешнего ключа. Первичный ключ – оба атрибута. Как выглядят эти отношения для нашего примера можно увидеть в таблице. Моделі та засоби систем баз даних і знань 104 Таблица Decomposition PrimaryKey UniqueKey ForeignKey SRelNm DRelNm SRelNm PrKeyNm SRelNm UnKeyNm SRelNm FrKeyNm R R1 R A R D R B R R2 R B R E R C R R3 R C S M S N R R4 S K S O R R5 S L S S1 S S2 S S3 S S4 S S5 Выводы В данной публикации мы дали определение и развернутое описание би- нарной реляционной модели данных. Оно охватывает определение бинарной реляци- онной структуры данных, бинарной реля- ционной алгебры и её операций, а также ограничений целостности. Помимо этого, в статье рассматривается вариант преобра- зования n-арных отношений в бинарные. Основная цель полученных результатов заключается в том, чтобы можно было установить отображение между дескрип- тивной логикой и реляционной моделью данных. Среди открытых вопросов остают- ся:  отображение операций RA в конструкторы дескриптивной логики;  представление операций RA для n-арных отношенй в RA2;  отображение n-арных расшире- ний дескриптивной логики в RM2. 1. Чистякова И.С. Онтолого-ориентирован- ная интеграция данных в семантическом вебе. Проблеми програмування. 2014. № 2–3. С. 188–196. 2. Серебряков В.А. (2012) Семантическая интеграция данных [Электронный ресурс]. Режим доступа: http://sp.cmc.msu.ru/ proseminar/2012/serebryakov.2012.04.20.pdf, свободный. Загл. с экрана. Яз. рус. 3. Ziegler P., Dittrich K.R. Data Integration – Problems, Approaches, and Perspectives. Conceptual Modelling in Information Systems Engineering. 2007. P. 39–58. 4. Резниченко В.А., Чистякова И.С. Отобра- жение дескриптивной логики ALC в бинарную реляционную структуру данных. Проблеми програмування. 2015. № 4. C. 13–30. 5. Резниченко В.А., Чистякова И.С. Интегра- ция семейства расширенных дескриптив- ных логик с реляционной моделью данных. Проблеми програмування. 2016. № 2-3. C. 38–47. 6. Чистякова И.С. Интеграция логик с операциями над ролями с реляционной моделью данных. Проблеми програму- вання. 2016. № 4. С. 58–65. 7. Чистякова И.С. Интеграция аксиоматики дескриптивных логик с реляционной моделью данных. Проблеми програму- вання. 2017. № 1. С. 51 – 58. 8. Codd E.F. Extending the database relational model to capture more meaning. ACM Transactions on Database Systems (TODS). 1979. № 4(4). P. 397–434. 9. Резниченко В.А. Рекурсивный SQL. Інженерія програмного забезпечення. 2010. Т. 4, № 4. С. 63–81. 10. Heath I.J. (1971) Unacceptable file operations in a relational data base. SIGFIDET '71. 1971. P. 19–33. Моделі та засоби систем баз даних і знань 105 References 1. CHYSTIAKOVA I.S. (2014). Ontology- oriented data integration on the Semantic Web Problems in programming. N 2–3, P.188–196. 2. SEREBRYAKOV V.A. (2012). Semantic data integration. http://sp.cmc.msu.ru/proseminar /2012/serebryakov.2012.04.20.pdf. 3. ZIEGLEE P., DITTRICH K.R. Data Integration – Problems, Approaches, and Perspectives. In:Conceptual Modelling in Information Systems Engineering, P. 39–58. Springer, Heidelberg (2007). 4. REZNICHENKO V.A., CHYSTIAKOVA I.S. (2015). Mapping of the Description Logics ALC into the Binary Relational Data Structure. Problems in programming. N 4. P. 13–30. 5. REZNICHENKO V.A., CHYSTIAKOVA I.S. (2016). Integration of the family of extended description logics with relational data model. Problems in programming. N 2–3, P. 38–47. 6. CHYSTIAKOVA I.S. (2016). Integration of the description logics with extensions into relational data model. Problems in programming. N 4. P. 58–65. 7. CHYSTIAKOVA I.S. (2017). Integration of the description logics axiomatic into relational data model. Problems in programming. N 1. P. 51–58. 8. CODD E.F. Extending the database relational model to capture more meaning. ACM Transactions on Database Systems (TODS). Vol. 4, Issue 4, Dec. 1979. P. 397–434. 9. REZNICHENKO V.A (2010). Recursive SQL. Software Engineering. Vol. 4, N 4. P. 63–81. 10. HEATH I.J. (1971). "Unacceptable file operations in a relational data base". Proceedings of the 1971 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '71. P. 19–33. doi:10.1145/1734714.1734717 Получено 09.03.2017 Об авторах: Чистякова Инна Сергеевна, младший научный сотрудник. Количество научных публикаций в украинских изданиях – 8. orcid.org/0000-0001-7946-3611, Резниченко Валерий Анатольевич, кандидат физико-математических наук, старший научный сотрудник. Количество научных публикаций в украинских изданиях – 58. Количество научных публикаций в зарубежных изданиях – 3. orcid.org/0000-0002-4451-8931. Место работы авторов: Институт программных систем НАН Украины, 03187, г. Киев, проспект Академика Глушкова, 40. Тел.: +38(044)526 5139; +38(044)526 6249. E-mail: vreznichenko_47@mail.ru, inna_islyamova@ukr.net. http://sp.cmc.msu.ru/proseminar%20/2012/ http://sp.cmc.msu.ru/proseminar%20/2012/

Бинарная реляционная модель данных

Репозитарії

Схожі ресурси