автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка методов организации вычислительного процесса при обработке данных, описываемых реляционной моделью

ВВВДЕНИЕ.

ГЛАВА I. Анализ процессов обработки данных, описываемых реляционной моделью

1.1. Уровни представления данных

1.2. Общее определение реляционной модели данных и ее свойств.

1.3. Анализ внутреннего уровня представления данных.

1.3.1. Структура внутреннего уровня.

1.3.2. Представление уровня хранения совокупностью способов организации данных

1.3.3. Представление уровня хранения обобщенной моделью данных.

1.3.4. Аппаратная реализация уровня хранения

1.4. Организация обработки данных в реляционных системах управления базами данных

1.5. Формулировка задач исследования.

1.6. Ейводы по первой главе

ГЛАВА 2. Построение и исследование модели данных уровня хранения.

2.1. Построение модели данных уровня хранения

2.1.1. Определение множества схем и операций.

2.1.2. Интерпретация операций алгебры отношений операциями уровня хранения.

2.1.3. Интерпретация выражений алгебры отношений операциями уровня хранения.

2.1.4. Полнота системы операций уровня хранения.

2.2. Оценка эффективности системы операций уровня хранения.

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

2.3.1. Способы внутреннего представления выражений алгебры отношений

2.3.2. Оптимизация выражений алгебры отношений.

2.3.3. Алгоритм преобразования выражений алгебры отношений.

2.4. Выводы по второй главе

ГЛАВА 3. Исследование инвертированного способа организации данных.

3.1. Инвертированный способ организации данных.

3.2. Анализ структуры индекса инвертированной БД.

3.2.1. Анализ структуры таблицы имен

3.2.2. Вопросы выбора способов организации таблицы имен.

3.2.3. Вопросы выбора структуры таблицы адресов. ЮО

3.2.4. Организация таблицы адресов

3.3. Оценка среднего времени обработки данных.

3.3.1. Структура запроса.

3.3.2. Характеристики оборудования.

3.3.3. Оценка времени выполнения элементарного запроса.ПО

3.3.4. Оценка времени выполнения запроса общего вида.

3.3.5. Время обработки данных

3.4. Исследование загрузки данных

3.4.1. Алгоритм загрузки.

3.4.2. Оценка времени выполнения загрузки.

3.5. Выводы по третьей главе

ГЛАВА. 4. Вопросы реализации операций алгебры отношений.

4.1. Реализация операции выборки.

4.2. Реализация теоретико-множественных операций.

4.3. Реализация операции соединения.

4.3.1. Традиционная схема выполнения операции соединения.

4.3.2. Влияние размещения отношений на накопителе на время выполнения операции

4.3.3. Влияние упорядоченности отношений на время выполнения операции соединения

4.3.4. Оценка времени доступа при реализации операции с помощью операций уровня хранения.

4.4. Выводы по четвертой главе

ГЛАВА 5. Практическое применение полученных результатов.

5.1. Использование разработанных средств в СУБД АДОНИС.

5.2. Реализация инвертированного способа организации данных.

5.2.1. Структура инвертированной БД

5.2.2. Схема выполнения инвертирования

5.2.3. Обработка данных инвертированной БД.

5.3. Пример практического применения.

5.4. Выводы по пятой главе.

В решениях ХХУ1 съезда КПСС, на июньском пленуме ЦК КПСС 1983 года большое внимание уделено вопросам повышения эффективности использования и широчайшего применения вычислительной техники в управлении, автоматизации и проектировании производства, научных исследованиях и других областях. Совершенствование процессов обработки данных в вычислительной системе (ВС) является одним из путей успешного решения поставленной проблемы, так как обеспечивает полноту использования возможностей, предоставляемых техническими средствами ВС, повышает производительность систем обработки данных (СОД), функционирующих в рамках ВС [67, 7, 30j .

Проблема организации эффективного управления процессом обработки данных и ресурсами ВС затрагивает вопросы разработки программного обеспечения для организации и управления вычислительным процессом(ВП). Методы организации ВП, понимаемые как совокупность организационных, программных, технологических, технических мероприятий [67, 45] , должны обеспечивать универсальность процессов обработки данных. Из комплекса задач, которые необходимо решить для этой цели [67] , выделим задачи: I) обеспечение возможности анализа и оценки процесса обработки данных на его различных этапах; 2) эффективное использование ресурсов ВС. Итог их решения -повышение скорости обработки данных, снижение затрат на их обработку.

Широкое применение получил в настоящее время подход к реализации СОД на основе структур данных, описываемых реляционной моделью [102, 16, 73, 74] . Подход характеризуется: I) ПРостотой модели данных, естественным для пользователя-непрограммиста способом представления данных - в виде отношений, которые можно рассматривать как двумерные таблицы; 2) наличием мощных средств манипулирования данными [102, 21, 62, IIj .

В СССР и за рубежом развитию теории структур данных, описываемых реляционной моделыо^и практическому их использованию посвящены работы многих ученых в том числе: Кодда Е., Дрибаса В.П., Кузина Л.Т., Столярова Г.К., Цаленко М.Ш., Дейта К., Мартина Дж.

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

1) Независимость реляционной модели данных от способов представления данных в памяти ВС. При использовании других известных абстрактных моделей данных - сетевой или иерархической [30, 68, 7] при описании данных требуется указание способов их взаимосвязи, которые затем используются для организации хранения данных в ВС, доступа к данным [16, 50, 59, 35] . При обработке данных, описываемых реляционной моделью, организация хранения данных в ВС и выбор пути доступа к данным не зависят от специфики прикладной задачи.

2) Низкая эффективность реализации операций обработки данных реляционной модели на традиционных последовательных машинах. По существу реляционная модель представляет собой модель ассоциативной памяти, в которой доступ к данным осуществляется по их содержимому.

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

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

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

В последнее время предложено решение ряда вопросов этой проблемы. В работах прослеживаются следующие тенденции:

1) Разработка специализированного оборудования для организации хранения и обработки данных, основанного на использовании ассоциативных процессоров [23, 122, 137 J . В силу большой стоимости таких средств результаты исследований не имеют широкого практического внедрения.

2) Разработка универсальных способов хранения данных. Этот подход носит, в основном, теоретический характер и не позволяет эффективно использовать особенности модели данных.

В связи с вышесказанным целью диссертационной работы является разработка методов организации вычислительного процесса, уменьшающих время обработки данных, описываемых реляционной моделью, и повышение эффективности использования ВС. В качестве средств обработки данных реляционной модели выбрана алгебра отношений (реляционная алгебра) [l02, 19J . Выбор алгебры отношений в качестве средств манипулирования данными объясняется: I) все другие средства обработки данных (реляционное исчисление, языки отображения) приводимы к алгебре отношений [103, 40, 21] ; 2) специализированное оборудование ориентировано на реализацию операций алгебры отношений.

В работе ставятся и решаются задачи:

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

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

3. Исследование инвертированного способа организации данных,

Лежащего в основе разрабатываемой промежуточной модели данных.

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

5. Исследование с помощью модели инвертированного способа организации данных реализации операций обработки данных промежуточной модели.

6. Разработка на ЕС ЭВМ комплекса программ, посредством которого реализуется разработанная модель данных, и внедрение его в реальные системы обработки данных.

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

- Проблема П.05.09. Целевой комплексной программы 0.Ц.027 Создать и ввести в действие первую очередь ВК с сетью терминальных станций коллективного пользования в МЭИ" Постановления ГКНТ СССР №474/250/132 от 12.12.80г.

- НИР по теме " Разработка технологии построения программного обеспечения на базе ВЦ коллективного пользования для ЭВМ третьего поколения" (регистрационный номер 78001854).

- НИР по теме " Разработка новых методов организации вычислительных процессов, обеспечивающих эффективное использование ресурсов ЭВМ и требований пользователей.

Разработка ППП, улучшающих обращение к блокам данных, обеспечение диалогового взаимодействия пользователей с ВС.Создание систем диалога "Исследователь - ЭШ".

- НИР в плане Договора 1824 о социалистическом содружестве между МЭИ (Вычислительный Центр) и Государственным научно-исследовательским институтом по промышленной и санитарной очистке газов (НИИОГАЗ).

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

Главными научными результатами являются:

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

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

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

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

Практическими результатами работы являются разработки и программная реализация: а) модели данных уровня хранения, позволяющей уменьшить время выполнения операций алгебры отношений и повысить оперативность обработки данных для класса задач; б) алгоритма преобразования реляционной модели данных в модель данных уровня хранения; в) комплекса программ, реализующих инвертированный способ организации данных для ЕС ЭМ, параметрическая универсальность которого позволяет использовать его при решении задач широкого круга; г) компоненты для оценки среднего времени доступа к данным при использовании инвертированного способа организации данных, учитывающего статистику использования атрибутов, реальные характеристики ВС; д) компоненты для выбора оптимальной стратегии доступа к данным при вычислении выражений алгебры отношений.

Разработанные средства являются параметрически универсальными. Они включены в состав диалоговой версии СУБД АДОНИС [54, 55] . Получено практическое подтверждение эффективноети результатов исследования при использовании комплекса разработанных на их основе средств в ВЦ МЭИ, НИИОГАЗ, в/ч 56020, ВНИИ "АЛЬТАИР".

По тематике исследования сделаны доклады на 3 научно-технических конференциях; основные положения диссертационной работы опубликованы в 5 статьях, 8 отчетах о НИР, 3 учебно-методических пособиях.

Текст диссертационной работы состоит из введения, 5 глав, заключения, списка литературы и приложения.

5.4. Выводы по пятой главе

1. Разработан комплекс программных средств, опробованных в рамках проекта диалоговой версии реляционной СУБД АДОНИС и включенной в состав этой системы, выполняющий функции:

- операции манипулирования данными уровня хранения;

- отображение выражений реляционной алгебры в выражение, представленное композицией операций уровня хранения;

- выбор оптимальной стратегии доступа.

2. Реализован инвертированный способ организации данных, использованный в СУБД АДОНИС и примененный автономно при решении задач обработки данных в войсковой части № 56020, в НИИ "Альтаир".

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

ЗАКЛЮЧЕНИЕ В диссертационной работе получены следующие основные результаты.

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

Исследован инвертированный способ организации данных:

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

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

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

L Получены аналитические оценки времени выполнения операций алгебры отношений посредством операций уровня хранения. Определена область изменения значений параметров, для которой <-•' 1, ■ ('/■ может быть получено ускорение выполнения операций алгебры отношений с помощью операций уровня хранения. >. На основе инвертированного способа организации данных разработан комплекс программных средств для ЕС ЭВМ, реализующий операции обработки данных уровня хранения, преобразование выражений алгебры отношений в эквивалентные выражения, представленные композицией операций уровня хранения. Все разработанные средства включены в состав диалоговой версии СУБД АДОНИС. 7. Разработанные программные средства применены при решении реальных информационно-справочных задач в НИИОГАЗ, ВЦ МЭИ, в/ч 56020 ВНИИ"АЛЬТАИР". Технический эффект от их использования получен за счет ускорения выполнения операций обработки данных.

1. Альянах И.Н, Внешние запоминающие устройства, ЕС ЭВМ,-М,:Сов, радио, 1979,-208 с.

2. Астахов А.В. Организация эффективного доступа на основе хеширования. -Программирование, 1980, $2, с, 28-33,

3. Ахо А,, Ульман Дж. Теория синтаксического анализа, перевода и компилляции. Т.2, Компилляция.-М.: Мир, 1978,- 487 с,

4. Ахо А,, Хопкрофт Дж,, Ульман Дж, Построение и анализ вычислительных алгоритмов,- М,: Мир, 1979,-536 с.

5. Бакаев А.А., Крамаренко Р.П., Коструба Г.В, Проблема независимости в СУБД ПАЛЬМА.-УСиМ, 1981, $ 4, с. 15-18,

6. Бертзисс А.Т. Структуры данных.-М.:Статистика,1974.-408с.

7. Бойко В.В., Савинков В.М. Проектирование информационной базы автоматизированной системы на основе СУБД.-М.: Финансы и статистика, 1982.- 174с.

8. Бушев С.Н., Бесфамильный М.С. Программно-аппаратные методы управления данными, М., Наука, 1982, 240 с.

9. Вейнеров О.М., Казаров М.С., Латышев М.И. Методы и средства автоматизации проектирования логических структур баз данных.-Зарубежная радиоэлектроника, 1980, Л 9, с. 33-48.

10. Виленкин С.Я., Трахтенгерц Э.А. Математическое обеспечение управляющих вычислительных машин. М.: Энергия, 1972,, 223 с.

11. Вольфенгаген В.Э., Кузин Л.Т., Саркисян В.И. Реляционные методы проектирования банков данных, Киев: Вища школа, 1979, 192 с.

12. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. Киев: Наукова думка, 1974. 328 с.

13. Грис Д. Конструирование компилляторов для цифровых вычислительных машин. М.: Мир, 1975. 543 с.

14. Дагаев Н.И., Рудзицкий"Б.Н. Банки данных.-Новое в жизни, науке,технике. Сер. Техника. М., 1979, вып.5. 64с. 5. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975, 248с.

15. Сб. Дейт К. Введение в системы баз данных. М.: Наука, 1980, 464с.

16. Джадд Д.Р. Работа с файлами. М.: Мир, 1975. 144 с.

17. Драммовд М. Методы оценки и измерений дискретных вычислительныхсистем. М.: Мир, 1977. 382 с. 9. Дрибас В.П. Реляционные модели баз данных. Мн.: изд-во ЕГУ им. В.И.Ленина, 1982. 192 с.

18. Дрибас В.П., Курскова Г.Л., Столяров Г.К. Введение в реляционные модели баз данных, йн-т математики АН БССР. Минск, 1977, 53 с.

19. Дрибас В.П., Курскова Г.Л. Анализ средств манипулирования реляционными базами данных. Ин-т математики АН БССР. Минск, 1979.64 с.

20. Евстигнеев В.А. Применение бинарных деревьев для организации больших массивов информации. В сб.: Прикладная информатика. М.: Финансы и статистика, 1981, вып. I, с. I70-2II.

21. Задыхайло И.Б., Соловьев В.В. Вопросы создания специализированного процессора для реляционных баз данных. Ин-т Прикладной математики АН СССР. М., 1979. 57 с.

22. Заикин О.А., Кацев С.Б., Советов Б.Я. Размещение файлов намагнитных дисках при проектировании баз данных. УСиМ, 1981, 7/3, с.

23. Зайцев М.Г. Реляционная однородно структурированная (несвязная) база данных. УС и М, 1982, № 6, с. 74-78.

24. Зубов B.C., Казарницкий С.Д., Цуников Ю.В. Математическое обеспечение цифровых вычислительных машин и систем. Учеб.пособие,- 4.2, М.: МЭИ, 1976. 73 с.

25. Зубов B.C., Сокурская И.Ю. О способе преобразования выражений реляционной алгебры. Тр./Моск.энерг.ин-т, 1983,вып.587,с.50-54.

26. Игнатенко Б.В., Колодко Л.В., Павловский В.И., Савченко С.Ф. Пакет прикладных программ физической организации баз данных -ППП ФОВД. УС и М, 1981, 162, с.116-120.

27. Ильинский Н.И., Мясников А.В. Система генерации программ обработки данных (РЕГББД). В сб.: Вопросы кибернетики. М., 1979,55, с. 40-45.

28. Информационные системы общего назначения /Пер. с англ. под ред. Е.Л.Ющенко. М.: Статистика, 1975. 471 с.

29. Казарицкий С.Д. Исследование вопросов построения систем управления реляционными базами данных: Автореферат канд. дисс. М.: МЭИ, 1980. 20 с.

30. Казарицкий С.Д., Овсянникова М.Р., Сокурская И.Ю. Технические приемы реализации системы управления базой данных. В кн.: Проблемы создания программного обеспечения АСУ. М., 1976, с.86-88.

31. Казарицкий С.Д., Овсянникова М.Р., Сокурская И.Ю. Системы управления базами данных. Учеб. пособие. М.: МЭИ, 1978, 24 с.

32. Калиниченко Л.А. Методы преобразования моделей данных. УС и М, 1982, № 5, с. 88-94.

33. Капп Д., Лебен Дж. Техника программирования для 1WS . Методология использования VL /I. М.: Финансы и статистика, 1983. 248 с.

34. Кнут Д. Искусство программирования, для ЭВМ. Т.З. Сортировка и поиск. М.: Мир, 1978, 847 с.

35. Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1978. 352 с.

36. Кохонен Т. Ассоциативные запоминающие устройства.'М.: Мир, 1982. 383 с.

37. Крамаренко Р.П., Скляров А.В., Лозняца Я.С. Управление памятью в системе ПАЛЬМА. В сб.: Банки данных и информационно-поисковые системы. М., 1980, с.40. 1фзин Л.Т. Основы кибернетики. Т.2. М.: Энергия, 1979. 584с.

38. Курскова Г.П., Дрибас В.П. Обзор основных реляционных языков. Ин-т математики АН БССР. Минск, 1979, 48 с.

39. Куцык Б.С. Структура данных и управление. М.: Наука, 1975. 125 с.

40. Лавров С.С., Гончаров Л.й. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971. 160 с.

41. Лебедев В.Н. Введение в системы программирования. М.: Статистика, 1975, 311 с.

42. Литвинов В.А. Некоторые методы обработки файлов в пашти прямого доступа и оценка их эффективности. УС и М, 1978, $ 5, с. 12-19.

43. Литвинов С.А., Иваненко В.И. Обобщенная функция расстановкии организации файла рандомизированной структурой. Программирование, 1980, № 5, с.31

44. Лефковиц Д. Структуры информационных массивов, . М.: Энергия, 1975, 208с.

45. Маклаков А.В. К вопросу определения функциональной зависимости между атрибутами отношений в реляционных базах данных, Программирование, 1978, $1, с.

46. Мальцев А.И. Алгебраические системы. М.: Наука, 1970, 332с.

47. Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир , i980t 664 с.

48. Мишенин А.И. Параметры, влияющие на выбор структуры данных. В сб.: Алгоритмы и организация решения экономических задач, М.: Статистика, 1979, вып. 13, с. 47-55.

49. Мультимодельная система управления базами данных МУССОВ Когаловский М.Р., Когутовский В.В., Макальский К.И., Виноградов

50. Н.М.- В сб.: Прикладная информатика. М.: Финансы и статистика, 1981, вып. I,o. 211-228.

51. Неклюдова Е.А., Цаленко М.Ш. Синтез логической схемы реляционной базы данных. Программирование, 1979, №6, с.58-68.

52. Обобщенный подход к построению автоматизированных систем обработки данных. Учеб.пособие /Казарицкий С.Д., Куликова С.А., Овсянникова М.Р., Сокурская И.Ю. М.: МЭИ, 1980. 64с.

53. Об одной системе управления базами данных /Казарицкий С.Д., Куликова С.А., Овсянникова М.Р. и др.- Тр. /Моск. Энерг.ин-т, 1979, вып. 441, с.

54. Обработка информационных массивов в автоматизированных системах управления /Гдушков В.М., Гдадун В.П., Лозинский Л.С., Погре-бинский С.Б. Киев: Наукова думка, 1970, 184с.

55. Овсянникова М.Р. Исследование способов отображения реляционной модели на память. Вычислительной системы: Автореферат канд. дисс.- М.: МЭИ, 1980, 20с.

56. Овсянникова М.Р., Пышкина С.А., Сокурская И.Ю. Представление реляционной модели данных в памяти ЭВМ. Учеб.пособие, М.: МЭИ, 1983 .1040.

57. Олле Т.В. Предложения КОДАСЩ по управлению базами данных. М.: Финансы и статистика, I98I. 286с.

58. Основные характеристики отечественных СУБД и ИШ /Под.ред.

59. A.А.Стогния. ИК АН УССР. Киев, 1980. 64 с.

60. Парницкий В.И. Об организации многоатрибутных файлов. Кибернетика, 1981, №5, с. 29-33.

61. Размыслов Ю.П. Язык VSL -d в рнляционной модели Кодда.

62. В сб.: Алгоритмы и организация решения экономический задач. М.: Статистика, 1978, вып. II, с.20-35.

63. РБГВНД реляционный подход к генерации программ обработки данных /Ильинский Н.И., Кузин Л.Т., Мясников А.В., Стрижевский

64. B.C. В сб.: Прикладная информатика. М.:Финансы и статистика,- 187 1982, вып. I, с. II4-I3I.

65. Савинков В.М., Назаров М.С., Рысевич Ю.К. Использование систем управления, базами данных в АСУ. В сб.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1979, вып. 13,с. 29-38.

66. Савинков В.М., Вейнеров О.М., Назаров М.С. Обобщенные процедуры автоматизированного логического проектирования БД. УС и М, 1981, № 4, с.

67. Система управления базами данных как инструмент построения ав-матизированных систем обработки данных /Казарицкий С.Д., Пыш-кина С.А., Сокурская И.10., Овсянникова М.Р.-Тр./Моск.энерг. ин-т, вып. 525, с.74-79.

68. Стогний А.А., Паньшин Б.Н. Программное обеспечение управления вычислительным процессом в ВЦ и сетях ЭВМ. Киев: Наукова Думка, 1983,237с.

69. Столяров Г.К, Обзор предложений рабочей группы КОДАСИЛ по базам данных. В сб.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1974, вып.4, с. 48-77.

70. Тихомиров В.П. Организация сопровождения программных средств АСУ. М.: Статистика, 1980, 60 с.

71. Ульман Дж. Основы систем баз данных. М.: Финансы и статистика,1983, 334 с.

72. Феррари Д. Оценка производительности вычислительных систем. М.: Мир, 1981, 576 с.

73. Флорес И. Структуры и управление данными. М.: Финансы и статистика, 1982, 819 с.

74. Цаленко М.Ш. Реляционные модели базы данных. В сб.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1977, вып. 9, с.18-36.

75. Цаленко М.Ш. Реляционные модели баз данных. В сб.: Алгоритмы иорганизация решения экономических задач. М.: Статистика, 1977, вып. 10, с. 16-29.ч

76. Цаленко M.II1. Организация информации и информационные инварианты. Семиотика и информатика, 1979, № 12, с.

77. Чукин Ю.В. К выбору организации файла. УС и М, 1977, №3, о. 74-78.

78. Шрейдвр Ю.А. Равенство, сходство, порядок. М.: Наука, 1971, 254с.

79. Цикритзис Д., Бернстайн Ф. Операционные системы.: Мир, 1977, 336 с.

80. Юровский Б.Ю. Методика оптимизации состава памяти и размещения информации в системах обработки данных. УС и М, 1979, № I,г

81. Aho А.V., Ullman J.D. Optimal partial match retrieval when fields are independently specified. ACM Trans, on Database Syst., 1979, v.4, n. , p.168-179.

82. Aho A.V., Sagiv Y., Ullman J.D. Egnivalences among relationalу ' . .expressions» SIAM J. on Computing, 1979» v.8, n.2, p.218-246.

83. Aho A.V., Beeri C., Ullman J.D. The theory of joins in relational databases. AOM Trans, on Database^ Syst., 1979, v.4, n.3, p.297-314.

84. ANSI/X3/ Study group on data base management systems Interim Report, ВДС, 1975, v.7, n.2.

85. Armstrong W.W. Dependency structures of database relationships. Proc. IFIP 74, North Holand, 1974, p.580-583.

86. Batory D.C., Gotlieb C.C. A Unifying model of physical databases. ACM Trans, on Database Syst., 1932, v.7, n.4, p.509-539.

87. Beeri C., Bernstein P.A., Coodman N. A Sophisticate Introduction to database normalization theory. Froc. 4 Int.Conf, on Very Large Data Bases, 1978, p.113-124.

88. Beery G., Fagin R., Howard J.H. A complite axiomatization for functional and multivalued dependencies in database relations. Proc. AOM SIGMOD Int.Conf on Manag. of Data, 1977, p.47-61.

89. Bernstein P.A. Synthesizing third normal form relations from functional dependencies. ACM Trans, on Database Sysfr., 1976, v. 1, n.4, p.277-298.

90. Berra В., Oliver E. The Role of Associative array processers in 8ata base machine architecture. Conqputer, 1979» v. 12, ^•3» p.53-61.

91. Blasgen M.W., Eswaran K.P. Storage and access in relational databases. IBM Syst. J., 1977» v.16, n.4, p.363-378.

92. Borkin S.A. Data model equivalence. Proc. 4 Int.Conf. on Very Large Data Bases, 1978, p.526&534.

93. Cardenas A.F. Analysis and performance of inverted database structures. С ACM, 1975» v. 18, n.5, p. 253-263.

94. Cardenas A.F. Evaluation of file Organization. A model and system. СACM, 1973» v.16, n.9, p.540-548.

95. Chandra A.K., Merlin P.M. Optimal incrementation of conjunctive queries in relational databases. Proc. 9 Ann. ACM Symp. on Theory of Computing, 1976, p.77-90.

96. Ohang C.C., Lee R.C.T., Du M.W. Symbolic gray code as a perfect multiattribute hashing scheme for partial match queries. IEEE Trans, on Software Engineering, 1982, v.8, ri.3, p.235-249.

97. Codd E.P. Further normalization of the data base relational model. In "Data Base Systems", Courant Computer Science Symposia Series, 6. Prentice-Hall, п., ., 1972, p.120-151.

98. Ю2. Godd E.F, A relational model of data for large shared data banks. СACM, 1970, v.13, n.6, p.377-387.

99. Codd E.I. Relational completeness of data base sublanguages. -In "Data Base Systems", Courant Congputer Science Symposia Series, 6. Prentice-Hall, п., J., 1972, p.65-98.

100. Gotlib L. Computing joinz of relations. Proc,of the ACM--SIGMOD Conf, San Jose Calif.Mag., 1975, p.53-65.112f Jakobsson M. Reducing block access in inverted files by partial clustering. Information Syst., 1980, v.5» n.1, p.1-5*

101. Haerder T. Implementing a generalized access path structure for a relational database system. ACM Trans, on Database Syst., 1978, v.3, n.3, p.285-298.

102. Hall P.A.V. Optimization of a single relational expression in relational database system. IBM J.Res. and Develop., 1976, v.2o, n.3, p.244-257.

103. Hammad P. Formulation of choice for file organization. Informations Syst., 1978, v.3, n. , p.125-130.

104. Hoffer J.A, Method for primary and secondary kfcy selection. 1980, p.

105. Hsiao D., Harary F. A formal system for information retrieval from file® v- С ACM, 1970, v.13, n.2, p.67-73,

106. Kerschberg L., Tung P., Yao S.B. Query optimization in star computer networks. ACM Trans, on Database Syst., 1982, v.7, n.4, p,678-711.

107. Kim W# Relational database systems. AOM Com.Surv., 1979» v.11, n.3, p.185-211.

108. King A. Calculating constraints on relational expressions. -ACM.Trans, on Database Syst., 1980, v.5, n.3, p.260-290.

109. Lin W.C., Lee R.C.T., Du, H.C. Common properties of some multi-attribute file systems. IEEE Trans, on Software Engeniering, 1979, v.5, n.2, p.160-174.

110. Liu J.W., Jino M. Intelligent magnetic bubble memories and their application in data base management systems. IEEE Trans, on Computing, 1979, v.28, n.12, p.888-906.

111. Lin S.C., Smith D.P.C., Smith J.M. The design of rotationg associative memory for relational database applications. -ACM Trans, on Database Syst., 1976, v.1, n.2, p.53-75•

112. Ozkarahan E.A., Sevik K.C. Analysis of architectural features for enhancing the performance of a database machine. ACM Trans, on Database Syst., 1977, v.2, n.4, p.297-316.

113. Pelagatti G., Paolini P., Pracchi G. Mapping external view to a common data model. Information Systems, 1978, v.3, n. p.141-151.

114. Sagiv I., Yannakakis M. Equivalence among relational expressions with the union and difference operations. Proc. 4 Int. Conf. on Very Large Data Bases, 1979, p.535-543.

115. Schenk K.L., Pinker Y.R. An algorithm for servicing multi-relational queries. Proc.Int.Conf. on Management of Data, 1977, p.10-20.

116. Schkolnick M. Secondary index optimization. Proc. ACM SIGMOD, 1975, p.186-192.

117. Schkolnick M. The optimal selection of secondary indices for files, Information Systems, 1977, v.1, n.3, p.22-44.

118. Selinger P.G., Astrahan M.M., Ghamberlin D.D., Lorie R.A., Price T.G. Access path selection in a relational database system. Res.Rep. RJ2429 IBM Research San Jose, Calif., 1979,p.23-34.

119. Senko M.E. et al. Data structures and accessing in data base systems. IBM System J., 1973, v.12, n.1, p.30-95.

120. Severance D.G., Carlie Y.V. A practical approach to selecting record access path. Computing Syrveys, 1977, v.9, n.4, p.259-272.

121. Smith J.M., Chang P.Y.T. Optimizing the performance of a relational algebra database interfuce. ACM, 1975, v.18, n.10,p.568-579.

122. Smith D., Smith J. Relational database machines. Computer, 1979, v.12, n.3, p.28-38.

123. Stonebraker M., Wong E., Kreps P., Held G, The design and implementation of INGRES. ACM Trans, on Database Syst., 1976, v.1, n.3, p.189-222.

124. Strand A.J. The relational approach to the management of data bases. Broc.IFIP North Holland, 1971, p.901-904.

125. Su S. et al. Retrieval operations and data representations ina context-oidressed disk system. Proc.AGH SIGPLAN/SIGIR, 1973, p.144-160.1

126. Tanaka К et al. A file organization suitable for relational database operations. Lecture Notes in Computer Sci., N , p.193-225.139* Todd S. The Peterlee Relational Test Vehicle a system overview. - IBM Syst.J., 1976, v.15, n.4, p.285-307.

127. Whitney V.K. Relational Data Management System information systems. - Proc.of C0HTS-I7/Ed by Ton. J.T., Plenum Press, 1974, p.103-117.

128. Yao S.B. An attribute based model for database access cost analysis. ACM Trans, on Database Syst., 1977, v.2, n.1, p.45-67.

129. Yao S.B. Optimization of query evaluation algorithm. ACM Trans, on Database Syst., 1979, v.4, n.2, p.133-155.