Разработка методов организации вычислительного процесса при обработке данных, описываемых реляционной моделью
Диссертация
L Получены аналитические оценки времени выполнения операций алгебры отношений посредством операций уровня хранения. Определена область изменения значений параметров, для которой ←•' 1, ¦ ('/¦ может быть получено ускорение выполнения операций алгебры отношений с помощью операций уровня хранения. >. На основе инвертированного способа организации данных разработан комплекс программных средств… Читать ещё >
Содержание
- ВВВДЕНИЕ
- ГЛАВА 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. Выводы по второй главе
- 2. 1. Построение модели данных уровня хранения
- ГЛАВА 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. Выводы по пятой главе
- 5. 2. Реализация инвертированного способа организации данных
Список литературы
- Альянах И. Н, Внешние запоминающие устройства, ЕС ЭВМ,-М:Сов, радио, 1979,-208 с.
- Астахов А.В. Организация эффективного доступа на основе хеширования. -Программирование, 1980, $ 2, с, 28−33,
- Ахо А, Ульман Дж. Теория синтаксического анализа, перевода и компилляции. Т.2, Компилляция.-М.: Мир, 1978, — 487 с,
- Ахо А, Хопкрофт Дж, Ульман Дж, Построение и анализ вычислительных алгоритмов, — М: Мир, 1979,-536 с.
- Бакаев А.А., Крамаренко Р. П., Коструба Г.В, Проблема независимости в СУБД ПАЛЬМА.-УСиМ, 1981, $ 4, с. 15−18,
- Бертзисс А.Т. Структуры данных.-М.:Статистика, 1974.-408с.
- Бойко В.В., Савинков В. М. Проектирование информационной базы автоматизированной системы на основе СУБД.-М.: Финансы и статистика, 1982.- 174с.
- Бушев С.Н., Бесфамильный М. С. Программно-аппаратные методы управления данными, М., Наука, 1982, 240 с.
- Вейнеров О.М., Казаров М. С., Латышев М. И. Методы и средства автоматизации проектирования логических структур баз данных.-Зарубежная радиоэлектроника, 1980, Л 9, с. 33−48.
- Виленкин С.Я., Трахтенгерц Э. А. Математическое обеспечение управляющих вычислительных машин. М.: Энергия, 1972, 223 с.
- Вольфенгаген В.Э., Кузин Л. Т., Саркисян В. И. Реляционные методы проектирования банков данных, Киев: Вища школа, 1979, 192 с.
- Глушков В.М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра, языки, программирование. Киев: Наукова думка, 1974. 328 с.
- Грис Д. Конструирование компилляторов для цифровых вычислительных машин. М.: Мир, 1975. 543 с.
- Дагаев Н.И., Рудзицкий"Б.Н. Банки данных.-Новое в жизни, науке, технике. Сер. Техника. М., 1979, вып.5. 64с. 5. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975, 248с.
- Сб. Дейт К. Введение в системы баз данных. М.: Наука, 1980, 464с.
- Джадд Д.Р. Работа с файлами. М.: Мир, 1975. 144 с.
- Драммовд М. Методы оценки и измерений дискретных вычислительныхсистем. М.: Мир, 1977. 382 с. 9. Дрибас В. П. Реляционные модели баз данных. Мн.: изд-во ЕГУ им. В. И. Ленина, 1982. 192 с.
- Дрибас В.П., Курскова Г. Л., Столяров Г. К. Введение в реляционные модели баз данных, йн-т математики АН БССР. Минск, 1977, 53 с.
- Дрибас В.П., Курскова Г. Л. Анализ средств манипулирования реляционными базами данных. Ин-т математики АН БССР. Минск, 1979.64 с.
- Евстигнеев В.А. Применение бинарных деревьев для организации больших массивов информации. В сб.: Прикладная информатика. М.: Финансы и статистика, 1981, вып. I, с. I70−2II.
- Задыхайло И.Б., Соловьев В. В. Вопросы создания специализированного процессора для реляционных баз данных. Ин-т Прикладной математики АН СССР. М., 1979. 57 с.
- Заикин О.А., Кацев С. Б., Советов Б. Я. Размещение файлов намагнитных дисках при проектировании баз данных. УСиМ, 1981, 7/3, с.
- Зайцев М.Г. Реляционная однородно структурированная (несвязная) база данных. УС и М, 1982, № 6, с. 74−78.
- Зубов B.C., Казарницкий С. Д., Цуников Ю. В. Математическое обеспечение цифровых вычислительных машин и систем. Учеб. пособие, — 4.2, М.: МЭИ, 1976. 73 с.
- Зубов B.C., Сокурская И. Ю. О способе преобразования выражений реляционной алгебры. Тр./Моск.энерг.ин-т, 1983, вып.587,с.50−54.
- Игнатенко Б.В., Колодко Л. В., Павловский В. И., Савченко С. Ф. Пакет прикладных программ физической организации баз данных -ППП ФОВД. УС и М, 1981, 162, с.116−120.
- Ильинский Н.И., Мясников А. В. Система генерации программ обработки данных (РЕГББД). В сб.: Вопросы кибернетики. М., 1979,55, с. 40−45.
- Информационные системы общего назначения /Пер. с англ. под ред. Е. Л. Ющенко. М.: Статистика, 1975. 471 с.
- Казарицкий С.Д. Исследование вопросов построения систем управления реляционными базами данных: Автореферат канд. дисс. М.: МЭИ, 1980. 20 с.
- Казарицкий С.Д., Овсянникова М. Р., Сокурская И. Ю. Технические приемы реализации системы управления базой данных. В кн.: Проблемы создания программного обеспечения АСУ. М., 1976, с.86−88.
- Казарицкий С.Д., Овсянникова М. Р., Сокурская И. Ю. Системы управления базами данных. Учеб. пособие. М.: МЭИ, 1978, 24 с.
- Калиниченко Л.А. Методы преобразования моделей данных. УС и М, 1982, № 5, с. 88−94.
- Капп Д., Лебен Дж. Техника программирования для 1WS . Методология использования VL /I. М.: Финансы и статистика, 1983. 248 с.
- Кнут Д. Искусство программирования, для ЭВМ. Т. З. Сортировка и поиск. М.: Мир, 1978, 847 с.
- Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1978. 352 с.
- Кохонен Т. Ассоциативные запоминающие устройства.'М.: Мир, 1982. 383 с.
- Крамаренко Р.П., Скляров А. В., Лозняца Я. С. Управление памятью в системе ПАЛЬМА. В сб.: Банки данных и информационно-поисковые системы. М., 1980, с. 40. 1фзин Л. Т. Основы кибернетики. Т.2. М.: Энергия, 1979. 584с.
- Курскова Г. П., Дрибас В. П. Обзор основных реляционных языков. Ин-т математики АН БССР. Минск, 1979, 48 с.
- Куцык Б.С. Структура данных и управление. М.: Наука, 1975. 125 с.
- Лавров С.С., Гончаров Л.й. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971. 160 с.
- Лебедев В.Н. Введение в системы программирования. М.: Статистика, 1975, 311 с.
- Литвинов В.А. Некоторые методы обработки файлов в пашти прямого доступа и оценка их эффективности. УС и М, 1978, $ 5, с. 12−19.
- Литвинов С.А., Иваненко В. И. Обобщенная функция расстановкии организации файла рандомизированной структурой. Программирование, 1980, № 5, с.31
- Лефковиц Д. Структуры информационных массивов, . М.: Энергия, 1975, 208с.
- Маклаков А.В. К вопросу определения функциональной зависимости между атрибутами отношений в реляционных базах данных, Программирование, 1978, $ 1, с.
- Мальцев А.И. Алгебраические системы. М.: Наука, 1970, 332с.
- Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир, i980t 664 с.
- Мишенин А.И. Параметры, влияющие на выбор структуры данных. В сб.: Алгоритмы и организация решения экономических задач, М.: Статистика, 1979, вып. 13, с. 47−55.
- Мультимодельная система управления базами данных МУССОВ Когаловский М. Р., Когутовский В. В., Макальский К. И., Виноградов
- Н.М.- В сб.: Прикладная информатика. М.: Финансы и статистика, 1981, вып. I, o. 211−228.
- Неклюдова Е.А., Цаленко М. Ш. Синтез логической схемы реляционной базы данных. Программирование, 1979, № 6, с.58−68.
- Обобщенный подход к построению автоматизированных систем обработки данных. Учеб. пособие /Казарицкий С.Д., Куликова С. А., Овсянникова М. Р., Сокурская И. Ю. М.: МЭИ, 1980. 64с.
- Об одной системе управления базами данных /Казарицкий С.Д., Куликова С. А., Овсянникова М. Р. и др.- Тр. /Моск. Энерг. ин-т, 1979, вып. 441, с.
- Обработка информационных массивов в автоматизированных системах управления /Гдушков В.М., Гдадун В. П., Лозинский Л. С., Погре-бинский С. Б. Киев: Наукова думка, 1970, 184с.
- Овсянникова М.Р. Исследование способов отображения реляционной модели на память. Вычислительной системы: Автореферат канд. дисс.- М.: МЭИ, 1980, 20с.
- Овсянникова М.Р., Пышкина С. А., Сокурская И. Ю. Представление реляционной модели данных в памяти ЭВМ. Учеб. пособие, М.: МЭИ, 1983 .1040.
- Олле Т.В. Предложения КОДАСЩ по управлению базами данных. М.: Финансы и статистика, I98I. 286с.
- Основные характеристики отечественных СУБД и ИШ /Под.ред.
- A.А.Стогния. ИК АН УССР. Киев, 1980. 64 с.
- Парницкий В.И. Об организации многоатрибутных файлов. Кибернетика, 1981, № 5, с. 29−33.
- Размыслов Ю.П. Язык VSL -d в рнляционной модели Кодда.
- В сб.: Алгоритмы и организация решения экономический задач. М.: Статистика, 1978, вып. II, с.20−35.
- РБГВНД реляционный подход к генерации программ обработки данных /Ильинский Н.И., Кузин Л. Т., Мясников А. В., Стрижевский
- B.C. В сб.: Прикладная информатика. М.:Финансы и статистика, — 187 1982, вып. I, с. II4-I3I.
- Савинков В.М., Назаров М. С., Рысевич Ю. К. Использование систем управления, базами данных в АСУ. В сб.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1979, вып. 13, с. 29−38.
- Савинков В.М., Вейнеров О. М., Назаров М. С. Обобщенные процедуры автоматизированного логического проектирования БД. УС и М, 1981, № 4, с.
- Система управления базами данных как инструмент построения ав-матизированных систем обработки данных /Казарицкий С.Д., Пыш-кина С.А., Сокурская И.10., Овсянникова М.Р.-Тр./Моск.энерг. ин-т, вып. 525, с.74−79.
- Стогний А.А., Паньшин Б. Н. Программное обеспечение управления вычислительным процессом в ВЦ и сетях ЭВМ. Киев: Наукова Думка, 1983,237с.
- Столяров Г. К, Обзор предложений рабочей группы КОДАСИЛ по базам данных. В сб.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1974, вып.4, с. 48−77.
- Тихомиров В.П. Организация сопровождения программных средств АСУ. М.: Статистика, 1980, 60 с.
- Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983, 334 с.
- Феррари Д. Оценка производительности вычислительных систем. М.: Мир, 1981, 576 с.
- Флорес И. Структуры и управление данными. М.: Финансы и статистика, 1982, 819 с.
- Цаленко М.Ш. Реляционные модели базы данных. В сб.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1977, вып. 9, с.18−36.
- Цаленко М.Ш. Реляционные модели баз данных. В сб.: Алгоритмы иорганизация решения экономических задач. М.: Статистика, 1977, вып. 10, с. 16−29.ч
- Цаленко M. II1. Организация информации и информационные инварианты. Семиотика и информатика, 1979, № 12, с.
- Чукин Ю.В. К выбору организации файла. УС и М, 1977, № 3, о. 74−78.
- Шрейдвр Ю.А. Равенство, сходство, порядок. М.: Наука, 1971, 254с.
- Цикритзис Д., Бернстайн Ф. Операционные системы.: Мир, 1977, 336 с.
- Юровский Б.Ю. Методика оптимизации состава памяти и размещения информации в системах обработки данных. УС и М, 1979, № I, г
- 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.
- Aho A.V., Sagiv Y., Ullman J.D. Egnivalences among relationalу '. .expressions" SIAM J. on Computing, 1979″ v.8, n.2, p.218−246.
- 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.
- ANSI/X3/ Study group on data base management systems Interim Report, ВДС, 1975, v.7, n.2.
- Armstrong W.W. Dependency structures of database relationships. Proc. IFIP 74, North Holand, 1974, p.580−583.
- 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.
- 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.
- 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.
- Bernstein P.A. Synthesizing third normal form relations from functional dependencies. ACM Trans, on Database Sysfr., 1976, v. 1, n.4, p.277−298.
- Berra В., Oliver E. The Role of Associative array processers in 8ata base machine architecture. Conqputer, 1979″ v. 12, ^•3″ p.53−61.
- Blasgen M.W., Eswaran K.P. Storage and access in relational databases. IBM Syst. J., 1977″ v.16, n.4, p.363−378.
- Borkin S.A. Data model equivalence. Proc. 4 Int.Conf. on Very Large Data Bases, 1978, p.526&534.
- Cardenas A.F. Analysis and performance of inverted database structures. С ACM, 1975″ v. 18, n.5, p. 253−263.
- Cardenas A.F. Evaluation of file Organization. A model and system. СACM, 1973″ v.16, n.9, p.540−548.
- 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.
- 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.
- 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.
- Ю2. Godd E. F, A relational model of data for large shared data banks. СACM, 1970, v.13, n.6, p.377−387.
- 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.
- 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*
- 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.
- 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.
- Hammad P. Formulation of choice for file organization. Informations Syst., 1978, v.3, n., p.125−130.
- Hoffer J. A, Method for primary and secondary kfcy selection. 1980, p.
- Hsiao D., Harary F. A formal system for information retrieval from file® v- С ACM, 1970, v.13, n.2, p.67−73,
- 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.
- Kim W# Relational database systems. AOM Com.Surv., 1979″ v.11, n.3, p.185−211.
- King A. Calculating constraints on relational expressions. -ACM.Trans, on Database Syst., 1980, v.5, n.3, p.260−290.
- 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.
- 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.
- 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•
- 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.
- Pelagatti G., Paolini P., Pracchi G. Mapping external view to a common data model. Information Systems, 1978, v.3, n. p.141−151.
- 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.
- Schenk K.L., Pinker Y.R. An algorithm for servicing multi-relational queries. Proc.Int.Conf. on Management of Data, 1977, p.10−20.
- Schkolnick M. Secondary index optimization. Proc. ACM SIGMOD, 1975, p.186−192.
- Schkolnick M. The optimal selection of secondary indices for files, Information Systems, 1977, v.1, n.3, p.22−44.
- 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.
- Senko M.E. et al. Data structures and accessing in data base systems. IBM System J., 1973, v.12, n.1, p.30−95.
- Severance D.G., Carlie Y.V. A practical approach to selecting record access path. Computing Syrveys, 1977, v.9, n.4, p.259−272.
- 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.
- Smith D., Smith J. Relational database machines. Computer, 1979, v.12, n.3, p.28−38.
- 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.
- Strand A.J. The relational approach to the management of data bases. Broc. IFIP North Holland, 1971, p.901−904.
- Su S. et al. Retrieval operations and data representations ina context-oidressed disk system. Proc. AGH SIGPLAN/SIGIR, 1973, p.144−160.1
- 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.
- Whitney V.K. Relational Data Management System information systems. — Proc. of C0HTS-I7/Ed by Ton. J.T., Plenum Press, 1974, p.103−117.
- 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.
- Yao S.B. Optimization of query evaluation algorithm. ACM Trans, on Database Syst., 1979, v.4, n.2, p.133−155.