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

ВВЕДЕНИЕ.

ГЛАВА I. МЕТОДЫ ПОСТРОЕНИЯ ЛОГИЧЕСКОЙ СХЕМЫ

РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ.

1.1. Логические модели баз данных. Основные понятия реляционной модели

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

1.3. Методы нормализации логических схем.

1.4. Выводы.

ГЛАВА 2. ПОИСК ДОПУСТИМЫХ СХЕМ РЕЛЯЦИОННОЙ

БАЗЫ ДАННЫХ.

2.1. Допустимые схемы базы данных

2.2. Разложение отношения и полные семейства схем разложений

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

2.4. Выводы.

ГЛАВА 3. ОЦЕНКА КАЧЕСТВА ЛОГИЧЕСКОЙ СХЕМЫ

РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ V.

3.1. Критерии выбора логической схемы РБД и задача восстановления проекции отношения.

3.2. Построение минимальных восстанавливающих подсхем.

3.3. Выводы.

ГЛАВА 4. СИСТЕМНЫЕ СРЕДСТВА АВТОМАТИЗАЦИИ

ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ РЕЛЯЦИОННЫХ

БАЗ ДАННЫХ.

4.1. Алгоритмы построения допустимых логических схем.

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

4.3. Подсистема автоматизации логического проектирования реляционных баз данных

4.4. Выводы.

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

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

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

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

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

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

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

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

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

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

Реализация "результатов -работы. Научные и практические результаты диссертационной работы положены в основу создания средств автоматизации логического проектирования реляционных баз данных, которые включены в состав системы управления базами данных ДОКА., реализованной на языке МНЕМОКОД М-7000 для ЭВМ СМ-2 и М-7000.

Разработанная подсистема логического проектирования использовалась при организации базы данных на Волжском автомобильном заводе.

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

Апробация работы. Основные результаты диссертационной работы докладывались на школе-семинаре "Построение высокопроизводительных систем информационного поиска и управления базами данных» (Суздаль, 1980), на майской сессии НТОРЭС им. А.С.Попова (Москва, 1981), на Всесоюзном совещании "Высокопроизводительные вычислительные системы" (Тбилиси, 1981), на московском семинаре "Проблемы расширения возможностей автоматов" (Москва, 1981,1984), на Всесоюзном научно-техническом совещании "Проблемы и перспективы передачи и телеобработки данных" (Кишинев, 1983), на школе-семинаре "Семиотические аспекты формализации интеллектуальной деятельности" (Телави, 1984), на экспертных оценках лучших работ Института проблем управления (Москва, 1984, I премия). Апробация диссертационной работы в целом проведена на межлабораторном семинаре Института проблем управления.

Публикации. По результатам выполненных исследований опубликовано 6 печатных работ.

Диссертация состоит из четырех глав.

В первой главе проведен обзор литературы и сравнительный анализ методов логического проектирования реляционной базы данных, которые основаны на замене отношения набором его проекций. Показаны трудности использования этих методов на практике и предложен способ преодоления некоторых из этих трудностей, в соответствии с которым выделены две отдельные задачи логического проектирования: генерация всевозможных допустимых логических схем РБД и выделение наилучшей схемы.

Во второй главе исследуется задача построения всевозможных логических схем РБД. Формально определены условия допустимости логической схемы и при некоторых ограничениях показана связь допустимости схемы со свойствами разложимости п,--арных отношений (относительно операции естественного соединения). Доказано, что каково бы не было множество возможных состояний РБД, в нем всегда найдется состояние, которое однозначно определяет все допустимые логические схемы для этой РБД.

В случае, когда РБД описывается ограничениями целостности вида зависимостей по соединению, решается задача поиска различных допустимых логических схем. Построена система правил вывода, позволяющая получать новые допустимые схемы из уже наиденных.

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

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

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

В заключении изложены основные результаты диссертации.

4.4. Выводы

1. Разработан алгоритм получения допустимых схем РБД путем построения базиса пополнения исходного семейства схем по правилам вывода. При построении базисных (наименьших) покрытий по этому алгоритму не строятся покрытия, заведомо большие текущих, что сокращает перебор.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

6. Создан комплекс системных программ по автоматизации построения логической структуры реляционной базы данных.

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

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

3. Цаленко М.Ш. Реляционные модели баз данных (обзор). В кн.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1976, вып. 9, с.20-32, вып.10, с.33-48.

4. Иваницкий В.И., Горчинская О.Ю., Кулмагамбетов А.Р. Системы управления базами данных. В кн.: Теория и техника управления, М.: Институт проблем управления, 1979, с.45-53.

5. Горчинская О.Ю. Теоретический аспект построения реляционных моделей баз данных. Автоматика и телемеханика, 1983, № I, с.5-25.

6. Codd Б.P. A Relational Model of Data for Large Shared Data Banks.- Comm. ACM, 1970, v.13, No.6, p.377-387.

7. Codd E.F. Further normalization of the data base relational model.- In: Data Base Systems. Englewood Cliffs, IT.J. Prentice-Hall, 1972, p.33-64.

8. Codd E.F. Recent Investigations in relational data base systems.- In: Proc. IFIP-74 Congress. Amsterdam: North Holland Publishing Company, 1974, 1017-1021.

9. Codd E.F. Extending the database relational model to cap- 133 ture more meaning.- ACM Trans. Database Systems, 1979, v.4, Ho.4, p.397-434.

10. McLeod D.J. High level expression of semantic integrity specifications in a relational data base systems.- In: Proc. Intern. Conf. Very Large Data Bases. Flamingham, Mass.: ACM, 1975, p.50-62.

11. Osborn S.J. Towards a universal relation interface.- In: Proc. 5th Intern. Conf. Very Large Data Bases. Rio de Jeneiro.

12. Вениаминов E.M. Алгебраическая структура реляционных моделей баз данных. В кн.: Научно-технич. информация. Сб. ВИНИТИ. М., ВИНИТИ, 1980, сер.2, № 9, с.23-25.

13. Вениаминов Е.М. Алгебраический подход к моделям баз данных реляционного типа. Семиотика и информатика, 1980, № 14, с.44-80.

14. Cadion J.M. On Semantic Issues in the Relational Model of

15. Data.- In: Proc. Intern. Symp. Math. Foundations Сотр. Science, Springer-Verlag, pp.104-131, 1975.

16. Hall P.A.V. Optimization of a single relational expression- 134in a relational database.- IBM Journal of Research and Development, 1976, v.20, No.3, p.244-257.

17. Smith J.M., Chang P.Y. Optimizing the performance of a relational algebra database interface.- Communication of the ACM, 1975, v.18, No.10, p.568-579.

18. Sagiv G., Yannakakis M. Equivalence among relational expressions with the union and difference operators.- In: Proc. Int. Symp. on Very Large Data Bases, 1978.

19. Beeri C., Bernstein P.A., Goodman N. A sophisticate's introduction to database normalization theory.- In: Proc. 4th Intern. Conf. Very Large Data Bases, Berlin, 1978,p.113-124.

20. Delobel C. An overview of the relational data theory.- In: Proc. IPIP-80 Congress, Amsterdam: North Holland Publishing Company, 1980, p.413-425.

21. Rissanen J. Theory of relations for databases-a tutorial survery.- In: Proc. 5th Symp. on Math. Foundations of Computer Science, Lecture Notes in Computer Science, Berlin: Springer-Verlag, 1970, v.64, p.537-551.

22. Fagin R. Multivalued dependencies and a new normal form for relational databases.- ACM Trans, on Database Systems, 1977, v.2, No.3, p.262-278.

23. Zaniolo C. Analysis and design of relational schemata for database systems. Tech. Report UCLA-E2?G -7669, Dept. of Computer Science, Univers. of California, 1976.

24. Pagin R. The decomposition versus the synthetic approach to relational database design.- In: Proc. 3rd Intern. Conf. on Very Large Data Bases, ffokyo, 1977, p.441-446.

25. Uelobel C. Normalization and hierarchical dependencies inthe relational data model.- ACM Trans, on Database Systems, 1978, v.3, No.3, p.201-222.

26. Delobel C., Leonard M. New approach in the design of logical data base schema.-Сердика Бълг.мат.спис.,1978,M,с.197208.

27. Nicolas J.M. Mutual dependencies and some results on unde-composable relations.- Inî Proc. 4th Intern. Conf. on Very Large Data Bases, West Berlin, 1978, p.360-376.

28. Beeri C., Pagin E., Howard J.H. A complete exiomatization for functional and multivalued dependencies in database relations.- In: Proc. ACM-SIGMOD Intern. Conf. on Management of Data, Toronto, ACM, 1977, p.47-61.

29. Armstrong W., Delobel C. Decompositions and functional dependencies in relations, Department d'Informatique et Recherche Operationelle, Université de Montréal, 1977.

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

31. Кибернетика, 1981, № 2, с.42-48.

32. Beeri C., Vardi M. On the properties of total j'oin dependencies.- In: Advances in Database Theory, 1981, v. 1, p. 2571.43« Sciore E. A complete axiomatization of full join dependencies.- Journal of the ACM, 1982, v.29, No.2, p.373-393.

33. Beeri C., Vardi M.Y. Formal systems for tuple and equality generating dependencies.- SIAM J. Comput., 1984, v.13,1. No.1, p.76-98.

34. Fagin R. Horn Clauses and database dependencies Journal of the ACM, 1982, v.29, No.4, p.952-985.

35. Yannakakis M., Papadimitriou C.H. Algebraic dependencies.- Journal of Computer and System Sciences, 1982, No.25.

36. Sardi F., Ullman T.D. Template dependencies A large class of dependencies in relational databases and itscomplete axiomatization Journal of the ACM, 1982,v.29,1. No.2, p.363-372.

37. Beeri C. On the membership problem for functional and multivalued dependencies in relational databases.- ACM Trans, on Database Systems, 1980, v.5, p.241-259.

38. Beeri C., Bernstein P.A. Computational problems related to the design of normal forms for relational schémas.- ACM Trans, on Database Systems, 1979, v.4, Ho.1, p.30-59.

39. Isloor S.S. An algorithm with logical simplicity designing third normal form relational database schema from functional dependencies.- In: Proc. Intern. Conf. Management of Data, Milanoi ACM, p.31-50.

40. Kamabayashi Yahiko. Equivalent key problem of the relational database model.- In: Lect. Notes Comput. Science, 1979, v.75, p.165-192.

41. Luk W.S. Possible membership of a multivalued dependency in a relational database.- Inform Processing Lett., 1979, v.9, Ho.2, p.80-83.

42. Maier D. Minimum covers in the relational database model. Journal of the ACM, 1980.

43. Maier D., Mendelzon A.0., Sagiv Y. Testing implications ofdata dependencies. Proc. ACM-SIGMOD Intern. Hat. Conf. on Management of Data, ACM Trans. Database Systems, 1979, v.4, No.4, p.455-469.

44. Parker D.S., Delobel C. Algorithmic applications for a new result on multivalued dependencies.- In: Proc. 5th Intern. Conf. on Very Large Data Bases, Rio de Janeiro, ACM, 1979, p.67-74.

45. Rissanen J. Independent components of relations.- ACM Trans, on Database Systems, 1977, v.2, No.4, p.317-325.

46. Bernstein P.A. Synthesizing third normal form relations from functional depndencies.- ACM Trans, on Database Systems, 1976, v.1, No.4, p.277-298.

47. Beeri C., Mendelson A., Sagiv Y., Ullman J.D. Equivalence of relational database schemes.- In: Proc. 11th Annual ACM Symp. on Theory of Computing, 1979, p.319-329.

48. Beeri C., Rissanen J. On the decomposition of relational databases schemes, Wrokshop CERT-DERI, Toulouse, 1979.

49. Maier D., Mendelson A., Sadri P., Ullman J.D. Adequacy of decompositions of relational database.- In: Proc. 20th IEEE Symp. on Foundations of Computer Science, 1979, p.541-548.

50. Fagin R. Normal forms and relational data base operators. Proc. ACM-SIGMOD Conf. Boston, Mas.: ACM, 1979, p.30-48.

51. Fagin R. A normal form for relational databases that is based on domains and keys. IBM Research Report RJ2520, Can Jose, Calif., IBM, 1979.

52. Osborn S. Normal forms for relational data bases, Ph.D. Thesis, University of Waterloo, 1977.

53. Srinivasan B., Ra^araman V. On the normalization of relational databases. Inform Process. Lett., 1979, v.9, No.2, p.84-94.

54. Zaniolo C., Melkanoff M.A. Relational schemes for database systems. Tech. Report UCLA:ENG-7801, UCLA, 1978.

55. Wang C.P., Wedekind H.H., Segment synthesis in logical data base design.- IBM Journal of Research and Developm., 1975, v.19, No.1, p.71-77.

56. Yao S.B., Navathe S.B., Weldon J.S. An integrated approach to logical database design.- In: Proc. NYU Data-Base Symposium, New York, 1978, p.503-518.

57. Shen Stewart N.T.A. A semantic approach in designing relational data bases.- In: Proc. Annual ACM Conf., Washington, 1978, v.2, p.596-601.

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

59. Biskup J., Bayal U., Bernstein P.A. Synthesizing independent database schemas.- In: Proc. ACM-SIGMOD Conf. Boston, Mass: ACM, 1979, p.143-151.

60. Delobel C., Pichat E. The design of relational information system according to different kind of dependencies.- In: Lecture Notes in Computer Science, Springer-Verlag, 1978, v.65, p.266-290.

61. Bernstein P.A., Berri C. An algorithmic approach to normalization of relational database systems. Tech. Report CSRG-73, Computer Science Research Group, Univers. Toronto, 1976.

62. Delobel C., Casey R. G. Decomposition of a database and the theory of boolean switching funcjtions.- IBM Journal of Research and Develop., 1973, v.17, No.5, p.374-386.

63. Maier D., Mendelzon A.0. Generalized mutual dependencies and the decomposition ofdatabase relations.- In: Proc. 5th Intern. Conf. on Very Large Data Bases, Rio de Janeiro, ACM, 1979, p.75-82.

64. Fagin R. Functional dependencies in a relational database and propositional logic.- IBM Journal of Research and Develop. , 1977, v.21, No.6, p.534-544.

65. Горчинская О.Ю., Петров C.B., Тененбаум Л.А. Разложение отношений и логическое проектирование реляционных баз данных. Автоматика и телемеханика, 1983, I - № 2, с.159-166, II - № 3, с.152-160.

66. Горчинская О.Ю., Петров C.B. О представимости многоместного отношения через его части. В кн. Семиотические аспекты формализации интеллектуальной деятельности. Тезисы докладов школы-семинара. М.: ВИНИТИ, 1983, с.39-40.

67. Горчинская О.Ю. Об одной задаче оптимизации выполнения запросов в реляционных баз данных. В кн. Проблемы и перспективы передачи и телеобработки данных. Тезисы докладов.

68. М.: НТОРЭС им. А.С.Попова, 1983, с.25-27.