Известия РАН. Теория и системы управления, 2019, № 2, стр. 58-74

АЛГЕБРАИЗАЦИЯ ВЫВОДА ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ

Л. А. Поморцев a*, В. И. Цурков a**

a МАИ (национальный исследовательский ун-т), ВЦ ФИЦ ИУ РАН
Москва, Россия

* E-mail: brickfactory.org@mail.ru
** E-mail: tsur@ccas.ru

Поступила в редакцию 01.11.2018
После доработки 12.11.2018
Принята к публикации 26.11.2018

Полный текст (PDF)

Аннотация

Рассматривается замкнутый автомат, располагающий шестью не более чем двухадресными командами, называемыми аксиомами вывода. Его назначением является преобразование так называемых функциональных зависимостей над произвольным конечным множеством R, именуемым схемой. В статье устанавливается возможность функционально эквивалентной замены алгоритмов вывода функциональных зависимостей алгебраическими выражениями с одной из бинарных алгебраических операций ▶ и ▹ с добавлением к ним очень простых нульарных и унарных операций (команд), составляющими в совокупности универсальную D-алгебру.

Введение. 1. Конструирование реляционных баз данных. Функциональные зависимости (ФЗ) – понятие, лежащее в основе вопросов, связанных с конструкцией таблиц, составляющих так называемые реляционные базы данных (РБД – RDB, Relational Databases), формализация которых началась с работ [1, 2]. ФЗ представляются упорядоченными парами подмножеств, состоящих из имен колонок (то же, что полей) таблиц, которые в научной литературе называются атрибутами данного отношения. В совокупности атрибуты составляют схему R, играющую в быту роль шапки таблицы. Содержательная часть таблицы является алгебраическим отношением [relation].

ФЗ формализуют семантические свойства таблицы, способные влиять на структуру РБД в соответствии с теоремой Хита [3; 4, § 3.6.2, с. 70], обеспечивающей декомпозицию таблиц без информационных потерь и избыточности. В совокупности с основополагающей в теории РБД (ТРБД) операцией ⋈ соединения таблиц декомпозиция Хита позволяет понимать РБД как единую таблицу с приданной ей совокупностью функциональных зависимостей, призванных разбить целое на требуемые части. Это означает, что ФЗ заключают в себе квинтэссенцию конструирования (проектирования) РБД, тем более что прочие ФЗ могут быть основой семантических правил заполнения таблиц.

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

1) синтез-анализ частично упорядоченных множеств,

2) перестройка порядков каскадно-упорядоченного множества,

3) гигиена последовательностей вывода,

4) чередующиеся последовательности вывода ФЗ,

5) алгебраический вывод функциональных зависимостей.

В первых двух задачах под упорядоченными множествами понимаются те же последовательности вывода ФЗ из заданного множества других ФЗ, но для применения к ним аппарата алгебры нет необходимости использовать терминологию теории РБД (ТРБД). Как видно, ПВ занимают основное место в списке задач, предстоящих для решения, а зависимости находятся на магистральном пути конструирования РБД, которое в свою очередь требует умения конструировать сами функциональные зависимости. Однако ПВ, как и всякое программное обеспечение, являются дорогим удовольствием. Альтернативой им являются алгебраические выражения в специально построенной ассоциативной алгебре, использующей в качестве аргументов те же ФЗ и дающие те же результаты. Они по сравнению с ПВ вербально однозначны, экономны и алгоритмически проще. Установка функциональной эквивалентности последовательностей вывода и соответствующих им алгебраических выражений достигается решением финальной задачи 5). Настоящая статья завершает исследования, начатые в [5, 6].

2. Информационная безопасность табличных данных. Совокупность $\mathbb{F}$ специально выделенных ФЗ способна накладывать ограничения на целостность (integrity constraints) данных (ЦД) таблиц в процессе эксплуатации РБД при условии включения в проект ПБД ∪ СУРБД (система управления РБД) информационных, включая $\mathbb{F}$, и вычислительных средств, обеспечивающих проверку неизменности $\mathbb{F}$ при каждом обновлении данных. Подобная проверка целесообразна также для обнаружения несанкционированного доступа (НСД) к РБД со стороны активных вредоносных программ. Таким образом, уже на этапе технического проектирования встает важный вопрос о корректной поддержке баз данных с помощью $\mathbb{F}$. Этот вопрос по сути является оптимизационным, поскольку в количественном отношении $\mathbb{F}$ должно быть одновременно необходимым (т.е. не большим) и достаточным (т.е. не малым) в целях обеспечения информационной безопасности. Вместе с тем на данном этапе развития ТРБД он относится к экспертным вопросам (зависящим от конструктора), поскольку надлежащие формальные критерии семантики, сформулированные на языке ФЗ, пока отсутствуют. В качественном отношении задача не представляется простой, так как зависимости по отношению друг к другу не обладают полной свободой, подчиняясь упомянутым выше АВ. Следовательно, необходимо и важно уметь оперировать с ФЗ, заключенными в $\mathbb{F}$, с учетом их “аксиоматических” связей.

ЦД, благодаря $\mathbb{F}$, становится информационной составляющей общей задачи компьютерной безопасности (КБ), но сохранение ЦД возможно и без использования ФЗ. Так, например, метод контрольных сумм (МКС) защищает колонки таблиц, однако неприятность заключается в достаточной вероятности возникновения или генерации “малоконечной” цепочки изменений данных таблицы, корректирующих неправильность контрольной суммы (КС). Более того, КС должны располагаться в таблице, что не всегда удобно пользователю и предоставляет дополнительные удобства злоумышленникам.

3. Алгебраизация алгоритмов. Нарушения ЦД могут быть следствием потери конфиденциальности данных в результате НСД, недопущение которого суть общая задача КБ. В любом случае НСД следует из программной опасности (ПО) вредоносных программных продуктов (ПП) и совершается как с нарушением ЦД, так и с ее сохранением. Переходя к ПО, сфокусируем внимание на так называемых недекларированных возможностях (НДВ) ПП. На практике НДВ реализуются программными закладками, внедряемыми злоумышленниками в исходный сертифицированный ПП, который мы будем далее называть эталонным. Как минимум они ощутимо замедляют исполнение программ, но во многих случаях ведут к логическому и подчас к физическому разрушению вычислительных средств. Все виды НДВ киберпреступны. Они применяются в коммерческих, политических, дезорганизующих, шпионских и прочих целях и реализуются компьютерными вирусами разнообразных типов. В частности, ими же производятся нарушения ЦД, а также НСД с последующим противоправным использованием данных. Вопрос: как отличить эталонный ПП от того же ПП, но с внедренными в него НДВ? Это еще одна непростая задача. Основным препятствием к ее решению является сверхгромоздкость развитых ПП. Так поразрядное сравнение кодов программ эталонного ПП с тем же ПП, но собранным в иное время и, что часто бывает, иными средствами, однозначно дает отрицательный результат. Это означает, что на фоне практической невозможности получения совпадений сравнения на специализированных испытаниях ПП несравнимость не может быть критерием несоответствия одного ПП другому. Задача усугубляется вариативностью написания программ, ниже названных функционально эквивалентными (ФЭ)11. Для них не может быть никаких соответствий в принципе, несмотря на похожесть обработки ими внешних событий и похожесть преобразования входных данных в выходные. Это тупик, казалось бы! Однако все же можно попытаться что-то сделать. Пути контроля соответствия ПП его эталону лежат в стандартизации разработки и жесткой регламентации структуры ПП. Нынешняя стандартизация на основе структурно-объектного программирования нацелена в основном на повышение производительности труда программиста. При этом задача компьютерной безопасности остается в тени. Напротив, решение объявленных выше задач 1)–5) открывает путь к обеспечению информационной безопасности на основе замены программ алгебраическими выражениями. Здесь под программами подразумеваются последовательности вывода ФЗ и с точностью до принципа этого достаточно.

4. Инструментарий.

Обозначение 1. Знаки логики:

0) ≗ – эквивалентность A PRIORI, эмпирическое равенство, читается как “то же, что”;

1) знак первоначального равенства := заменяет фразу “…по определению есть…”. Для правостороннего расположения определяемого субъекта22 𝔛 будет использоваться ≕. Например,

𝔛 ≔ 𝔉(𝔛1, 𝔛2, …, 𝔛n) ≗ 𝔉(𝔛1,𝔛2, …, 𝔛n) ≕ 𝔛;

2) символ “|” обозначает словосочетания “такой, что…”, “при условии…”;

3) предикат 𝒜 ⇒ ℬ читается, как “из 𝒜 следует ℬ”;

4) $\overrightarrow \subset $ и $\overrightarrow \subset $ – символы произвольного выбора элемента и подмножества в заданном множестве. Подобно знаку “:=” выбор играет роль глагола повелительного наклонения в предикатах, предназначенных для формирования нового субъекта из существующих.

Пояснение: a $\overrightarrow \subset $ Xa|aX и A $\overrightarrow \subset $ XA|AX.

В приведенных выше выражениях символы a и A становятся именами выбранных элемента и подмножества соответственно. Однако можно сделать разовый выбор $\overrightarrow \subset $X и $\overrightarrow \subset $X без именования субъектов. В том случае $\overrightarrow \subset $X и $\overrightarrow \subset $X являются “именами” выбора для локального использования.

Пояснение: X $\overleftarrow \supset $ aa $\overrightarrow \subset $ X и X $\overleftarrow \supset $ A ≗ A $\overrightarrow \subset $ X.

5) × – декартовое произведение;

6) μ(М) – мощность множества М;

7) ℤ – множество целых чисел; ℤ+ – все неотрицательные целые числа;

8) [i, j]|i, j∈ ℤ |ij – отрезок целых чисел; [n, m[ ≔ [n, m]\{m};

]n, m] := [n, m]\{n} (пустота полуинтервалов не исключается);

9) (( и )) – средство группирования элементарных предложений.

Обозначение 2. Кортеж:

0) Отображение типа x : [1, n] → X|n ∈ 1 + ℤ+ называется кортежем;

1) 〈x0, x1, … , xn〉 – кортеж сущностей x0, …, xn|xiX|i ∈ [0, n], упорядоченных в строке в направлении чтения, где X некоторое множество;

2) 𝒫i – член, стоящий на i-том месте (i = 0, 1, …) кортежа или последовательности 𝒫. По умолчанию нумерацию элементов будем начинать с 0 (нуля). Это означает: 𝒫 ≡ 〈𝒫0, …, 𝒫µ(𝒫)1〉, где µ(𝒫) 1 – последний номер ФЗ в 𝒫.

Обозначение 3. Алфавиты порядков.

Символы ≤ ≥ и слова ≤*)(*≥| ((≤*)(*≥)) будут служить именами частичных порядков (ЧП) на множестве скажем W. В качестве * возможно использование слов любого алфавита или целых чисел $\overrightarrow \subset $+.

Пример: $\mathcal{P}_{i}^{{({\text{и м я }}}}$ ≥ 𝒫j ≗ 𝒫jимя) 𝒫i.

Определение 1. Каскады частичных порядков.

1. Назовем W базой каскадно-упорядоченного множества (КУМ), а совокупность порядков {≤i) |i)W×2| i ∈ [0, n[} – каскадом глубины n|n ∈ ℤ+ на W, если $\text{v}$,wW ⇒ (($\text{v}$i)w$\text{v}$i –1)w))|i ∈ [1, n[. Каскадность выражается цепочкой включений: ≤0) ⊇ ≤1) ⊇ … ⊇ ≤n –2) ⊇ ≤n –1).

2. Обозначение КУМ’а 𝒲 с базой W и глубиной n:

𝒲 ≔ {W, ≤n –2) ⊇ ≤n –1)|i ∈ [1, n[} ≗ {W, ≤0) ⊇ … ⊇ ≤n –1)}.

3. Термины: отдельное частично-упорядоченное множество (ЧУМ) {W, ≤i)|i ∈ [0, n[} будем называть i-тым слоем КУМ’а 𝒲. Каскад – это совокупность слоев КУМ’а.

4. Острое ЧУМ 𝒲 ≔ {W ≤}:

𝒲 называется острым (≗ заостренным), если μ(max{W ≤}) = 1.

Выражения min𝒲 и max𝒲 имеют смысл всегда, поскольку в качестве W будут фигурировать только конечные множества.

1. Отношения и таблицы. Таблицы двумерны. Это означает, что каждая из них состоит из кортежей, которые в свою очередь состоят из значений, привязанных к элементам ее схемы, являющейся конечным, линейно-упорядоченным множеством R, называемым схемой. В настоящей работе схема R универсальна. Другими схемами могут быть только ее подмножества.

Значения компонент кортежа выбираются из доменов, именами которых служат элементы из R, называемые атрибутами. В реальной таблице им соответствуют имена полей (колонок).

Обозначение 4: μ(R) – мощность множества R.

Характерная особенность ТРБД – конечность рассматриваемых в ней схем, т.е. μ(R) < ∞. На этом фоне домены могут быть произвольными бесконечными множествами. Домены разных атрибутов (полей) могут совпадать.

Определение 2. Домены атрибутов и подсхем.

Пусть R – схема, X|XR – подсхема и 𝒟 – множество, необязательно конечное. Для бинарного отношения δ|δ $\overrightarrow \subset $ R × 𝒟 определим домены равенствами:

dom(r) ≔ rδ ≔ {d|d ∈ 𝒟 и rδd} для ∀rR и dom(X) ≔ $\mathop \times \limits_{x \in X} $dom(x).

Домен dom(X) состоит из кортежей, так как подсхема X наследует упорядоченность от схемы R. Далее сформулируем понятие отношения, являющегося основным объектом в ТРБД.

Определение 3. Отношение, таблица:

1) отношением Ш со схемой R называется μ(R)-арное отношение на совокупности доменов {dom(r)|rR}. Формально Ш $\overrightarrow \subset $ dom(R);

2) таблицей со схемой R называется пара {R, Ш} ≕ RШ.

На практике таблицы, входящие в реляционные базы данных, конечны, хотя определение 3, лежащее в основе ТРБД, этого не требует. Ввиду конечности схемы R мощность μ(R) является количеством в ней атрибутов, поэтому кортежи таблицы Ш со схемой R имеют длину μ(R) и состоят из элементов соответствующих доменов.

Усечение кортежа ш|ш ∈ Ш подсхемой X|XR будет обозначаться через ш ⊦ X. Формально ш ⊦ X ≔ {ш ⊦ x|xX}, где ш ⊦ x – значение кортежа ш на подсхеме X и ш ⊦ xdom(x).

Термин. Проекция подсхем на кортежи и отношения:

X ⫞ ш ≔ ш ⊦ X и X ⫞ Ш ≔ Ш ⊦ X.

Предупреждение: то же самое в [7, § 2.3, с. 24] называется “наоборот”: проекция отношения (таблицы) Ш на подсхему X.

Для наглядности элементы в кортежах расположим горизонтально, а кортежи в таблице Ш – вертикально, тогда для атрибута r $\overrightarrow \subset $ R совокупность {ш ⊦ r|ш ∈ Ш} образует колонку таблицы, реализующую ее поле r (атрибут). Внесение элементарной геометрии в устройство таблицы предрасполагает к использованию следующей синонимии: {кортеж, строка, ряд}, {атрибут, поле, колонка}, {проекция, усечение}. Выделенные курсивом термины являются ключевыми словами ТРБД.

Для XR имеем XШ ≔ Ш ⫞ X=X ⫞ Ш и μ(Ш ⫞ X) ≤ μ(Ш), так как после атрибутного усечения таблицы Ш неразличимые элементы в множестве Ш ⫞ X группируются, образуя единственный кортеж в Ш ⊦ X.

Замечание 1. В соответствии с принципами ТРБД [8, Гл. 5, § 5.3, с. 166] в таблицах не должно быть совпадающих строк. Поэтому после удаления колонок (атрибутов) необходима очистка таблицы от дубликатов строк-кортежей.

2. Функциональные зависимости. 2.1. Конструкция. Каждая зависимость Ф является упорядоченной парой Ф =X, Y= XY подсхем X, Y|X, YR схемы R. Конструктивно ФЗ проста и может существовать абстрактно вне ТРБД. Именно в таком виде ФЗ на схеме R появятся в обозначениях 5–7. Однако, начиная с определения 4, будем возвращаться к истокам ФЗ, которыми являются таблицы РБД, представленные многоместными алгебраическими отношениями между атрибутами схемы R в среде dom(R).

Предупреждение. В [7, 8] вместо XY используется XY, что мы резервируем для функций.

Обозначение 5. Показательная (степенная) функция множеств:

1) AW – множество всех отображений из множества W в множество A;

2) 2W – множество всех подмножеств множества W|2W ≔ {0, 1}W.

Слово 2W сокращает запись {0, 1}W, которая подразумевает взаимно однозначное соответствие (см. [9, § 24, c. 121]) между характеристическими функциями W → {0, 1} и подмножествами в W.

Пример: 2R × 2R является множеством всех зависимостей, поскольку в декартовом произведении сомножители линейно упорядочены.

Обозначение 6. ФЗ схемы R:

$2_{ \to }^{R}$2R ≔ 2R × 2Rвсе зависимости (см. обозначение 5 и далее обозначение 8);

X2R ≔ {XZ|ZR}|YR начально определенные зависимости;

$2_{ \to }^{R}$Y ≔ {ZY|ZR}|YRконечно определенные зависимости.

В обозначениях 6 мы навязываем нижним стрелкам роль декартового произведения, хотя в кортежах вида UV знак ’’ является всего лишь направленным соединителем, но не произведением ’×’. Это делает обозначения $2_{ \to }^{R}$2R и 2R × 2R синонимичными, но первое из них предпочтительнее, поскольку оно визуализирует упорядоченность подсхем в парах UV, выбираемых из $2_{ \to }^{R}$2R, тем более, что само декартово произведение ориентировано.

Обозначение 7. Компоненты ФЗ.

Пусть Ф – какая-либо ФЗ над схемой R. Словом ФH будет обозначаться подсхема, фигурирующая в ее начале, а ФK – в конце. Это означает ФH, ФKR и Ф ≡ $\Phi _{ \to }^{H}$ФK|Ф ∈ $2_{ \to }^{R}$2R.

Связь между ФЗ и ее таблицей дается нижеследующим определением 4, в котором ФЗ извлекается из таблицы. В этой интерпретации ФЗ отражает какое-либо семантическое свойство таблицы.

Определение 4. ФЗ отношения Ш.

Пусть Ш – отношение со схемой R и X, Y $\overrightarrow \subseteq $ R – подсхемы. Отношение Ш удовлетворяет зависимости Ф ≔ XY, если (см. [67, § 4.1, с. 51]) для ∀ пары кортежей ш1, ш2 ∈ Ш из равенства ш1X=ш2X следует ш1Y=ш2Y. С помощью обозначения 7 определение 4 можно представить короче:

ш1 ⫞ ФH= ш2 ⫞ ФH ⇒ ш1 ⫞ ФK= ш2 ⫞ ФK.

В случае Y = R приходим к определению ключа X отношения Ш(R) как совокупности атрибутов ФH, на которых однозначно определяются кортежи отношения Ш. Каждое отношение имеет не менее одной зависимости, так как схема R является его ключом.

Обозначение 8. Класс разделяющихся ФЗ:

2R ≔ {Θ|ΘH ∩ ΘK =|Θ ∈ $2_{ \to }^{R}$2R}.

Следующее определение важно для ТРБД, но далее не используется.

Определение 5: (влечет) $\mathbb{F}$AB (следует).

Множество зависимостей $\mathbb{F}$ влечет за собой зависимость AB, если каждое отношение, удовлетворяющее всем зависимостям из $\mathbb{F}$, удовлетворяет также зависимости AB. В этом случае будем говорить также, что функциональная зависимость AB следует из $\mathbb{F}$.

2.2. Аксиомы вывода. Следование зависимости из других не кажется конструктивным. Напротив вывод зависимости AB из какого-либо множества $\mathbb{F}$, обозначаемый далее стрелкой ⇛, осуществляется поэтапным применением к зависимостям из $\mathbb{F}$ правил, именуемых далее, как и в [7, § 4.2, с. 55], F-аксиомами вывода. Ниже приведен их полный перечень, исходя из обозначений подсхем X, Y, Z, V схемы R, т.е. R $\overleftarrow \supseteq $ X, Y, Z, V:

F1. Рефлексивность33: ∅ ⇛ XX.

F2. Пополнение: XYX ZY.

F3. Аддитивность: XY и XZXYZ.

F4. Проективность: XYZXY.

F5. Транзитивность: XY и YZXZ.

F6. Псевдотранзитивность: XY и YZVXZV.

Заметим, правые части АВ, фигурирующие в порядке чтения после символа ⇛, могут отсутствовать в $\mathbb{F}$. Литеры вида F№, где № ∈ [1, 6], являются именами АВ и предназначены для использования в последовательностях (≗ алгоритмах) вывода в качестве имен. Как отмечалось выше, аксиомы вывода служат командами в некоторой умозрительной ВМ, преобразующей ФЗ множества $\mathbb{F}$ |$\mathbb{F}$$2_{ \to }^{R}$2R, заданного произвольно.

Три аксиомы F1, F2 и F6, называемые аксиомами Армстронга, составляют достаточное и независимое подмножество. Под достаточностью понимается выводимость из них F3, F4 и F5, а независимость означает невозможность вывода каждой аксиомы из оставшихся двух.

Также самодостаточны B-аксиомы (см. [7, § 4.5, с. 60]):

B1. Рефлексивность: ∅ ⇛ XX,

B2. Накопление: XYZ и ZUXYZU,

B3. Проективность: XYZXY.

Обозначение 9. Аксиомы вывода F, B и FB:

F1÷F6 ≔ {F1, F2, F3, F4, F5, F6},

B1÷B3 ≔ {B1, B2, B3}, B12 B1B2 = B\B3, B23B2 B3 = B\B1,

FBF1÷ F6 B1÷B3.

Ввиду произвольности X, Y, Z, U аксиому накопления B2 можно записать как: {AB, CD}|B ⊇ ⊇ CA(BD).

3. Вывод функциональных зависимостей. 3.1. Алгоритмический вывод. Перечисленные выше F и B аксиомы, на самом деле, являются нетрудными следствиями определения 4, что уже отмечалось во Введении. Для демонстрации его применения сформулируем следующее утверждение.

Лемма 1. Усечение зависимости: AB $ \Lleftarrow \Rrightarrow $ A(B $\overrightarrow \subset $ A)|A,BR.

Определение 6. Замкнутость множества зависимостей.

Будем говорить, что множество зависимостей $\mathbb{F}$ | $\mathbb{F}$ ⊆ 2R × 2Rзамкнуто или, что то же самое, устойчиво относительно E|EFB, если применение аксиом $\overrightarrow \subset $E к зависимостям из $\mathbb{F}$ дает снова зависимости из $\mathbb{F}$.

Определение 7. ${{\mathbb{F}}^{{\mathbf{E}}}}$ – замыкание $\mathbb{F}$ |$\mathbb{F}$ ⊆ 2R × 2R аксиомами из E|EFB.

Замыканием ${{\mathbb{F}}^{{\mathbf{E}}}}$ множества $\mathbb{F}$ аксиомами из E назовем множество ФЗ, наименьшее из замкнутых относительно E множеств, содержащих $\mathbb{F}$.

В частности, ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$ – замыкание множества $\mathbb{F}$ всеми FB-аксиомами вывода.

Определение 7 допускает дуальную формулировку: ${{\mathbb{F}}^{{\mathbf{E}}}}$ является максимальным множеством ФЗ, выводимых из $\mathbb{F}$ с помощью аксиом E|EFB.

Следующее определение выражает понятие E-вывода зависимости XY из множества $\mathbb{F}$ через его замыкание [7, § 4.3, с. 57].

Определение 8. XY E-выводима из множества $\mathbb{F}$, если (XY) ∈ ${{\mathbb{F}}^{{\mathbf{E}}}}$.

Обозначение 10. Факт E-выводимости XY из $\mathbb{F}$: $\mathbb{F}$ $\mathop \Rrightarrow \limits^{\mathbf{E}} $ XY|E FB.

Термин. Индифферентная выводимость: $\mathbb{F}$XY$\mathbb{F}$ $\mathop \Rrightarrow \limits^{{\mathbf{FB}}} $ XY.

Непосредственно из определений 5 и 8 следует $\mathbb{F}$XY$\mathbb{F}$XY или, что то же самое: Если XY выводится из $\mathbb{F}$, то $\mathbb{F}$ влечет за собой XY.

Большим достижением ТРБД является нижеследующая теорема 1 об эквивалентности вывода ⇛ и следования⇉. Ее формулировка включает в себя одновременно предыдущее утверждение и обратное к нему.

Теорема 1 (Армстронг). Система аксиом FF1÷F6 вывода полна, т.е. XY выводится из $\mathbb{F}$, тогда и только тогда, когда $\mathbb{F}$ влечет за собой XY.

Иными словами, $\mathbb{F}$XY$\mathbb{F}$XY.

Доказательство теоремы можно почерпнуть в [7, теорема 4.1, с. 58].

Лемма 2. Системы аксиом Армстронга {F1, F2, F6} и B-аксиом – эквивалентны; ⇒ система B-аксиом {B1, B2, B3} полна (см. [7, § 4.5, с. 60]).

Полнота B-аксиом приводит к возможности F-вывод заменить B-выводом и наоборот, а также пользоваться на равных индифферентным выводом.

Нетрудно видеть, что получение усеченной функциональной зависимости в лемме 1 дважды для ⇚ и ⇛ подпадает под действие определения 9.

Определение 9. Последовательность Вывода 𝒫.

Внесение линейного порядка в ℙ|ℙ $\overrightarrow \subset $ 2R × 2R делает из него ПВ, если каждая функциональная зависимость в 𝒫:

является рефлексией, т.е. выводится с помощью F1/В1,

выводится из предыдущих ФЗ в 𝒫 после применения к ним одной из АВ,

не выводима вообще из каких-либо ФЗ в ℙ.

Замечание 2. Определение 9 допускает повторы ФЗ в 𝒫. Во избежание этого далее с помощью определения 15 будут временно приняты очень простые, формально-технические меры.

Одной из главных целей настоящей работы является спрямление алгоритмов ПВ. Задача принципиальна, серьезна и будет решена с соблюдением принципа ФЭ в два этапа:

1) консолидация повторов ФЗ в их повторное использование (см. далее п. 3) леммы 3;

2) устранение в ПВ повторных использований ФЗ (см. далее теорему 4).

На этапе 1) достигается индивидуализация ФЗ в ПВ без привлечения искусственных приемов, упомянутых в замечании 2. Пока же, вплоть до достижения необходимого уровня математического аппарата, затрагивающего ПВ отвлеченно, будем временно предполагать отсутствие повторов ФЗ в ПВ.

На этапе 2) выводу придается структура дерева, что необходимо для алгебраизации алгоритмического вывода ФЗ.

Обозначение 11. Каскад порядков вывода.

1. Последовательность вывода 𝒫 является “двухцветным” графом:

↠ ребро пошагового формирования в графе следования,

⇛ ребро вывода в графе вывода.

2. Последовательность вывода 𝒫 дважды упорядочена:

=↠ линейный порядок ее пошагового формирования,

=⇛ частичный порядок вывода ФЗ.

Направленности ребер и упорядоченностей представляются записями:

Φ ↠ Ψ ≗ Φ предшествует Ψ и Φ ⇛ Ψ ≗ Ψ выводится из Φ,

min =↠ max и min =⇛ max.

Линейная упорядоченность =↠ задана определением 9. Частичная упорядоченность отношения =⇛ следует из трех свойств: рефлексивность – очевидно; антисимметричность – обеспечивается встроенностью =⇛ в =↠ ; транзитивность – по построению =⇛ из ⇛.

Свойство Φ =⇛ Ψ ⇒ Φ =↠ Ψ делает последовательность вывода Каскадно-Упорядоченным Множеством (см. п. 1) определения 1), что является предметом исследования задачи 2) Введения.

3. Сборка структур последовательности вывода 𝒫:

𝒫 ≔ {ℙ{↠ =↠}{⇛ =⇛}} – результат сборки,

{𝒫, ↠} ≔ {ℙ, ↠} ≔ 𝒫0↠…↠ 𝒫 µ(𝒫)1 – граф следования,

{𝒫, ↠}i ≗ 𝒫i| i ∈ [0, µ(𝒫)[ – функциональные зависимости вывода,

{𝒫, ⇛} ≔ {ℙ, ⇛} – граф вывода,

{𝒫, =↠} ≔ {ℙ, =↠} – линейно упорядоченное множество следования,

{𝒫, =⇛} ≔ {ℙ, =⇛} – частично упорядоченное множество вывода,

{𝒫} ≔ ℙ – все ФЗ, составляющие 𝒫 без связей между ними.

Замечание. 𝒫 состоит из трех элементов: ℙ, {↠ =↠} и {⇛ =⇛}, однако, если позволит контекст, будем писать 𝒫 или ℙ вместо {𝒫}.

ПВ как процесс и как результат (см. п. 2 в Обозначении):

𝒫 является выводом для Θ, если 𝒫µ(𝒫)1= Θ ≗ 𝒫 ⇛ Θ|𝒫µ(𝒫)1= Θ ≗ Θ ⇚ 𝒫.

Потенция ФЗ в ПВ:

активность – ФЗ используется для вывода ФЗ следующих за ней в 𝒫,

пассивность – ФЗ является результатом вывода из предшествующих ФЗ,

бездействие – изолированные ФЗ ≗ не активность -и- не пассивность,

активность-и-пассивность – состояние, определяющее так называемые “внутренние” ФЗ.

Определение 10. Классификация ФЗ в ПВ:

min𝒫 ≔ min{ℙ =⇛} – ФЗ (возможно активные) -и- не пассивные в 𝒫,

ℂ(𝒫) ≔ min𝒫\∅B1 – совокупность констант вывода 𝒫,

{𝒫}\ℂ(𝒫) – множество выводимых (≗ пассивных) ФЗ в 𝒫,

{𝒫}\ℂB1(𝒫) – все строго выводимые ФЗ в 𝒫, то же, что {𝒫}\min𝒫.

Замечание 4. Свойства Ψ ∈ (ℂ(𝒫)\{Ψ})FB|Ψ ∈ ℂ(𝒫) и Ψ ∈ ((𝒫 ∩ ℂ(𝒫))\\{Ψ})FB|Ψ ∈ 𝒫 ∩ ℂ(𝒫), справедливые для некоторых ПВ, указывают на возможное присутствие выводимых ФЗ среди констант и наоборот.

Определение 11. Представление результата Θ вывода 𝒫 в виде функции от констант ℂ(𝒫) (важно!): Θ ≗ Θ〈〈ℂ〉〉 ≔ 𝒫 µ(𝒫)1|((𝒫 ⇛ Θ и ℂ ≔ ℂ(𝒫)).

Представление Θ в виде функции Θ〈〈ℂ〉〉 позволит выращивать деревья вывода из констант ℂ(𝒫), используя суперпозиции функций, как это сделано ниже в теореме 3. Константы являются посевным материалом для формирования ПВ из ФЗ, и в этом качестве они выступают в определении в [7, § 4.5, с. 59], от которого мы немного отошли, дав вместо него определение 9, где роль констант не выявлена. Тем не менее, позже они станут операндами в алгебраических выражениях, ФЭ-заменяющих ПВ.

3.2. Регламентация вывода. RAP-вывод, определяемый ниже, представляет исторический интерес. Аббревиатура RAP составлена из первых букв названий B-аксиом: B1Reflexivity, В2 – Accumulation, В3Projectivity.

Определение 12 (см. [7, п. 4.5.1, с. 61] и обозначения 2). RAP-последовательностью 𝒫 вывода AB из $\mathbb{F}$ называется B-вывод, удовлетворяющий следующим условиям:

0) 𝒫0AA – начальная (нулевая) зависимость в B-выводе;

1) 𝒫 µ(𝒫)1AB – последняя зависимость в B-выводе;

2) каждая зависимость, отличающаяся от первой или последней, либо принадлежит $\mathbb{F}$, либо имеет вид A $\overrightarrow \subset $ R и получена с помощью аксиомы B2.

С точки зрения [7] ценность этой конструкции заключена в следующем утверждении.

Теорема 2. RAP-редукция вывода. Пусть $\mathbb{F}$ – множество зависимостей. Если AB выводима из $\mathbb{F}$, то существует RAP-последовательность вывода AB из $\mathbb{F}$.

Теорема 2 имеет ту же формулировку, что и теорема 4.2 в [7, с. 62]. Нам, к сожалению, не удалось передоказать ее, чего она заслуживала бы. Вместо нее в разд. 4.2 сформулирована теорема 3, которой воспользуемся для алгебраической интерпретации аксиом вывода, лежащей в основе эффективного вычисления замыкания $\mathbb{F}$FB. Она исходит из игнорирования нижеследующим определением 12* начальной рефлексии определения 12.

Определение 13. Однотипность ПВ.

𝒫 однотипна, если начальные подсхемы всех ее выводимых ФЗ совпадают ≗ μ{(𝒫\$\mathbb{F}$B1)H} ≤ 1 (см. определение 7).

Примером однотипных ПВ могут служить RAP-последовательности, подчиняющиеся определению 12. Нижеследующее определение родственно ему и отличается от него свободой использования рефлексий.

Определение 12*. AP-последовательность вывода 𝒫:

1) 𝒫 является однотипной последовательностью B-вывода,

2) аксиомы В3 (проективность) используются только в конце вывода.

Присутствие в определении 12* требования 2) на самом деле является следствием очень простого свойства совместного использования АВ в ситуации В3В2, справедливого для любых ПВ и установленного ниже в лемме 4. Более того в виду элементарного равенства (X\Y)\Z = X\(YZ) в него можно внести дополнительное условие μ{В3|В3 ∈ 𝒫} ≤ 1.

Усиление регламентации вывода ФЗ будет связано со стилями, представленными ниже.

Обозначение 12. Стили вывода:

FB-вывод – индифферентный вывод (использующий F и B аксиомы), при этом префикс “FB-” необязателен для применения;

F-вывод – ПВ, использующие только F-аксиомы;

B-вывод – ПВ, использующие только B-аксиомы;

RAP-вывод – то же, чтоRAP-последовательность вывода” в определении 12.

Дополним список стилями, содержащими суть наших исследований:

AP-вывод – упрощение RAP-вывода (см. определение 12*),

AP\B1-вывод – AP-вывод без использования аксиомы B1,

ALT-вывод – чередующийся AP-вывод, в котором выводимые ФЗ, следуют строго за константами и наоборот,

АЛГ-вывод – выводы, реализуемые алгебраическими выражениями.

Обозначение 13. Стилевой класс ФЭПВ (см. сноску 1):

{$\mathbb{F}$ $\mathop \Rrightarrow \limits^{\mathbf{E}} $ XY}|EFB или E ∈ {СТИЛИ ВЫВОДА} (см. обозначение 10),

{$\mathbb{F}$XY} – все выводы XY из $\mathbb{F}$E = FB,

{$2_{ \to }^{R}$2RXY} – все ФЭ последовательности вывода E = FB,

{$\mathbb{F}$ $\mathop \Rrightarrow \limits^{{\mathbf{B2}}} $ Ψ} – все B2-выводы зависимости Ψ из $\mathbb{F}$E = B2,

{$\mathbb{F}$ $\mathop \Rrightarrow \limits^{{\mathbf{B2}}} $ Ψ $\mathop \Lleftarrow \limits^{{\mathbf{B2}}} $ $\mathbb{G}$} – все B2-выводы зависимости Ψ из $\mathbb{F}$ и $\mathbb{G}$E = B2,

{$\mathbb{F}$ ⇛ Ψ} ≗ {$\mathbb{F}$ $\mathop \Rrightarrow \limits^{{\mathbf{FB}}} $ Ψ} – все ПВ Ψ из $\mathbb{F}$E = FB,

{$\mathbb{F}$ ⇛} ≗ {$\mathbb{F}$ $\mathop \Rrightarrow \limits^{{\mathbf{FB}}} $} – все ПВ из $\mathbb{F}$ (индифферентные ПВ) $ \equiv \mathop \cup \limits_\Phi $ {$\mathbb{F}$ ⇛ Ф},

{$\mathbb{F}$ $\mathop \Rrightarrow \limits^{\mathbf{E}} $} – все E-выводы из $\mathbb{F}$,

{$\mathbb{F}$ $\mathop \Rrightarrow \limits^{{\mathbf{А Л Г }}} $} – все алгебраические выражения с операндами из $\mathbb{F}$.

Справедливо утверждение

${{\mathbb{F}}^{{\mathbf{E}}}}$ = MAX{$\mathbb{F}$ $\mathop \Rrightarrow \limits^{\mathbf{E}} $, =⇛} ≗ $\mathop \cup \limits_\mathcal{P} $MAX{𝒫, =⇛}|𝒫 ∈ $\mathbb{F}$ $\mathop \Rrightarrow \limits^{\mathbf{E}} $.

3.3. Постановка задачи алгебраизации вывода. Из правил вывода F1÷F6 и B1÷B3 видно, что АВ по сути являются алгебраическими операциями, заданными на полном множестве зависимостей $2_{ \to }^{R}$2R. При этом F2, F4 можно отнести к квазиунарным операциям, а B2, F6 – к бинарным:

F2. XY и ZVXZYоперация пополнения,

F4/B3. XY и ZVXY\Vоперация проектирования,

B2F6. XY и ZVX ∪ (Z\Y)YVоперация полного накопления.

Заметим, рефлексивность F1/B1 можно трактовать как нульарную операцию, действие которой подчинено случаю или, напротив, преднамеренному выбору. Правило вывода B2F6, составляющее содержание леммы 6, ранее не встречалось нам. Упоминание о нем без должных предыстории и развития можно найти в [8, § 10.4, с. 406]. Вместе с тем B2F6, являясь важной предпосылкой получения целевого результата, алгебраически интерпретирует B2 и F6. Она обозначается символом ▶, с помощью которого B2F6 приобретает знакомый для операций вид (AB)▶(CD) ≔ A ∪ (C\B)BD, от которого можно с легкостью вернуться к аксиомам вывода44:

(3.2)

В алгебраической природе AB кроется возможность ФЭ-замены вольно написанных программ вывода, т.е. элементов множества {$\mathbb{F}$AB}, регламентированными алгебраическими выражениями, использующими одну из бинарных операций ▶, ▹, ⋗, которые в определениях 19, 22, 23 будут названы операциями накопления. Первая из них ▶, так называемая операция полного накопления, алгебраизует правило вывода B2F6. Наиболее логично выглядит средняя: (XY) ▹ (ZV) = = (X ∪ (Z\Y))((Y ∪ (V\X)). Операция ⋗ носит вспомогательный характер.

ДЕКЛАРАЦИЯ. Целью настоящей статьи является замена последовательностей вывода зависимостей Функционально Эквивалентными им алгебраическими выражениями в D-алгебре унарных операций F1/B1, F4/B3, а также операций {▶▹} типа B2F6, определенных на множестве $2_{ \to }^{R}$2R.

Решение поставленной задачи дается ниже теоремами 6 и 6*, эффективно вычисляющими замыкание ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$. Начало этому положено теоремой 1, и далее строится математический алгоритм алгебраизации вывода ФЗ.

4. Гигиена ПВ. Переход от одного стиля вывода к следующему без потери результата вывода сопровождается освобождением ПВ от ненужных деталей, а также в ряде случаев согласованной перестройкой двукаскадных связей следования и вывода, ведущей к их упрощению. В совокупности операции “очищения” ПВ, ведущие к получению из нее другой функционально эквивалентной ей ПВ, составляют гигиенические средства аппарата допустимых преобразований алгоритмов вывода.

Определение 14. Нежелательные особенности ПВ.

Повтор – зависимость, которой в 𝒫 строго предшествует в смысле порядка следования ≠↠ другая ФЗ, совпадающая с ней.

Тупик – зависимость, не использующаяся для вывода иных ФЗ в 𝒫. Тупики образуют множество max{𝒫, =⇛}, содержащее, в частности, последнюю зависимость max{𝒫, =↠}. Тупики неактивны-и-(возможно пассивны) в терминах п. 5 обозначений 11.

Пункт 3) леммы 3 заменяет повторы ФЗ их повторным использованием, что называется исходящим гнездованием. Затем теорема 4 приводит ПВ к функционально эквивалентному состоянию, в котором исходящее гнездование отсутствует. Вершины графа вывода {𝒫 =⇛} могут иметь произвольную полустепень выхода (≗ исхода), в то время как полустепени входа (≗ захода) ≤2 [10, Гл. X, § 64, с. 283] в соответствии с конструкцией аксиом F1÷F6 и B1÷B3. Для них проблем меньше, но все же понятие AP-вывода (см. определение 12*), основанное на свойстве однотипности ФЗ (см. определение 13), ставит задачу представления ПВ в виде суперпозиции острых ЧУМ'ов (см. п. 4) определения 1), коими являются AP-выводы.

В связи с замечанием 2 к определению 9 дополним конструкцию ПВ средством индивидуализации ее членов. С этой целью свяжем ФЗ с ее номером в ПВ, хотя вместо индексов из [0, µ(𝒫)[ можно использовать элементы любого множества N|μ(N) = μ(𝒫) ≡ μ(ℙ).

Определение 15. Индивидуализация зависимостей в 𝒫.

〈𝒫〉 ≔ 〈〉 ≔ {〈i,|I ∈ [0,µ(ℙ)[} (см. п. 1) в обозначении 2).

Индивидуализация заключается в переходе от ℙi к 〈i,ℙi〉. Номер i является меткой, позволяющей формально различать в ПВ совпадающие функциональные зависимости, стоящие на разных местах.

Лемма 3. Сборка повторов и удаление тупиков.

Пусть 𝒫 – последовательность вывода XY из множества зависимостей $\mathbb{F}$, тогда, не изменяя порядка следования ФЗ в 𝒫 и перестраивая связи вывода, можно достичь следующего:

1) привести 𝒫 в состояние 𝒬, в котором XY будет уникальна так, чтобы XY стала бы последней в 𝒬;

2) удалить из 𝒬 все тупиковые зависимости, отличные от XY;

3) исходящее гнездование: заменить в 𝒬 повторы ФЗ их повторным использованием;

4) резюме: последовательность 𝒫 вывода XY можно привести в состояние , в котором отсутствуют тупики и удалены повторы, а также XY является последней зависимостью, т.е. ⇛ ⇛ XY.

Вербализуем результат предыдущей леммы.

Определение 16. Уплотнение последовательности вывода 𝒫:

0. 𝒫 ↦ . Символ ↦ означает алгоритмический переход.

1. Процесс удаления в последовательности вывода тупиковых и повторяющихся зависимостей назовем ее уплотнением 𝒫 ⇛Ψ ⇒ ⇛Ψ.

2. Последовательность вывода 𝒫, в которой нет повторяющихся и тупиковых, кроме последней, зависимостей, назовем плотной, что выражается равенством 𝒫 = .

Имеем: ПВ – плотно ⇒ {𝒫µ(𝒫)1} ≡ max{ℙ =↠} ≡ max{𝒫 =⇛}.

4.1. Принуждение B-вывода к AP-требованиям.

Лемма 4. Переставляемость аксиом.

Исполняемые друг за другом аксиомы B3 и B2 переставляемы.

То же символически: B3B2B2B3 (см. п. 0 определения 16).

Сформулированная лемма и предшествующее ей замечание обеспечивают концентрацию B3 в конце вывода. Это позволяет сосредоточить внимание на B12-выводе (см. обозначения 9 и 12).

Следствие из леммы 4. Плотный вывод можно ФЭ-привести в состояние B12B3. Под (B12B3)-выводом подразумевается последовательное соединение B12-вывода с единственной аксиомой B3, присоединенной к нему в конце.

4.2. Декомпозиция последовательности вывода.

Обозначение 14. Нéмощное разбиение $\mathop \cup \limits^\centerdot $ множества:

A $\mathop \cup \limits^\centerdot $ BAB|μ(AB) ≤ 1.

Теорема 3 и ее доказательство представляют собою описание алгоритма, следующего правилам традиционного программирования.

Теорема 3. AP-декомпозиция плотного вывода 𝒫 (см. п. 2 определения 16).

Плотный вывод 𝒫|𝒫 ⇛ $\Delta _{1}^{1}$ ≔ 𝒫µ(𝒫) – 1 можно ФЭ-привести к нéмощному разбиению на плотные AP-выводы с результатами вывода $\Delta _{q}^{p}$ |$\Delta _{q}^{p}$ ∈ 𝒫|p,q ∈ [1,μ(𝒫)[. Все AP-выводы изоморфны лежащим в 𝒫 соответствующим фрагментам вывода.

Доказательство. Требуемая декомпозиция устанавливается итеративно, начиная с результата вывода $\Delta _{1}^{1}$ |$\Delta _{1}^{1}$ ≔ 𝒫µ(𝒫)1 до ФЗ, используемых в 𝒫 для вывода, т.е. до аргументов 𝒫, лежащих в ℙ. Иначе говоря, движение осуществляется от max к min против ребер вывода $\mathop \Rrightarrow \limits^{{\mathbf{B2}}} $. В результате для каждой зависимости Ψ, выводимой в 𝒫, можно восстановить непрерывную и максимальную цепь ее получения по признаку однотипности начала и конца звена, к которым могут примыкать ФЗ другого типа, становящимися аргументами формируемого локального вывода. На этом отрезке вывода по ⇛ зависимость Ψ является ее максимальным элементом. Однотипный с ним противоположный конец Ф минимален. В силу особенностей B12-вывода он обязан быть константой, т.е. Ф ∈ ℙ. Если на предыдущем этапе максимальная ФЗ была найдена таким же образом и ей ранее был присвоен уровень p – 1, то всем ФЗ другого типа, примыкающим к полученной подпоследовательности вывода, присвоим следующий уровень p. Назовем их совокупность, исключая константы из ℙ, группой. Если Ψ на предыдущем этапе представляла собой $\Delta _{1}^{1}$, то положим p = 1 в предположении, что нумерация уровней начинается с 0. Одноуровневые группы ФЗ расположим друг за другом последовательно в любом порядке и затем перенумеруем ФЗ их совокупности так, чтобы номера внутри группы представляли собой отрезки целых чисел. Продолжение процесса для всех групп и всех ФЗ в них даст в результате требуемое разбиение 𝒫 на AP-выводы $\Delta _{k}^{{p - 1}}\left\langle {\left\langle {\kern 1pt} \right.} \right.\Delta _{i}^{p},\, \ldots ,\Delta _{j}^{p}\left. {\left. {\kern 1pt} \right\rangle } \right\rangle $, где p – номер уровня и k, i, j – групповые номера ФЗ. Будем считать, что константы встроены в полученные AP-последовательности и в выявлении не нуждаются, в то время как выводимые в 𝒫 зависимости $\Delta _{i}^{p},\, \ldots ,\Delta _{j}^{p}$ необходимы для продолжения и завершения процесса декомпозиции.

Таким образом, на уровне № 0 располагается фиктивная AP-последовательность $\Delta _{1}^{0}\left\langle {\left\langle \right.} \right.\Delta _{1}^{1}\left. {\left. \right\rangle } \right\rangle $. На уровне № 1 – $\Delta _{1}^{1}\left\langle {\left\langle \right.} \right.\Delta _{1}^{2},\, \ldots ,\Delta _{n}^{2}\left. {\left. {\kern 1pt} \right\rangle } \right\rangle $. На следующем уровне возможно образование n|n ∈ ℤ+ штук AP-выводов и т.д.

Определение 17. Сверхплотный вывод (см. определение 16).

Плотный вывод называется сверх-плотным, если в нем отсутствует исходящее гнездование (≗ повторное использование) ФЗ (см. п. 3) леммы 3).

Теорема 4 обеспечивает спрямление алгоритмов вывода и является центральным местом настоящей работы. К сожалению, мы не можем здесь представить ее доказательство в силу большого объема и невозможности привлечения к нему необходимых математических аксессуаров по той же причине:

Теорема 4. Устранение повторов использования ФЗ (важно!).

1. Плотный, однотипный B2-вывод 𝒫 можно привести 𝒫 ↦ к сверх-плотному однотипному B2-выводу .

2. Устранение повторов использования ФЗ в B2-выводе 𝒫 оставляет почти-неизменным вход и неизменным выход:

вход 𝒫 ∩ ℙB1 ∩ ℙB1⊆(𝒫 ∩ ℙB1) ∪ {$\overline X $ |X ≔ 𝒫µ(𝒫)1} (см. сноску 3),

выход max𝒫=max,

где max𝒫 ≔ max{𝒫 =↠}=max{𝒫 =⇛} ((⇐; вывод 𝒫 плотен)) и max𝒬 = 𝒬µ(𝒬)1|𝒬 ∈ {$2_{ \to }^{R}$2R⇛}.

Обозначение 15. Результат сверх-уплотнения вывода 𝒫.

Лемма 5 (важно!). Древовидность сверх-плотного вывода.

Сверх-плотный вывод 𝒫|𝒫 ⇛ Δ ≔ 𝒫µ(𝒫)1 является деревом с корнем Δ.

4.3. Чередующаяся последовательность вывода (то же, что ALT-вывод, упомянутый в обозначениях 12).

Определение 18. Чередование ФЗ в выводе.

1. Операция $ \sqsubset \sqsupset $ формирования чередующегося кортежа. Пусть T – некоторое множество. Исходя из двух кортежей ti ≔ 〈$t_{0}^{i}$, …, $t_{n}^{i}$|ti $\overrightarrow \subset $ T|i ∈ 〈0, 1〉 (см. обозначение 2) размерности n|n ∈ 1 ++, построим t0 $ \sqsubset \sqsupset $ t1 ≔ 〈$t_{0}^{0}$, $t_{0}^{1}$, $t_{1}^{0}$, $t_{1}^{1}$, …, $t_{n}^{0}$, $t_{n}^{1}$〉 размерности 2n.

2. Чередующаяся ПВ. Вывод 𝒜 зависимости 𝒜µ(𝒜)1 из множества $\mathbb{F}$ |$\mathbb{F}$ ≔ min𝒜 ⊆ $2_{ \to }^{R}$2R (см. определение 11) называется чередующимся, если для n ≔ µ(𝒜) 1, 𝒜′ ≔ 𝒜\𝒜n| ∈ 𝒜 и 𝒜′ ≔ 𝒜| ∉ 𝒜 выполняются два условия:

2.1. 𝒜0$\mathbb{A}$ и = (𝒜0 ↠ ((𝒜\𝒜0) ∩ $\mathbb{A}$) $ \sqsubset \sqsupset $ 𝒜′\$\mathbb{A}$) $\mathop \Rrightarrow \limits^{{\mathbf{B3}}} $ 𝒜n. Часть $\mathop \Rrightarrow \limits^{{\mathbf{B3}}} $ 𝒜n необязательна для использования;

2.2. {𝒜2i, 𝒜2i+ 1} $\mathop \Rrightarrow \limits^{{\mathbf{B2}}} $ 𝒜2(i+ 1)|i ∈ [0, $\frac{{n - 1}}{2}$[.

Определение не исключает использование множества ${{\mathbb{A}}^{{{\mathbf{B1}}}}}$ вместо $\mathbb{A}$. Чередование в 𝒜 констант 𝒜2i –1|i ∈ [0, $\frac{{n - 1}}{2}$[, включая 𝒜0, и выводимых ФЗ 𝒜2i | i ∈ [1, $\frac{{n - 1}}{2}$], включая 𝒜n, для наглядности представим схемой:

(4.1)

В ней символ ↠ изображает один шаг следования/формирования в выводе 𝒜 и является ребром графа {𝒜 ∩ ${{\mathbb{A}}^{{{\mathbf{FB}}}}}$ ↠}. Вертикальные шаги ⤋ предложенной выше схемы связывают ФЗ, между которыми имеет место одношаговое следование ↡. Горизонтальные выводы 𝒜2(i –1)$\mathop \Rrightarrow \limits^{{\mathbf{B2}}} $ 𝒜2i | i ∈ ∈ [0, $\frac{{n - 1}}{2}$] реализуются двумя шагами следования, последний из которых совмещен с вертикальным выводом вида 𝒜2i –1$\mathop \Rrightarrow \limits^{{\mathbf{B2}}} $ 𝒜2i. В любом случае ALT-вывод удовлетворяет требованиям каскадности (см. определение 1).

Теорема 5. ALT-редукция сверх-плотного AP-вывода (см. определение 17). Сверх-плотный AP-вывод 𝒫 можно ФЭ-привести в состояние (4.1).

5. Алгебраический вывод ФЗ. Уже в разд. 3.3 АВ толковались как алгебраические операции, и на том этапе можно было бы придать статус “D-алгебра” полному множеству зависимостей $2_{ \to }^{R}$2R, а также замыканиям ${{\mathbb{F}}^{{\mathbf{D}}}}$|(($\mathbb{F}$ $\overrightarrow \subset $ $2_{ \to }^{R}$2R и D $\overrightarrow \subset $ )) (см. обозначение 9). В нашем случае понятие “D-алгебра” соответствует установкам [11, гл. II “Алгебры”, с. 55] и [12, Гл. 3, § 1, п. 3, с. 109], в которых вместо D используется знак Ω. В этой главе D будет дополнена тремя операциями {▶▹⋗} (см. далее определения 19, 22 и 23), две из которых {▶▹} позволят заменить последовательности вывода функционально-эквивалентными им алгебраическими выражениями в двух алгебрах {B1B3} и {B1B3}.

Лемма 6. Аксиома полного накопления.

Если R – схема и X, Y, Z, V $\overrightarrow \subset $ R , то XY и ZVX ∪ (Z\Y)YV.

Утверждение леммы 6 после ее доказательства становится аксиомой вывода

                                                    XYX ∪ (Z\Y)YVZV.                                                           (5.1)

5.1. Операция полного накопления ▶. Любую зависимость можно подвергнуть воздействию унарного правила вывода F2 (пополнение), изменяющего ее левую часть. В результате получим более слабую зависимость в том смысле, что обратного хода F2 не дает. Для нетривиального же преобразования начал функциональных зависимостей в нашем распоряжении остается только правило, представленное леммой 6 и являющееся легким усилением аксиом B2 и F6 (см. (3.2)).

По сути правило вывода (5.1) определяет на зависимостях алгебраическую операцию ▶, формализация которой дается ниже с помощью подсхем X, Y, Z, U, W| $\overrightarrow \subset $ R и зависимостей Фi$\overrightarrow \subset $ $2_{ \to }^{R}$2R|i ∈ [1, k] |k ∈ 1 ++.

Определение 19 (важно!). Операция полного накопления.

Ф1 ▶ Ф2$\Phi _{1}^{H}$ ∪ ($\Phi _{2}^{H}{\backslash }\Phi _{1}^{K}$)($\Phi _{1}^{K} \cup \Phi _{2}^{K}$).

Лемма 7. Алгебраические свойства операции ▶ полного накопления:

1) некоммутативность (имеется в виду общий случай),

2) ассоциативность 2(Ф1 ▶ Ф2) ▶ Ф3 = Ф1 ▶ (Ф2 ▶ Ф3),

3) идемпотентность Ф ▶ Ф = Ф,

4) сверх-идемпотентность.

Идемпотентность операции ▶ обобщается на случай, когда в “произведении” Ф1 ▶ Ф2 ▶ … ▶ Фk есть совпадающие “сомножители”. Пусть к примеру Фp = Фq для некоторых p, q ∈ [1, k ] |((k∈ ℤ+ и p < q)), тогда

Ф1 ▶ … ▶ Фq –1 ▶ Фq ▶ Фq +1 ▶ Фk = Ф1 ▶ Фq –1 ▶ Фq +1 ▶ Фk.

Обозначение 16. Замыкание ${{\mathbb{F}}^{\blacktriangleright }}$ множества $\mathbb{F}$ $\overrightarrow \subset $ $2_{ \to }^{R}$2R операцией ▶.

Для отображения f: [1, k ] → $\mathbb{F}$|k ∈ 1++ введем временное обозначение

Ф〈f, k〉 ≔ f(1) ▶ f(2) ▶ f(k).

Ассоциативность операции ▶ допускает возможность произвольной группировки сомножителей в правой части, а ее сверх-идемпотентность позволяет ограничиться только инъективными отображениями f. На основе Ф〈f, k〉 определим замыкание ${{\mathbb{F}}^{\blacktriangleright }}$ : ${{\mathbb{F}}^{\blacktriangleright }}$ ≔ {Ф〈f, k|k∈ ℤ+, f${{\mathbb{F}}^{{[1,k]}}}$} (важно!).

При этом будем полагать Ф〈f, 0〉 ≔ {∅∅}. Поскольку $\mathbb{F}$ ≡ Ф〈f, 1〉 , то $\mathbb{F}$${{\mathbb{F}}^{\blacktriangleright }}$. Иначе говоря, замыкание ${{\mathbb{F}}^{\blacktriangleright }}$ является расширением исходного множества зависимостей $\mathbb{F}$. В силу сверх-идемпотентности операции накопления можно написать: ${{\mathbb{F}}^{\blacktriangleright }}$ ={Ф〈f, k|k ∈ [0, μ($\mathbb{F}$)], f$\mathbb{F}$[1, k ] и f – инъективно} (важно!).

Лемма 8. Замкнутость операции ▶ в замыкании $\mathbb{F}$FB:

$\mathbb{F}$ $\overrightarrow \subset $ $2_{ \to }^{R}$2R$\mathbb{F}$${{\mathbb{F}}^{\blacktriangleright }}$${{\mathbb{F}}^{{{\mathbf{FB}}\blacktriangleright }}}$ = ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$.

5.2. Алгебраическая интерпретация аксиом вывода.

Лемма 9. Алгебраизация сверх-плотного AP-вывода 𝒜:

𝒜 ∈ {$\mathbb{F}$ $\mathop \Rrightarrow \limits^{{\mathbf{AP}}} $} и (см. обозначение 15) 𝒜 = ⇒ max𝒜 ∈ ${{\mathbb{F}}^{{\blacktriangleright {\mathbf{F3}}}}}$ ≔ (${{\mathbb{F}}^{\blacktriangleright }}$)B3.

Теорема 6. Алгебраизация полного накопления.

Каждую последовательность вывода можно ФЭ-заменить алгебраическим выражением алгебры {$2_{ \to }^{R}$2R; B1B3} и обратно. Формально (важно!)

((${{\mathbb{F}}^{{{\mathbf{B1}}}}}{{)}^{\blacktriangleright }}$)B3 ${{\mathbb{F}}^{{{\mathbf{B1}}\blacktriangleright {\mathbf{B3}}}}}$${{\mathbb{F}}^{{{\mathbf{FB}}}}}$|$\mathbb{F}$$2_{ \to }^{R}$2R.

Доказательство. Тождество ≡ логически разобьем на ⊆ и ⊇:

согласно лемме 8, имеем ${{\mathbb{F}}^{{{\mathbf{FB}}\blacktriangleright {\mathbf{B3}}}}}$${{\mathbb{F}}^{{{\mathbf{FB}}}}}$;

обратно. ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$ будем понимать в смысле (3.1). Доказываемое утверждение является итоговым для всей статьи и ниже расположен путь доказательства, начиная с уплотнения последовательности вывода 𝒫 $\overrightarrow \subset $ {$\mathbb{F}$ $\overrightarrow \subset $ ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$} до момента, предшествующего получению функционально эквивалентного ей алгебраического выражения.

Инструмент                    Название

Определение 16.           Уплотнение последовательности вывода.

Лемма 3.                          Сборка повторов и удаление тупиков.

Лемма 4.                          Переставляемость аксиом: B3B2B2B3.

Следствие леммы 4.     Плотный вывод можно ФЭ-привести в состояние B12B3.

Теорема 3.                       AP-декомпозиция плотного вывода 𝒫.

Определение 17.            Сверх-плотный вывод.

Теорема 4.                       Устранение исходящего гнездования.

То же, что        →            приведение плотного B2-вывода к сверх-плотному.

Теорема 5.                       ALT-редукция сверх-плотного AP-вывода.

То же, что        →            устранение в AP-выводе заходящего гнездования ФЗ.

Специальных требований к последовательности вывода 𝒫 лемма 3 не предъявляет. Каждый шаг инструментальной таблицы использует в качестве начальных те условия, которые возникают в конце предыдущего действия. Ее последняя строка предполагает замену всех конусов $\Delta _{k}^{{p - 1}}\left\langle {\left\langle \right.} \right.\Delta _{i}^{p}, \ldots ,\Delta _{j}^{p}\left. {\left. \right\rangle } \right\rangle $, из которых склеивается 𝒫 (см. теорему 3), соответствующими выражениями в алгебре {$2_{ \to }^{R}$2R; B1B3}. В множестве $\mathbb{F}$ используемых зависимостей рефлексий B1 может не быть. Их возможному возникновению в сверх-уплотненном выводе мы обязаны теореме 4, генерирующей рефлексии в случае появления F3 (аддитивность), которую необходимо транслировать на язык B-аксиом. В результате получим алгебраическое {B1B3}-выражение, имеющее значение max𝒫 ;⇒ ${{\mathbb{F}}^{{{\mathbf{B1}}\blacktriangleright {\mathbf{B3}}}}}$${{\mathbb{F}}^{{{\mathbf{FB}}}}}$.

5.3. Усечение ▹ и операции полного накопления ▶. В зависимостях XY пересечения XY неинформативны. Это можно вывести непосредственно из определения 4. В самом деле для отношения Ш и кортежей ш1, ш1$\overrightarrow \subset $ Ш импликация ш1 ⊦ (XY) = ш2 ⊦ (XY) ⇒ ⇒ ш1 ⊦ (XY) = ш2 ⊦ (XY), являющаяся как бы частью упомянутого определения, бессодержательна. С помощью проективности B3/F4 от XY можно избавиться, приведя XY к виду XY\X (в общем случае вывод XYX\AY\A не имеет место и, в частности, для AXY). Вопрос об обратимости этой процедуры для некоторой совокупности зависимостей $\mathbb{F}$|$\mathbb{F}$ $\overrightarrow \subset $ $2_{ \to }^{R}$2R решается ниже.

Определение 20. Унарная операция усечения ° (пузырь):

Ф° ≔ $\Phi _{ \to }^{H}$ФKH|Ф ∈ $2_{ \to }^{R}$2R.

Усечение ° основано на проективности B3/F4 и обладает свойством идемпотентности Ф°° ≡ Ф°, поскольку Ф°H ≡ ФH. Если $\mathbb{F}$$2_{ \to }^{R}$2R – некоторое множество зависимостей, то положим $\mathbb{F}$° ≔ ≔ {Ф° | Ф ∈ $\mathbb{F}$}.

Определение 21. Эквивалентность множеств ФЗ.

Множества зависимостей $\mathbb{F}$, $\mathbb{G}$ $\overrightarrow \subset $ $2_{ \to }^{R}$2Rэквивалентны, если ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$ = $\mathbb{G}$FB.

Обозначение 17. Эквивалентность множеств зависимостей: $\mathbb{F}$ ~ $\mathbb{G}$.

Лемма 10. Незаметность усечения в замыкании: $\mathbb{F}$$2_{ \to }^{R}$2R$\mathbb{F}$° ~ $\mathbb{F}$.

Обозначение 18. Инверсия $\overline \Theta $ зависимости Θ:

$\overline \Theta $$\Theta _{ \to }^{K}$ΘH|Θ ∈ $2_{ \to }^{R}$2R или, что то же самое, ${{\overline \Theta }^{H}}$ ≔ ΘK и ${{\overline \Theta }^{K}}$ ≔ ΘH.

Замечание 5. Для инверсии и рефлексии (см. сноску 3) используется одно и то же обозначение $\overline \blacksquare $. Они различаются по типу аргумента ■. Будьте внимательны!

Определение 22. Операция ⋗ усеченого накопления:

Ф1 ⋗ Ф2 ≔ (Ф1 ▶ Ф2)°|Ф1, Ф2$2_{ \to }^{R}$2R.

Справедливы утверждения:

1) Ф1 ⋗ Ф2∈2R$\mathop \to \limits^ \circ $ 2R (см. обозначение 8), 2) (Ф1 ⋗ Ф2)H ≡ (Ф1 ▶ Ф2)H.                                          (5.2)

Лемма 11. Вычисление усеченного накопления:

      1) Θ, Ω ∈ $2_{ \to }^{R}$2R ⇒ Θ ⋗ Ω = Θ° ∪ (Ω°\$\overline \Theta $) = Θ° ∪ (Ω°\$\overline \Theta $°)
      2) Θ, Ω ∈ ⇒ Θ ⋗ Ω = Θ ∪ (Ω\$\overline \Theta $)

Лемма 12. Незаметность усечения операндов в усеченном накоплении:

1) Ф1, Ф2$2_{ \to }^{R}$2R$\Phi _{1}^{ \circ }$$\Phi _{2}^{ \circ }$ ≡ Ф1 ⋗ Ф2,

2) Ф1 ⋗ Ф2 ⋗ … ⋗ Фk ≡ (Ф1 ▶ Ф2 ▶ … ▶ Фk)°.

Определение 23. Операция накопления ▹:

Θ ▹ Ω ≔ Θ ∪ (Ω\$\overline \Theta $) ≕ Ω ◃ Θ|Θ, Ω ∈ $2_{ \to }^{R}$2R.

Лемма 13. Алгебраические свойства операций накопления ⋗ и ▹:

1) некоммутативность,

2) ассоциативность1εФ2)εФ3 = Ф1ε(Ф2εФ3)|ε ∈ {▹⋗},

3) идемпотентность Ф ▶ Ф = Ф|ε ∈ {▹⋗},

4) сверх-идемпотентность

Ф1ε…εФq –1εФqεФq +1ε εФk = Ф1ε εФq –1εФq +1ε εФk|ε∈{▹⋗}.

Примечание. Свойства леммы 13 однозначно соответствуют лемме 7.

Лемма 14. Прочие свойства операций ⋗ и ▹:

1) операция усеченного накопления ⋗ замкнута на множестве разделяющихся зависимостей, что следует из утверждения 1 (5.2) и подтверждено леммой 11;

2) операции ⋗ и ▹ определены на $2_{ \to }^{R}$2R и совпадают на : Θ ⋗ Ω = Θ° ▹ Ω° |Θ,Ω ∈ $2_{ \to }^{R}$2R;

3) если Θ, Ω ∈ $2_{ \to }^{R}$2R, то:

(Θ ⋗ Ω)H ≡ (Θ ▹ Ω)H ≡ (Θ ▶ Ω)H ⇐; определения 19, 22, 23.

(Θ ⋗ Ω)K ⊆ (Θ ▹ Ω)K⊆(Θ ▶ Ω)K ⇐; то же и лемма 11;

4) взаимодействие рефлексии с однотипной ФЗ:

$\overline Z $ ⋗ (ZU) = Z(U\Z)|ZR и  $\overline Z $ ▷ (ZU)=Z(UZ)|ZR.

Лемма 8*. Замкнутость операции ε $\overrightarrow \subset $ {▹⋗} в замыкании ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$ (см. лемму 8): $\mathbb{F}$ $\overrightarrow \subset $ $2_{ \to }^{R}$2R$\mathbb{F}$ ⊆ ⊆ ${{\mathbb{F}}^{\varepsilon }}$${{\mathbb{F}}^{{{\mathbf{FB}}\varepsilon }}}$ = ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$.

Теорема 6* (важно!). Алгебраизация накопления (см. теорему 6).

Каждую последовательность вывода можно ФЭ-заменить алгебраическим выражением алгебры {$2_{ \to }^{R}$2R; B1 B3} и обратно:

((${{\mathbb{F}}^{{{\mathbf{B1}}}}}$))B3 ${{\mathbb{F}}^{{{\mathbf{FB}}}}}$|$\mathbb{F}$$2_{ \to }^{R}$2R.

Заключение. Теоремы 6 и 6* завершают решение задачи, поставленной в ДЕКЛАРАЦИИ разд. 3.3. Здесь мы кратко опишем те средства, которые были использованы для достижения полученных результатов и которые в силу объемности не получили отражения в настоящей работе.

Логика. Построение аппарата силлогизмов, позволившего автоматизировать доказательства утверждений (леммы, теоремы и пр.). Накоплена коллекция логических схем, построенных из силлогизмов и дополняющая ранее построенные графы вывода в [13, 14]. С нашей точки зрения это крайне необходимо для осмысления понятий, связанных с искусственным интеллектом.

Теория алгоритмов. Алгоритмы работы некоторой “примитивной” вычислительной машины (ВМ) заменены функционально эквивалентными им алгебраическими выражениями, т.е. дающими тот же результат, что и алгоритмы.

Установлены интересные факты перестройки связей в ЧУМ’ах, что имеет также отношение к предыдущему абзацу. Построен механизм синтеза так называемых “острых” ЧУМ на основе использования теоремы Цермело [12, Гл. 1, § 6, п. 3, с. 27] о возможности полного упорядочения множеств и развития теоремы Шпильрайна [15] о вложимости ЧУМ во вполне упорядоченное множество. Введено понятие КУМ, позволившее на абстрактном уровне осуществлять гигиену алгоритмов, поскольку они являются КУМ’ами.

Универсальные алгебры. Для ранее упомянутой ВМ построена алгебра, позволяющая заменить алгоритмы алгебраическими выражениями на принципах ФЭ.

Список литературы

  1. Codd E.F. A Relational Model of Data for Large Shared Data Banks // Comm. ACM. 1970. V. 13. № 6. P. 377–387.

  2. Codd E.F. Extending the Database Relational Model to Capture More Meaning // ACM Trans. on Database Systems. 1979. № 4. P. 397–434.

  3. Heath I.J. Unacceptable File Operation in Relational Database // Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control. San Diego, California, 1971.

  4. Ульман Дж. Базы данных на Паскале. М.: Машиностроение, 1990.

  5. Поморцев Л.А. Алгебраическая интерпретация полноты аксиом вывода // Фундамент. и прикл. матемематика. 2002. Т. 8. Вып. 1. С. 195–219.

  6. Поморцев Л.А. Алгебры функциональных зависимостей в теории реляционнных баз данных // Тр. Института системного анализа РАН. Динамика неоднородных систем. 2007. Т. 29(1). Вып. 11. С. 169–183.

  7. Мейер Д. Теория реляционных баз данных. М.: Мир, 1987.

  8. Дейт К.Дж. Введение в системы баз данных. М., СПб., Киев: Изд. дом “Вильямс”, 2001.

  9. Хаусдорф Ф. Теория множеств. М., Л.: Главная редакция технико-теоретической литературы ОНТИ, 1937.

  10. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

  11. Кон П. Универсальная алгебра. М.: Мир, 1968.

  12. Курош А.Г. Лекции по общей алгебре. М.: Физматгиз, 1962.

  13. Поморцев Л.А. Вычисление моментов порядковых статистик последовательных сумм симметрически зависимых случайных величин // Тр. Московского математического общества. 1983. Т. 46. С. 201–242.

  14. Поморцев Л.А. Комбинаторно-симметрический анализ многомерных случайных блужданий // Дискретная математика. 1991. Т. 3. Вып. 1. С. 21–41.

  15. Szpilrajn E. Sur L’extension de L’ordre Partiel // Fundamenta Mathematicae. 1930. V. 16. P. 386–389.

Дополнительные материалы отсутствуют.