Методы доступа к хронологическим данным в реляционных системах управления базами данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Полухин, Александр Леонидович

• Полухин, Александр Леонидович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Полухин, Александр Леонидович

Аннотация 2Снисок сокран];ений и условных обозначений

Глава 1. Подходы к формализации модели данных. Оныт ис-нользования различных моделей данных в СУБД

1.1 Подходы к организации доступа к данным И

1.2 Выработка требований

1.3 Постановка задачи повышения эффективности доступа к хро-нологическим данным

Глава 2. Описание используемого способа расп1ирения реля-ционной модели данных

2.1 Метод темпорального расширения реляционной модели данных

2.2 Операторы для задания размерностей времени

2.3 Операторы для задания календарей

2.4 Операторы работы с темноральным расширением

2.5

Выводы но второй главе

Глава 3. Методы индексирования хронологических данных

3.1 Выработка требований

3.1.1 Особенности темнорального индексирования

3.1.2 SR-дерево

3.1.3 ЗК*-дерево

3.2 Управление пространственными данными

3.3 Алгоритмы улучшения качества R-деревьев

3.3.1 Глобальные алгоритмы

3.3.2 Алгоритмы разбиения множества объектов на мини-мально пересекаюЕдиеся грунпы

3.4 Практический анализ глобальных алгоритмов

3.5 Расширяемая архитектура

3.6

Выводы но третьей главе

Введение диссертации (часть автореферата) на тему «Методы доступа к хронологическим данным в реляционных системах управления базами данных»

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

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

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

Глава 3 посвящена методам индексации хронологических данных в СУБД. Первая часть главы посвящена описанию особенностей организации эффективного доступа к хронологическим данным. В ней так же предлагается метод переноса подходов к работе с пространственными данными на хронологическую модель. Вторая часть содержит ряд деталей работы с пространственными данными, а также особенности обработки пространственных соединений. Третья часть посвящена ключевому моменту использования предложенного подхода для хронологических данных, а именно алгоритму построения индекса. На основе более простых решений предлагается свой алгоритм. В оставшейся части главы проведен анализ полученных в ней результатов и излагается ряд предложений по направлению разработок, с целью дальнейшего повышения эффективности работы с хронологическими данными. Глава так же заканчивается выводами из полученных в ней результатов.

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

Оглавление.

Аннотация 2

Список сокращений и условных обозначений 7

Введение 8

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Полухин, Александр Леонидович

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

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

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

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

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

Заключение.

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

Также в этой работе был предложен новый метод доступа для хранения исторических данных, который получил название ЗЯ*-дерево; рассматриваются вопросы формирования и организации сегментов данных для исторических БД с большим числом записей. К SR*-дереву, как разновидности R-дерева применимы подходы, используемые для пространственных данных. В работе приведены алгоритмы построения оптимизированных R-деревьев, наиболее перспективных и популярных структур хранения и индексации, предложенных к настоящему времени. И наконец, показана возможная схема расширяемой архитектуры обработчика запросов.

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

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

Резюмируя, для достижения поставленных задач решены следующие вопросы.

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

2. Разработан набор операторов для работы с предложенным расширением.

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

4. Предложен алгоритм построения R-деревьев на неравномерных данных с минимализацией перекрытий.

5. Проведена оценка трудоемкости предложенного алгоритма.

Основные положения и отдельные результаты работы докладывались и обсуждались на следующих конференциях:

• XXXVI межвузовская научная конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2005)

• IX Санкт-Петербургская международная конференция «Региональная информатика - 2004» (РИ-2004) (Санкт-Петербург, 2004)

Список литературы диссертационного исследования кандидат физико-математических наук Полухин, Александр Леонидович, 2006 год

1. Аткинсон М. и др. Манифест систем объектно-ориентированных баз данных // Системы Управления Базами Данных, №4, 1995, с.142-155.

2. Дейт К.Дж. Введение в системы баз данных, 7-е издание: Пер. с англ.- М.: Издательский дом "Вильяме 2001 1072 с.

3. Гуляев А.И. Временные ряды в динамических базах данных. М.: Радио и связь, 1989 г. - 128с.

4. Иванов А.Ю., Саенко И.Б. Основы построения и проектирования реляционных баз данных. СПб: ВАС, 1998 г. - 80с.

5. Ким В., Гарза Ж.Ф., Грэхэм Б. Пути развития объектно-реляционных технологий баз данных. // Системы управления базами данных, №04, 1996.

6. Кирстен В., Иренгер И., Рёриг Б., Шульте П. СУБД Cache': объектно-ориентированная разработка приложений. СПб, "Питер 2001.

7. Кнут Д.Э. Исскуство программирования, Том 3: Сортировка и поиск.- М.: Издательский дом Вильяме, 2000.

8. Когаловский М.Р. Расширение реляционной модели баз данных временных рядов // Управляющие системы и машины. 1994. № 6.

9. Кречетов Н., Петухова Е., Скворцов В., Умников А., Щукин Б. Постреляционная технология Cache' для реализации объектных приложений. -М, МИФИ, 2001.

10. Маслов Д.В. Модель баз данных для хранения и обработки упорядоченных данных в АСУТП и экономических приложениях. // Промышленные АСУ и контроллеры. 2003. № 12

11. И. Маслов Д.В. Некоторые вопросы функциональности и производительности WinCC версии 5.1 // Промышленные АСУ-и контроллеры. 2003. №6. с. 45-46.

12. Мейер Д. Теория реляционных баз данных./ Пер. с англ. М.: Мир, 1987 г., 608с.

13. Полухин A.JI. Методы доступа к пространственным данным. IX Санкт-Петербургская международная конференция "Региональная информатика-2004". Материалы конференции., СПб, 2005, с.75-81.

14. Полухин A.JI. Метод темпорального расширения реляционной модели данных. XXXVI межвузовская научная конференция аспирантов и студентов "Процессы управления и устойчивость". Материалы конференции., СПб, 2005.

15. Полухин A.JI. Операторы темпорального расширения реляционной модели данных. // Вестник С.-Петерб. ун-та. Сер.10. 2006. Вып.1. с.123-132.

16. Прохоров А. Использование объектно-реляционных СУБД для хранения и анализа временных рядов. //КомпьютерПресс. 2001. - №6.

17. Сидоров А.А., Маслов Д.В. (Самара, ООО НВФ "CMC"). Реляционно-темпоральная модель данных.

18. Скворцов А.В. Алгоритмы улучшения качества R-деревьев. Томский госуниверситет, 2001.

19. Смирнов В. Системы хранения данных тенденции, решения, перспективы. //Корпоративные системы. - 2002. - №3 - С. 24-29.

20. Чемберлин Д. Анатомия объектно-реляционных баз данных // Системы Управления Базами Данных, №1-2, 1998, с.3-24.

21. Энсор Д., Стивенсон Й. Oracle. Проектирование баз данных: Пер. с англ. К.: Издательская группа BHV, 1999 - 560 с. ISBN 966-552-019-9

22. Allen J. F. Time and time again: The many ways to represent time. // International Journal of Intelligent Systems 6 (4), July 1991. New York, USA. - John Wiley & Sons, Inc, 1991. - p. 341-356.

23. Batory D. et al. GENESIS: An Extensible Database Management System. IEEE Trans, on Software Engineering, vol. 14, no. 11, Nov. 1988.

24. Beckman N., Kriegel H.-P., Schneider, Seeger B. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. Proc. ACM SIGMOD, 1990.

25. Bertino E., Kim W., and Garza J. Composite Objects Revisited. Proc. ACM SIGMOD Intl. Conf. on Management of Data, Portland, Oregon, June 1989.

26. Bettini C., Dyreson C.E., Evans W.S., Snodgrass R.T., Wang X.S. A Glossary of Time Granularity Concepts. Temporal Databases: Research and Practice, Eds. Etzion 0., Jajodia S., Sripada S., Springer-Verlag, 1998.

27. Bettini C., De Sibi R. Symbolic Representation of User-defined Time Granularities. Annals of Mathematics and Artificial Intelligence, 2000, Vol. 30, No. 1-4, pp. 53-92.

28. Bettini C., Wang X.S., Bertino E., Jajodia S. Semantic Assumptions and Query Evaluation in Temporal Databases. ACM SIGMOD Conference, 1995, pp. 257-268.

29. Bettini C., Wang X.S., Jajodia S. A General Framework for Time Granularity and Its Application to Temporal Reasoning. Annals of Mathematics and Artificial Intelligence, 1998, Vol. 22, No. 1-2, pp. 29-58.

30. Bliujute R. R-Tree Based Indexing of Now-Relative Bitemporal Data. -Proc. VLDB Conf., 1998.

31. Bozkaya Т., Ozsoyoglu M. Indexing Transaction Time Databases. -Information Sciences, 1998.

32. Chandra R., Segev A. Managing Temporal Financial Data in an Extensible Database. Proceedings of the 19th Conference on Very Large Databases,1993, pp. 302-313.

33. Chou H.T., Kim W. A Unifying Framework for Versions in a CAD Environment. Proc. Intl. Conf. on Very Large Data Bases, August 1986, Kyoto, Japan.

34. Chou H.T., Kim W. Versions of Schema for Object-Oriented Databases. Proc. Intl. Conf. on Very Large Data Bases, Long Beach, Calif., Sept. 1988.

35. Clifford J., Warren D.S. Formal semantics for time in databases. ACM Transactions on Database Systems, 1983, Vol. 8 , No. 2, pp. 214-254.

36. Comer D. The Ubiquitous B-tree. ACM Сотр. Surv., 11(2), 1979.

37. Date C.J., Darwen H., Lorentzos N. Temporal Data & the Relational Model (1st edition). Morgan Kaufmann, 2002, 480 pages.

38. Dreyer W., Kotz A.D., Schmidt D. An Object-Oriented Data Model for a Time Series Management System. Proceedings of the 7th International Working Conference on Scientific and Statistical Database Management,1994, pp. 186-195.

39. Dyreson C.E., Evans W.S., Lin H., Snodgrass R.T. Efficiently Supported Temporal Granularities. IEEE Transactions on Knowledge and Data Engineering, 2000, Vol. 12, No. 4, pp. 568-587.

40. Easton M. Key-Sequence Data Sets on Indelible Storage. IBM Journal of Research and Development, 30(3), 1986.

41. Faloutsos С., Sellis Т., and Roussopoulos N. Analysis of Object-Oriented Spatial Access Methods. Proc. ACM SIGMOD Intl. Conf. on Management of Data, San Francisco, Calif., May 1987, pp. 426-439.

42. Freytag J. A Rule-Based View of Query Optimization. Proc. ACM SIGMOD Intl. Conf. on Management of Data, pp. 173-180, San Francisco, Calif., 1987.

43. Greene D. An Implementation and Perfomance Analysis of Spatial Data Access Methods. Proc. Data Engineering, 1989.

44. Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching. -Proc. ACM SIGMOD, 1984.

45. Jensen C.S. A Consensus Glossary of Temporal Database Concepts. ACM SIGMOD Rec., 23(1), 1994.

46. Katz R. Towards a Unified Framework for Version Modelling in Engineering Databases. ACM Computing Surveys, vol. 22, no. 4, Dec. 1990, pp. 375408.

47. Kim W., Ballou N., Garza J., Woelk D. A Distributed Object-Oriented Database System Supporting Shared and Private Databases. ACM Trans, on Office Information Systems, Jan. 1991, pp. 31-51.

48. Kolovson C.P., Stonebraker M. Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. Proc. ACM SIGMOD, 1991.

49. Kriegel H., Schiwietz M., Schneider R., Seeger B. // Proc. Symp. On the Design and Implementation of Large Spatial Databases, Santa Barbara. -1989. P.413-418.

50. Leban В., McDonald D., Forster D. A Representation for Collection of Temporal Intervals. Proceedings of the AAAI-1986, 5th International Conference on Artificial Intelligence, 1986, pp. 367-371.

51. Lin L., Risch Т., Skuld M., Badal D. Indexing Values of Time Sequences- Proceedings of the 5th International Conference on Information and Knowledge Management, 1996, pp. 223-232.

52. Lin L., Risch T. Quering Continuous Time Sequences Proceedings of the 24th International Conference on Very Large Databases, 1998, pp. 170-181.

53. Lomet D.B., Salzberg B. The Perfomance of a Multiversion Access Method.- Proc. ACM SIGMOD, 1990.

54. Maurer W.D., Lewis T.G. Hash Table Methods. ACM Сотр. Surv., 7(1), 1975.

55. Niezette M., Stevenne J. An Efficient Symbolic Representation of Periodic Time. Proceedings of the International Conference on Information and Knowledge Management, Lecture Notes in Computer Science, 1993, Vol. 752, pp. 161-168.

56. Ning P., Wang X.S., Jajodia S. An Algebraic Representation of Calendars // Annals of Mathematics and Artificial Intelligence. 2002. Vol. 36, No. 1-2. Pp. 5-38.

57. Oracle8i Concepts. Release 2 (8.1.6). December 1999. Part No. A76965-01

58. Oracle8i Administrator's Guide. Release 2 (8.1.6). December 1999. Part No. A76956-01

59. Oracle8i Time Series User's Guide. Release 8.1.5. February 1999. A67294-01

60. Ramakrishnan R., Donjerkovic D., Ranganathan A., Beyer K.S., Krishnaprasad M. SRQL: Sorted Relational Query Language. Proceedings of the 10th International Conference on Scientific and Statistical Database Management, 1998, pp. 84-95.

61. Shasha D. Time Series in Finance: the array database approach, http: / / www. cs. nyu. edu/cs/faculty / shasha/papers / j agtalk.html

62. Richardson J. Supporting Lists in a Data Model (A Timely Approach). -Proceedings of the 18th International Conference on Very Large Databases, 1992, pp. 127-138.

63. Salzberg В., Tsotras V.J. Comparison of Access Methods for Time-Evolving Data. ACM Сотр. Surv., 31(2), 1999.

64. Schmidt D., Dittrich K.A., Dreyer W., Marti R. Time Series, a Neglected Issue in Temporal Database Research / Proceedings of the Int. Workshop on Temporal Databases. 1995.

65. Segev A., Shoshani A. A Temporal Data Model Based on Time Sequences. Temporal Databases - Theory, Design and Implementation, Eds. Tansel A.U. et al., The Benjamin/Cummings Publishing Company, 1993, pp. 248269.

66. Segev A., Shoshani A. Logical Modeling of Temporal Data. Proceedings of ACM SIGMOD Conference, 1987, pp. 454-466.

67. Sellis Т., Roussopoulos N., Faloutsos C. The R-Tree: A Dynamic Index for Multi-Dimensional Objects. Proc. VLDB Conf., 1987.

68. Seshadri P. Management of Sequence Data. Ph.D. Thesis, University of Wisconsin, Computer Science Department, 1996.

69. Seshadri P. SEQ: A Model for Sequence Databases. 1995.

70. Seshadri P., Livny M., Ramakrishnan R. The Design and Implementation of a Sequence Database System. Proceedings of the 22th International Conference on Very Large Databases, 1996, pp. 99-110.

71. Snodgrass R., Aim I. Temporal Databases. IEEE computer, vol. 19, no. 9, Sept. 1986, pp. 35-42.

72. Snodgrass R. The Temporal Query Language TQuel. ACM Trans, on Database Systems, vol. 12, no. 2, June 1987, pp. 247-298.

73. Stonebraker M. The Design of the Postgres Storage System. Proc. VLDB Conf., 1987.

74. Varman P.J., Verma R.M. An Efficient Multiversion Access Structure. -IEEE Trans, on Knowledge, Data Engineering, 9(3), 1997.

75. Wang X.S., Bettini C., Brodsky A., Jajodia S. Logical Design for Temporal Databases with Multiple Granularities. ACM Transactions on Database Systems, 1997, Vol. 22, No. 2, pp. 115-170.

76. Woelk D., Kim W. Multimedia Information Management in an Object-Oriented Database System. Proc. Intl. Conf. on Very Large Data Bases, Brighton, England, Sept. 1987, pp. 319-329.

77. Yao F.F., van Leeuwen J. Computational Geometry. Handbook of Theoretical Computer Science, Vol. A. MIT Press, 1998.