Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/content_root/programs/kaf/special/vichmat/teor-af.doc Дата изменения: Mon Nov 10 08:54:35 2008 Дата индексирования: Sun Apr 10 03:12:38 2016 Кодировка: koi8-r

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СИСТЕМ УПРАВЛЕНИЯ
ПОЛУСТРУКТУРИРОВАННЫМИ ДАННЫМИ
с.н.с. С.А. Афонин, н.с. А.С. Шундеев
1/2 года, 2-5 курс
1. Структура курса. Понятие полуструктурированных данных и причины их
возникновения. XML. Неформальное описание задач системы управления.
2. Реляционная алгебра. Краткий обзор систем управления реляционными
данными. Индексы, представления, оптимизация запросов.
3. Формальное представление полуструктуриропанных данных (OEM-модель).
Представление XML документов в соответствии с OEM-моделью. Схемы данных.
Ограничения на пути.
4. Языки запросов. Конъюнктивные регулярные путевые запросы (CR-PQ).
Аналогия с задачей изоморфного вложения графов.
5. Алгоритм поиска подграфа и его модификация для вычисления CRPQ-
запроса.
6. Классификация методов повышения эффективности алгоритма вычисления
запросов. Переписывание CRPQ-запросов с учетом графовой схемы (усечение,
запроса).
7. Индексные структуры дня полуструктурированных данных.
8. Вычисление запросов при наличии представлений. Переписывание запроса.
Оценка полноты совокупности представлений.
9. Проблема определения эквивалентности запросов в общем случае.
10. Распределенное вычисление запросов и другие перспективные задачи.

Литература
1. Джонсон Д. Гэри М. Вычислительные машины и труднорешаемые задачи. М.,
Мир, 1982.
2. Serge Abiteboul and Victor Vianu. Regular path queries with constraints.
pages 122-133, 1997.
3. Peter Buneman. Susan Davidson, Gerd Hillebrand, and Dan Suciu. A query
language and optimization techniques for unstructured data. In Proceedings
of the 1996 ACM SIGMOD International, Conference on Management of Data,
pages 505-516. 1996.
4. Peter Bimeman. Susan Davidson, Gerd Hillebrand, and Dan Suciu. A query
language and optimization techniques for unstructured data. Technical
Report 9, PENN Database Research Group, http://db.cis.upenn.edu/index.html,
1996.
5. Peter Bimeman, Susan B. Davidson, Mary F. Fernandez, and Dan Suciu.
Adding structure to unstructured data. In Foto N. Afrati and Phokion Ko-
laitis, editors, Database, Theory ICDT'97, 6th International Conference,
volume 1186 of Lecture Notes in Computer Science, pages 336-350, Delphi,
Greece, 8-10 January 1997. Springer.
6. Peter Bimeman, Wenfei Fan, Jerome Simeeon, and Scott Weinstein.
Constraints for semistructured data and XML. SIGMOD Record (A CM Special
Interest Group on Management of Data), 30(1): 47-54, 2001.
7. Peter Buneman, Wenfei Fan. and Scott Weinstein. Path constraints in
semistructured databases. Journal of Computer and System Sciences, 61(2):
146-193, 2000.
8. Peter Buneman, Mary F. Fernandez, and Dan Suciu. UnQL: a query language
and algebra for semistructured data based on structural recursion. VLDB
Journal: Very Large Data Bases, 9(1): 76-110, 2000.
9. Diego Calvanese, Giuseppe De Gia.eomo, Maiirizio Lenzerini, and Moshe Y.
Vardi. Lossless regular views. In Proc. of the 21st ACM SIGACT SIGMOD
SIGART Sym. on Principles of Database Systems (PODS 2002), pages 247-258,
2002.
10. S. Chawathe, H. Garcia-Molina, J. Hammer, K. Ireland, Y. Papakoiistanti-
nou, J. Ullman, and J. Widom. The TSIMMIS project: Integration of
heterogeneous information sources. In Proc. of the. 100th Anniv. Meeting,
pages 7-18. Information Processing Society of Japan, 1994.
11. Alin Deutsch. Mary Fernandez, Daniela Florescu, Alon Levy, and Dan
Suciu. A query language for XML. Computer Networks (Amsterdam, Netherlands:
1999), 31(11 16): 1155-1169, 1999.
12. Alberto Mendelzon Flavio Rizzolo. Indexing xml data with toxin.
13. R. Goldman and J. Widom. Dataguides: Enabling query formulation and
optimization in semistructured databases. In Twenty-Third International
Conference, on Very Large. Data Bases, pages 436-445, 1997.
14. H.V. Jagadish, Raymond T. Ng, and Divesh Srivastava. Substring
selectivity estimation, pages 249-260, 1999.