Некоторые аспекты поддержки целостности в базах данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Павлова, Екатерина Юрьевна

• Павлова, Екатерина Юрьевна
• кандидат физико-математических наук
• 2000

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

1 Поддержка целостности

1.1 Поддержка целостности в классических СУБД.

1.1.1 Пессимистический подход

1.1.2 Оптимистический подход.

1.1.3 Сравнение подходов.

1.2 СУБД реального времени.

1.2.1 Управление транзакциями.

1.2.2 Системы с устаревающими данными.

1.3 Слабоструктурированная информация.

1.3.1 Модель данных OEM.

1.4 Применение формальных методов.

1.4.1 Duration Calculus

2 Управление транзакциями в базах данных реального времени хранимых в оперативной памяти

2.1 Системы с виртуальной памятью.

2.1.1 Общий механизм работы.

2.2 Управление транзакциями для систем с виртуальной памятью

2.2.1 Модель.

2.2.2 Постановка задачи.

2.2.3 Мотивация.

2.2.4 Основная идея — "Грубый" подход.

2.2.5 Подход, основанный на версиях.

2.2.6 Вариации алгоритма и близкие вопросы

2.3 Сравнительный анализ.

2.3.1 "Грубый" подход и подход, основанный на версиях

2.3.2 Сравнение с другими алгоритмами

3 Управление вложенными транзакциями в БДРВ

3.1 Модель вложенных транзакций.

3.1.1 Алгоритм управления транзакциями для модели вложенных транзакций.

3.1.2 Преимущества модели.

3.2 Рассматриваемая модель.

3.3 Мотивировка.

3.4 Основные понятия.

3.5 Алгоритм.

4 Формализация систем БД реального времени

4.1 Базовая модель.

4.2 Сериализуемость.

4.3 Формализация двухфазного протокола блокирования

4.4 Модель системы БД реального времени

5 Целостность слабоструктурированных данных

5.1 Ограничения целостности.

5.1.1 Ограничения в структурированных БД.

5.1.2 Ограничения в слабоструктурированных БД

5.2 Ограничения корректности данных.

5.2.1 Временные ограничения

5.2.2 Описание ограничений корректности данных в существующих моделях.

5.3 Коммутативность операций над слабоструктурированными данными

5.3.1 Модель данных

5.3.2 Предикаты коммутативности.

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

Заключение

В работе получены следующие основные результаты:

• предложена серия оптимистических алгоритмов управления транзакциями в многопроцессорных системах реального времени специального вида. Основным достоинством предлагаемых алгоритмов является очень низкая дополнительная нагрузка на "только читающие" транзакции.

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

• Построено формальное описание систем баз данных реального времени и критериев корректности в рамках временной логики (Duration Calculus).

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

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

• Предложена классификация подходов к определению понятия согласованности для систем обработки слабоструктурированных данных.

Список литературы диссертационного исследования кандидат физико-математических наук Павлова, Екатерина Юрьевна, 2000 год

1. Е. А. Горшкова, И. С. Некрестьянов, Б. А. Новиков, Е. Ю. Павлова. Поддержка согласованности для слабоструктурированных данных. Программирование, 3:23-30, 2000.

2. С. Д. Кузнецов. Введение в СУБД: часть 7. СУБД, 3:136-148, 1996.

3. А. Саймон. Стратегические технологии баз данных. Финансы и статистика, 1999.

4. М. Гринев. Системы управления полуструктурированными данными. Открытые системы, 05-06, 1999.

5. К. Дейт. Введение в системы баз данных. Вильяме, 1999.

6. Е. Павлова. Управление транзакциями в СУБД реального времени. Программирование, 2:41-58, 2000.

7. R. Abbott and Н. Garcia-Molina. Scheduling real-time transactions: A performance evaluation. In Procedings of the 14th VLDB Conference, August 1988.

8. R. Abbott and H. Garcia-Molina. Scheduling real-time transactions with disk resident data. In Procedings of the 15th VLDB Conference, August 1989.

9. S. Abiteboul. Querying semistructured data. In Proceedings of the International Conference on Database Theory, Delphi, Greece, jan 1997.

10. S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The lorel query language for semistructured data. Journal of Digital Libraries, 1(1), nov 1996.

11. S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, 1:68-88, April 1997.

12. S. Abiteboul and V. Vianu. Regular path queries with constraints. In Proc. of the PODS'1991, 1997.

13. Serge Abiteboul, Peter Buneman, and Dan Suciu. Data on the Web. Morgan Kaufmann Publishers, 1999.

14. Rakesh Agrawal, Michael J. Carey, and Miron Livny. Concurrency control performance modeling: alternatives and implications. ACM Transactions on Database Systems, 12(4):609-654, December 1987.

15. P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.

16. Azer Bestavros and Spyridon Braoudakis. Timelines via speculation for real-time databases. In Proceedings of RTSS'94: The 14th IEEE Real-time Systems Symposium, San Juan, Puetro Rico, December 1994.

17. Azer Bestavros, Kwei-Jay Lin, and Sang Hyuk Son. Real-Time Database Systems: Issues and Applications. Kluwer Academic Publishers, 1997.

18. Angela Bonifati and Stefano Ceri. Comparative Analysis of Five XML Query Languages. SIGMOD Record, 29(1), March 2000.

19. Peter Buneman, Wenfei Fan, and Scott Weinstein. Path constraints on semistructured and structured data. In Proc. of the PODS'1998, June 1998.

20. Peter Buneman, Wenfei Fan, and Scott Weinstein. Interaction betwen path and type constraints. In Proc. of the PODS'1999, 1999.

21. M. J. Carey and M. R. Stonebraker. The performance of concurrency control algorithms for database management systems. In Proceedings of the 10th VLDB Conference, Singapore, August 1984.

22. R. G. G. Cattell, editor. The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann Publishers, 1996.

23. Zhou Chaochen, C. A. R. Hoare, and Anders P. Ravn. A calculus of durations. Information Processing Letters, 40(5):269-276, 1991.

24. S. Chawathe, S. Abiteboul, and J. Widom. Representing and querying changes in semistructured data. In Proceedings of the Fourteenth International Conference on Data Engineering, February 1998.

25. Sophie Cluet and Tova Milo, editors. ACM SIGMOD Workshop on The Web and Databases (WebDB), Philadelphia, Pennsylvania, USA, June 1999.

26. Lee Dongwon and W. Chu Wesley. Comparative Analysis of Six XML Schema Languages. SIGMOD Record, 29(3), September 2000.

27. Curtis E. Dyreson, Michael H. Bohlen, and Christian S. Jensen. Capturing and querying multiple aspects of semistructured data. In Proc. of the 25th VLDB Conference, Edinburgh, Scotland, 1999.

28. Joakim Eriksson. Real-Time and Active Databases: A Survey. In Active, Real-Time, and Temporal Database Systems, Second International, ARTDB-97, pages 1-23, Como, Italy, September 1997.

29. K. Eswaran, J. Gray, R. Lorie, and I. Traiger. The notions of consistency and predicate locks in a database system. In ACM, November 1976.

30. Schneider. F. On Concurrent Programming. Springer, 1997.

31. M. Fernandez, D. Florescu, J. Kang, A. Levy, and D. Suciu. Strudel: a web-site management system. In Proc. of the A CM SIGMOD conference on Management of Data, 1997.

32. Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. Verifying integrity constraints on web sites. In Proc. of the IJCAI'99, August 1999.

33. Michael J. Franklin (ed.). Management of semi-structured data. SIGMOD Record, 26(4), 1997.

34. D. Georgakopoulos. Multidatabase recoverability and recovery. In Proceedings of First International Workshop on Interoperability in Multidatabase Systems, Kyoto, Japan, April 1991.

35. R. Goldman and J. Widora. Dataguides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the Twenty-Third International Conference on Very Large Data Bases, pages 436445, Athens, Greece, August 1997.

36. Michael R. Hansen and Zhou Chaochen. Duration calculus: Logical foundations. Formal Aspects of Computing, 9:283-330, 1997.

37. J. R. Haritsa, M. J. Carey, and M. Livny. Dynamic real-time optimistic concurrency control. In Procedings of the IEEE Real-Time Systems Simposium, Orlando, Florida, December 1990.

38. Lee Juhnyoung and H. Son Sang. Concurrency Control Algorithms for Real-Time Database Systems, chapter Performance of Concurrency Control Mechanisms in Centralized Database Systems, pages 429-460. Prentice-Hall, 1996.

39. Yaron Kanza, Werner Nutt, and Yehoshua Sagiv. Incomplete answers for queries over semistructured data. January 1999.

40. Gerti Kappel, Elisabeth Kapsammer, and Werner Retschitzegger. X-Ray Towards Integrating XML and Relational Database Systems. Technical report, Johannes Kepler University Linz, July 2000.

41. Woosaeng Kim and Jaideep Srivastava. Enhancing real-time dbms performance with multiversion data and priority based disk scheduling. In Proceedings of the 12th Real-time Systems Symposium, San Francisco, California, December 1991.

42. H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM Transactions on Database Systems, 6(2), June 1981.

43. K. Lam, S. H. Son, V. Lee, and S. Hung. Using separate algorithms to process read-only transactions in real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS'98), pages 50-59, Madrid, Spain, December 1998.

44. A. Layman, E. Jung, E. Maler, H. J. Thompson, J. Paoli, J. Tigue, N. J. Mikula, and S. De Rose. XML Data. World Wide Web Consortium, 1998.

45. J. McHugh, S. Abiteboul, R. Goldman, D. Quass, and J. Widom. Lore: A database management system for semistructured data. Technical report, Database Group, Stanford University, feb 1997.

46. Jason McHugh and Jennifer Widom. Compile-time path expansion in lore. January 1999.

47. Giansalvatore Mecca and Paolo Atzeni. Cut and paste. Journal of Computer and System Sciences (JCSS), 58(3):453-482, 1999.

48. Giansalvatore Mecca, Paolo Merialdo, Paolo Atzeni, and Valter Crescenzi. The (short) Araneus guide to web-site development. In Proc. ot the WebDB, pages 13-18, 1999.

49. J. E. B. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. PhD thesis, MIT Press, Cambridge, MA, 1985.

50. K. Ramamritham. Real-time databases. International Journal of Distributed and Parallel Databases, 1(1), 1992.

51. R. Schmidt, J. Chase, and H. Levy. Using Shared Memory for Read-Mostly RPC Services. In Proceedings of the 29th Hawaii International Conference on System Sciences, January 1996.

52. Marc Shapiro and Paulo Ferreira. Larchant-RDOSS: a Distributed Shared Persistent Memory and its Garbage Collector. In Proceedings of the 9th International Workshop on Distributed Algorithms, September 1995.

53. S. H. Son, S. Park, and Y. Lin. An integrated real-time locking protocol. In Eighth IEEE International Conference on Data Engineering, pages 527-534, Phoenix, Arizona, February 1992.

54. Sang H. Son, J. Lee, and Yi Lin. Hybrid protocols using dynamic adjustment of serialization order for real-time concurrency control. The Journal of Real-Time Systems, 4:269-276, 1992.

55. J. Stankovic, S. H. Son, and J. Hansson. Misconceptions about real-time databases. IEEE Computer, 32(6):29-36, June 1999.

56. Jeffrey D. Ullman. Principles Of Database And Knowledge-Base Systems. W.H. Freeman &: Company, 1988.

57. O. Ulusoy. Analysis of concurrency control protocols for real-time database systems. Technical Report BU-CEIS-9514, Bilkent University, 1995.

58. O. Ulusoy. Research issues in real-time database systems. Information Sciences, 87(1-3), November 1995.

59. O. Ulusoy and G. G. Belford. A performance evaluation model for distributed real-time database systems. International Journal of Modeling and Simulation, 15(2), 1995.

60. G. Weikum. Principles and realization strategies of multilevel transaction management. ACM Transactions on Database Systems, 16(1): 132-180, March 1991.

61. World Wide Web Consortium. Extensible Markup Language (XML) 1.0, February 1998.

62. World Wide Web Consortium. XML Linking Language (XLink), July 1999.

63. M. Xiong, K. Ramamritham, J. A. Stankovic, D. Towsley, and R. Sivasankaran. Maintaining temporal consistency: Issues and algorithms. In First International Workshop on Real-Time Databases, Newport Beach, California, March 1996.