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

МАССОВАЯ ОБРАБОТКА 

ДАННЫХ

АЛГЕБРАИЧЕСКИЕ  
МОДЕЛИ И МЕТОДЫ

В.И. МУНЕРМАН

МОНОГРАФИЯ

Москва 
ИНФРА-М 

2023

УДК 519.61(075.4)
ББК 22.192
 
М90

Мунерман В.И.

М90  
Массовая обработка данных. Алгебраические модели и методы : 

монография / В.И. Мунерман. — Москва : ИНФРА-М, 2023. — 
229 с. — (Научная мысль). — DOI 10.12737/1906037.

ISBN 978-5-16-018035-9 (print)
ISBN 978-5-16-111050-8 (online)
Монография посвящена математической и алгоритмической поддержке 

массовой обработки данных на основе алгебраических моделей. Рассматривается 
один из самых распространенных классов массовой обработки – обработка 
высокоактивных структурированных данных. Анализируются построение 
алгебраических моделей данных и вычислений и методы доказательства их 
соответствия. Изучаются три алгебраические системы, которые могут быть 
использованы и как модели данных, и как модели вычислений. Исследуются 
алгебраический и аксиоматический методы доказательства соответствия этих 
моделей. Дается доказательство их соответствия: гомоморфизма и изоморфизма. 
Поднимается проблема оптимизации процессов массовой обработки данных, 
представленных в виде алгебраических выражений в предложенный алгебрах-
моделях. Подробно описываются алгоритмы синтеза и оптимизации вычисления 
этих выражений, метод симметричного горизонтального распределения 
данных, обеспечивающий параллельную реализацию вычисления алгебраических 
выражений и обобщение блочного алгоритма параллельного умножения 
матриц на случай умножения многомерных матриц. Предлагаются архитектуры 
программно-аппаратных комплексов для эффективной параллельной реализации 
операций в рассмотренных алгебрах-моделях. Приводится ряд реальных 
примеров, иллюстрирующих применение предложенных методов.

Для студентов, аспирантов и преподавателей технических и физико-математических 
вузов и факультетов.

УДК 519.61(075.4)

ББК 22.192

Р е ц е н з е н т ы:

Борисов В.В., доктор технических наук, профессор, профессор кафедры 
вычислительной техники Смоленского филиала Национального 
исследовательского университета «МЭИ»;

Кононова А.И., доктор физико-математических наук, доцент, профессор 
Национального исследовательского университета «Московский 
институт электронной техники»

ISBN 978-5-16-018035-9 (print)
ISBN 978-5-16-111050-8 (online)
© Мунерман В.И., 2023

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ ................................................................................................................6

Глава 1. МАССОВАЯ ОБРАБОТКА ДАННЫХ: ОПРЕДЕЛЕНИЕ, МЕТОДЫ 
ОПИСАНИЯ, АНАЛИЗ ПРОБЛЕМ ...........................................................................9

1.1. 
Понятие массовой обработки данных  ............................................................................................9

1.2. 
Связь моделей МОД с архитектурами программно-аппаратных комплексов  .........19
1.2.1. 
Логически последовательный метод доступа  ...........................................................19

1.2.2. 
Архитектуры вычислительных комплексов для реализации логически 
последовательного метода доступа ...............................................................................22

1.3. 
Проблемы оптимизации процессов массовой обработки данных  ................................29

1.4. 
Требования к моделям массовой обработки данных  ...........................................................34

Глава 2. АЛГЕБРАИЧЕСКИЕ МОДЕЛИ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ 
ПРОГРАММНО-АППАРАТНЫХ КОМПЛЕКСОВ ................................................. 39

2.1. 
Основные алгебраические понятия ...............................................................................................39
2.1.1. 
Универсальные алгебры и алгебраические си стемы .............................................39

2.1.2. 
Интуитивный подход к объектно-ориентированному моделированию, 
проектированию и программированию .......................................................................42

2.1.3. 
Алгебраический (формальный) подход к объектно-ориентированному 
моделированию, проектированию и программированию ..................................44

2.1.4. 
Объектно-ориентированный подход к разработке моделей данных  ...........46

2.2. 
Файловая (теоретико-множественная) модель данных ........................................................52
2.2.1. 
Анализ определений файла  ...............................................................................................52

2.2.2. 
Определение файла ................................................................................................................54

2.2.3. 
Описание операций над файлами ....................................................................................56

2.3. 
Многомерно матричная модель данных ......................................................................................60
2.3.1. 
Задачи многомерно матричного представления данных.....................................60

2.3.2. 
Алгебра многомерных матриц ...........................................................................................62

2.4. 
Соответствие моделей данных  ........................................................................................................68
2.4.1. 
Соответствие теоретико-множественной и многомерно-матричной  
моделей  ........................................................................................................................................68

2.4.2. 
Соответствие промежуточных моделей данных высокоуровневым  
моделям  .......................................................................................................................................74

2.5. 
Аксиоматический подход к формализации моделей данных для МОД ........................77
2.5.1. 
Соответствие аксиоматического и алгебраического подходов 
к формализации МОД .............................................................................................................78

2.5.2. 
Определение аксиоматической теории МОД ............................................................79

2.5.3. 
Интерпретация формул аксиоматической теории МОД .......................................80

2.5.4. 
Аксиомы теории массовой обработки данных ..........................................................81

2.5.5. 
Теоремы аксиоматической теории МОД ......................................................................84

2.5.6. 
Эквивалентность моделей МОД ........................................................................................85

Глава 3. МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ МАССОВОЙ 
ОБРАБОТКИ ДАННЫХ......................................................................................... 88

3.1. 
Проблемы повышения эффективности обработки данных ................................................88

3.2. 
Синтез и оптимизация процесса МОД...........................................................................................92
3.2.1. 
Модель и метод построения процесса МОД ..............................................................92

3.2.2. 
Формальное описание метода синтеза и оптимизации процесса МОД .......95

3.2.3. 
Реализация метода синтеза и оптимизации процесса МОД ...............................99

3.3. 
Выбор параллельных алгоритмов для реализации операций МОД ............................103

3.4. 
Алгоритм параллельного умножения многомерных матриц..........................................105
3.4.1. 
Выбор алгоритма умножения многомерных матриц ...........................................105

3.4.2. 
Описание алгоритма умножения многомерных матриц ....................................109

3.5. 
Алгоритм параллельной реализации операции слияния нестрого  
упорядоченных файлов .....................................................................................................................124
3.5.1. 
Анализ алгоритмов параллельной реализации операции слияния  
нестрого упорядоченных файлов .................................................................................124

3.5.2. 
Организация данных для параллельной реализации операции  
слияния нестрого упорядоченных файлов ...............................................................126

3.5.3. 
Параллельный алгоритм реализации операции слияния нестрого 
упорядоченных файлов ......................................................................................................129

3.6. 
Алгоритм параллельной реализации операции соединения в реляционной  
модели SQL ...............................................................................................................................................139

3.7. 
Стратегия повышения эффективности процессов МОД ....................................................144

Глава 4. АРХИТЕКТУРЫ ПРОГРАММНО-АППАРАТНЫХ КОМПЛЕКСОВ 
ДЛЯ МАССОВОЙ ОБРАБОТКИ ДАННЫХ ........................................................ 146

4.1. 
Этапы построения программно-аппаратных комплексов ................................................146

4.2. 
Архитектура программно-аппаратного комплекса для реализации  
многомерно-матричной модели данных ..................................................................................148

4.3. 
Архитектуры программно-аппаратных комплексов для реализации простых 
операций теоретико-множественной модели данных .......................................................151
4.3.1. 
Параллельная реализация внешней сортировки  .................................................151

4.3.2. 
Параллельная реализация операций выборки, слияния строго 
упорядоченных файлов и сечения ...............................................................................155

4.4. 
Параллельная реализация операции слияния нестрого упорядоченных  
файлов в теоретико-множественной и реляционной моделях данных.....................157
4.4.1. 
Параллельная реализация операции слияния нестрого  
упорядоченных файлов алгоритмом черпака .........................................................159

4.4.2. 
Параллельная реализация последовательности операций слияния  
нестрого упорядоченных файлов  ................................................................................163

4.4.3. 
Параллельная реализация операции слияния нестрого упорядоченных 
файлов с использованием ассоциативных вычислительных си стем ...........165

Глава 5. ЭКС ПЕ РИМЕНТАЛЬНЫЙ АНАЛИЗ ПРОГРАММНО-АППАРАТНЫХ 
РЕАЛИЗАЦИЙ МАССОВОЙ ОБРАБОТКИ ДАННЫХ ....................................... 169

5.1. 
Анализ параллельной реализации операции умножения многомерных  
матриц ........................................................................................................................................................169

5.2. 
Анализ параллельной реализации операции слияния нестрого  
упорядоченных файлов  ....................................................................................................................171

5.3. 
Анализ параллельной реализации операции слияния нестрого  
упорядоченных файлов средствами СУБД и SMP-архитектуры .....................................171

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

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

5.6. 
Анализ параллельной реализации операции слияния нестрого  
упорядоченных файлов с использованием SMP-архитектуры и многоядерных 
графических процессоров ...............................................................................................................181

Глава 6. ПРИМЕНЕНИЕ АЛГЕБРАИЧЕСКОГО ПОДХОДА ДЛЯ РЕШЕНИЯ 
ПРИКЛАДНЫХ ЗАДАЧ ....................................................................................... 183

6.1. 
Использование предложенного метода для решения задач о кратчайшем  
пути ..............................................................................................................................................................183
6.1.1. 
Решение традиционной задачи ......................................................................................183

6.1.2. 
Решение задачи с одновременным построением пути ......................................187

6.2. 
Использование предложенного метода для решения задачи вывода 
ассоциативных правил .......................................................................................................................195

6.3. 
Использование предложенного метода для решения задачи поиска  
изображений в базах данных  ........................................................................................................199
6.3.1. 
Архитектура программно-аппаратного комплекса для поиска  
изображений в базах данных  .........................................................................................199

6.3.2. 
Параллельное сравнение ключей изображений ...................................................202

6.3.3. 
Реализация и анализ метода поиска изображений в базе данных ...............204

6.4. 
Реализация алгоритма шифрования Хилла на основе алгебры многомерных 
матриц ........................................................................................................................................................207
6.4.1. 
Краткое описание алгоритма шифрования Хилла ................................................207

6.4.2. 
Дополнительные элементы алгебры многомерных матриц  ...........................208

Заключение ........................................................................................................ 214

Список использованной литературы ........................................................... 215

ВВЕДЕНИЕ

В книге рассматриваются математическая и алгоритмическая 

поддержка массовой обработки данных на основе алгебраических 
моделей. Традиционно массовую обработку данных связывают 
с параллельными вычислениями и чаще всего определяют сле-
дующим образом: массовая параллельная обработка — способ па-
раллельной обработки больших объемов данных большим числом 
процессоров. В настоящее время массовую обработку данных свя-
зывают с направлением, получившим название Big data. Big data 
(большие данные) — общий термин, который обозначает вновь 
создающиеся структурированные, неструктурированные и полу-
структурированные данные сверхбольших и постоянно возрас-
тающих объемов. Загрузка неструктурированных и полуструктури-
рованных данные в обычную (например, реляционную) базу данных 
и последующая обработка требуют слишком больших затрат ре-
сурсов вычислительных комплексов. Поэтому книга посвящена 
рассмотрению одного самого распространенного из классов мас-
совой обработки — обработке высокоактивных структурированных 
данных. Высокая активность данных означает, что при выпол-
нении операций над данными в обработку включается их большая, 
близкая к ста процентам. 

Большие данные (Big data) — не только неотъемлемая часть 

современного мира обработки данных, но и основная его часть. 
Комплекс сложных научно-технических проблем, связанных с ре-
шением задач на основе обработки больших данных, при переходе 
к информационному обществу не только сохраняет, но и усиливает 
свою актуальность. Об этом свидетельствуют интенсивные на-
учные исследования в области баз данных, проводимые в России 
и за рубежом.

Требования к обработке больших данных существенно влияют 

на технологию разработки программных и аппаратных вычисли-
тельных средств, ее реализующих. Решение сложных вычисли-
тельных задач [1–3], информационно-логических задач, к которым 
относятся обработка транзакционных запросов и запросов, тре-
бующих больших рабочих нагрузок [4, 5], а также задач в области 
искусственного интеллекта [6, 7], таких как переобучение свер-
точных нейронных сетей [8, 9], обусловили необходимость исполь-
зования параллельной обработки и обработки в основной (опера-
тивной) памяти. Важное значение в обработке больших данных 

имеют параллельные и распределенные базы данных [10], для 
которых создаются специализированные программно-аппаратные 
комплексы — машины баз данных. 

При разработке параллельных вычислительных си стем особую 

роль играет повышение эффективности реализации отдельных 
операций, имеющих большую вычислительную сложность, о чем 
свидетельствуют многие публикации, например, [11–15]. К этим 
операциям относятся такие, как многомерное дискретное преобра-
зование Фурье, свертки в процессе обучения нейронных сетей, опе-
рация Join в реляционных си стемах баз данных.

Современные аппаратные средства, такие как многопоточные 

процессоры архитектур, подобных x86 и ARMv8, а также графи-
ческие процессоры и ускорители, позволяют проектировать парал-
лельные вычислительные си стемы, которые обеспечивают решение 
многих из перечисленных задач [16, 24]. Важное направление осно-
вано на использовании современных программируемых логических 
интегральных схем (ПЛИС/FPGA). Относительная простота прог-
раммирования [25, 26] позволяет использовать их для решения как 
вычислительных, так и информационно-логических задач, и со-
здания центров обработки данных (Data Center) [27–30]. Особую 
роль современные ПЛИС играют в решении проблемы построения 
быстро реконфигурируемых вычислительных си стем [31]. Так, 
в машине баз данных IBM Netezza [32] ПЛИС позволяет быстро 
перестраивать процессор обмена и подготовки данных S-Blade, 
превращая его в специализированный процессор для выполнения 
конкретного запроса, полученного от случайного пользователя.

Рассмотренные важные задачи требуют для своего решения по-

строения программно-аппаратных комплексов, основное свойство 
которых заключается в достижении эффективного баланса прог-
раммного и аппаратного обеспечения [33, 34]. Эта эффективность 
достигается тогда, когда, как сказано в [35]: «Для всех конкретных 
параллельных вычислительных си стем степень согласованности 
структуры алгоритмов с архитектурой си стем играет самую важную 
роль в достижении наивысших скоростей». Формальная постановка 
этой проблемы предложена в [36]: «Одним из основных источников 
задач при кладной теории алгоритмов является проблема оптималь-
ного перевода с одного языка на другой, которая может быть сфор-
мулирована сле дующим образом: существуют два алгоритмических 
языка и некото рый алгоритм, написанный на одном из них; требу-
ется найти опти мальную по заданным критериям реализацию этого 
алгоритма на другом языке. В программировании обычно первым 
является некото рый язык программирования, ориентированный 

на тот или иной круг задач, а вторым — внутренний язык машины, 
на которой ре шаются данные задачи.

Поиск причин возникновения трудностей при решении задач 

на вычислительной технике параллельной архитектуры неизбежно 
приводит к выводу, что как истоки этих причин, так и пути их 
преодоления надо искать в математических знаниях об алго-
ритмах».

Эти две посылки позволяют сделать заключение, состоящее 

в следующем:

Алгебраическая си стема, в которой формализована решаемая 

задача, и модель вычислений (алгебраическая си стема, реализо-
ванная в си стеме команд вычислительной си стемы или комплекса) 
должны в наибольшей степени соответствовать друг другу. Эти 
алгебраические си стемы должны быть по крайней мере гомо-
морфными, в идеальном случае, когда достигается полное соответ-
ствие — изоморфными.

Для обработки больших данных традиционно используется мас-

совая обработка данных (massively data processing, massively data 
computing) — способ параллельной обработки больших объемов 
данных большим числом процессоров [37, 38]. Для ее реализации 
проектируются и используются специализированные программно-
аппаратные комплексы [39–41]. 

Область, в которой применение массовой обработки данных 

имеет важное значение — это обработка высокоактивных данных. 
Активность данных определяется отношением числа обращений 
элементу данных (записи файла, элементу матрицы, строки 
таблицы) к общему числу обращений к информации (файлу, 
матрице, базе данных) в единицу времени [42, 43].

В соответствии со сказанным монография содержит под-

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

Глава 1 

МАССОВАЯ ОБРАБОТКА ДАННЫХ: 

ОПРЕДЕЛЕНИЕ, МЕТОДЫ ОПИСАНИЯ,  

АНАЛИЗ ПРОБЛЕМ

1.1. ПОНЯТИЕ МАССОВОЙ ОБРАБОТКИ ДАННЫХ 

Традиционно массовую обработку данных связывают с парал-

лельными вычислениями и чаще всего определяют следующим 
образом: массовая параллельная обработка — способ параллельной 
обработки больших объемов данных большим числом процес-
соров. В настоящее время массовую обработку данных связывают 
с направлением, получившим название Big data. Big data (большие 
данные) — общий термин, который обозначает вновь создаю-
щиеся структурированные, неструктурированные и полуструк-
турированные данные сверхбольших и постоянно возрастающих 
объемов; загрузка их в обычную (например, реляционную) базу 
данных и последующая обработка требуют слишком больших за-
трат ресурсов вычислительных комплексов. В работе рассматри-
вается один из классов массовой обработки — обработка структу-
рированных данных. 

Исторически обработка структурированных данных — один 

из самых ранних классов обработки. Первые математические (ал-
гебраические) модели для него появились еще в начале 60-х годов 
ХХ века и в конечном счете привели к современным реляционным 
и объектным моделям данных. Технологические решения также 
развивались в основном применительно к обработке структури-
рованных данных. К числу таких решений можно отнести фор-
мализацию методов доступа к данным. Разделение их на последо-
вательный, индексный и индексно-последовательный позволило 
существенно повысить производительность вычислительных ком-
плексов, так как метод доступа определялся характером решаемой 
задачи. Это позволяло выбирать наиболее эффективный алгоритм 
обработки данных для каждой операции из последовательности 
операций, приводящих к решению прикладной задачи. Далее 
в работе речь будет идти только о массовой обработке структу-
рированных данных, поэтому под термином «массовая обработка 
данных» (МОД) будет пониматься только обработка структуриро-
ванных данных.

Традиционно МОД широко используется для решения многих 

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

 
• оперативная статистическая обработка экс пе риментальных 

данных, таких как виброзащитные характеристики, оперативно 
получаемые в ходе летных испытаний [44];

 
• в банковской сфере, задача «Операционный день банка» требует 

ежедневной обработки от 40 до 90% всей базы данных банка [45, 
46];

 
• ежедневные задачи учета и планирования производства в совре-

менных си стемах управления (стандарты ERP [47, 48]), при ре-
шении которых процент обрабатываемых данных всегда близок 
к 100;

 
• задачи статистического анализа и синтеза подси стем послепро-

дажного обслуживания в си стемах интегрированной логисти-
ческой поддержки наукоемкой продукции [49].
Таким образом, особенность этих классов задач заключается 

в том, что:

1) при их решении в обработку включаются практически все 

данные, характеризующие объекты этих задач;

2) объемы обрабатываемых данных очень велики, то есть можно 

утверждать, что они (эти классы) относятся к области исследований, 
связанной с обработкой данных больших объемов (Big data).

В работе рассматривается такая разновидность МОД, которая 

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

Далее предполагается, что используемые и обрабатываемые 

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

Обычно СУБД опирается на файловую си стему, присущую 

конкретному вычислительному комплексу или операционной системе [
50]. Файловая си стема обеспечивает функции управления 
данными, хранимыми в файлах во внешней памяти. Эти данные организуются 
с использованием различных методов доступа, которые 
трактуются как совокупность соглашений о способах размещения 
данных некоторого типа в пространстве памяти, поиска требуемых 
экземпляров и выполнения над ними операций навигации, выборки 
обновления и удаления [51]. Однако при работе с СУБД методы 
управления файлами, определяющие способы их организации и доступа 
к отдельным записям, уходят на второй план, становятся не-
видимыми для программистов, разрабатывающих запросы к базе 
данных. Это приводит к тому, что способы повышения эффектив-
ности обработки данных (оптимизация запросов) перестают быть 
инструментами прикладного программиста и становятся преро-
гативой программистов, разрабатывавших СУБД. Это подтверж-
дается такими стандартными определениями запроса, как: 

 
• вопроса, затрагивающего те или иные аспекты информации, хра-

нящейся в базе данных, и модификации средствами языка за-
проса или языка манипулирования данными [52]; 

 
• сообщения конечного пользователя или приложения, направ-

ляемого СУБД и активизирующего в си стеме баз данных дей-
ствия, обеспечивающие выборку, вставку, удаление или обнов-
ление указанных в нем данных [51].
Частичные решения, дающие прикладному программисту неко-

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

Поэтому цели изложения, направленные на повышение эффек-

тивности МОД, определяются следующим образом:

1) разработка моделей данных, обеспечивающих наибольшее 

соответствие существующим моделям данных и архитектурам вы-
числительных комплексов;

2) разработка на основе этих моделей способов организации 

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

На основе сказанного можно сформулировать основные пред-

положения и определить (пока нестрого) понятия, в наибольшей 
степени соответствующие заявленным целям:

1) данные хранятся в базе данных (БД) и управляются си-

стемой управления базами данных (СУБД);

2) модель данных и способ их организации, присущие кон-

кретной СУБД, не влияют на характер выборки в процессе выпол-
нения операций;

3) данные извлекаются из базы в виде поименованных упоря-

доченных последовательностей однотипных агрегатов, содержащих 
сведения об однородных объектах;

4) в дальнейшем для этих последовательностей будет исполь-

зоваться (в соответствии с традицией) название файлы, а для агре-
гатов — записи;

5) предполагается, что время выборки данных из базы в файл 

минимально (на практике оно определяется свойствами СУБД).

Вовлеченность большинства записей в обработку можно выра-

зить количественно при помощи величины, называемой коэффици-
ентом активности файла. Пусть L — общее число записей в файле, 
Le — число записей того же файла, подвергающихся обработке 
в процессе выполнения операции над этим файлом.

Отношение 
=
e

a

L
K
L  называется коэффициентом активности 

файла. Коэффициент активности определяет метод доступа 
к файлу. Если он высокий — близок к единице, то более эффек-
тивным будет последовательный доступ к файлу, в противном 
случае, когда он близок к нулю, целесообразно использовать произ-
вольный доступ.

Таким образом, основное свойство МОД состоит в том, что 

коэффициенты активности всех обрабатываемых файлов близки 
к единице.

Реализация МОД осуществляется посредством обработки 

файлов специальным набором операций. Причем этот набор опе-
раций не меняется на протяжении длительного периода времени, 
от конца пятидесятых годов ХХ века до настоящего времени. Одним 
из наиболее эффективных подходов к формализации был подход, 
основанный на создании алгебры файлов [53, 54]. При таком под-
ходе файл рассматривается как самостоятельный объект, обла-
дающий набором присущих ему специфических свойств, суще-

ственно используемых при формализации операций и разработке 
алгоритмов, реализующих эти операции. В [53] формализуется 
понятие ключа как неотъемлемого свойства файла, а в [54] файлы 
и операции классифицируются в соответствии со свойствами за-
данных на них ключей. Такой подход имеет ряд преимуществ 
перед появившемся несколько позже, но завоевавшем исключи-
тельную популярность реляционным подходом [55]. Одно из этих 
преимуществ состоит в том, что файл определяется и рассматри-
вается в контексте операций не как множество, подобно тому, как 
это делается в реляционном подходе при определении отношения, 
а как производный от множества объект, что позволяет избежать 
использования громоздкого аппарата нормализации. Второе пре-
имущество заключается в том, что формализация файлов и опе-
раций над ними позволяет создавать процедурные модели данных, 
в которых определения операций одновременно задают способы 
представления данных и алгоритмы их обработки. Вместе с тем оба 
подхода не только не противоречат друг другу, но и взаимно до-
полняют друг друга, что особенно важно в настоящее время, когда 
объектно-ориентированный подход к обработке данных, наиболее 
естественный с математической точки зрения, стал преоблада-
ющим. Поэтому, а также в силу популярности реляционного под-
хода и производных от него, в дальнейшем при описании представ-
ления данных и операций над ними будут приводиться их аналоги 
в реляционной (SQL) модели.

Далее приводится неформальное описание операций над фай-

лами в МОД, строгое определение которых будет дано в после-
дующих главах.

1. Сортировка. Упорядочивает файл в соответствии с неко-

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

2. Выборка. Выбирает из файла записи, соответствующие за-

данному критерию. В реляционной модели ей соответствует опе-
рация Select.

3. Сжатие. Операция квантификации. Заменяет несколько 

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