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

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

В докладе рассматривается представление слабоструктурированных данных в виде ориентированных графов с помеченными ребрами, для описания которых используется модель OEM [1]. В первой части дается краткий обзор известных методов [2,3] сокращения времени поиска в слабоструктурированных базах данных. Внимание во второй части доклада акцентируется на методах сокращения времени поиска при помощи индексов, представляющих собой иерархии схем OEM-документов [4-6].

Слайды к докладу в формате PDF: Gorelov20090309.pdf

Литература:

1. Papakonstantinou Y., Garcia-Molina H., Widom J. "Object exchange across heterogeneous information sources". Proceedings of the Eleventh International Conference on Data Engineering, 1995. P.251–260.
2. Qun Chen , Andrew Lim , Kian Win Ong, D(k)-index: an adaptive structural summary for graph-structured data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California.
3. Pierre Geneves, Jean-Yves Vion-Dury, «Logic-based XPath optimization». Proceedings of the 2004 ACM symposium on Document engineering. Milwaukee, Wisconsin, USA. P. 211–219.
4. Афонин С. А. «Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов». Вычислительные технологии. Вып. 12, 2007, cтр.23–32.
5. Горелов С.С. , Васенин В.А. Усечение пространства поиска в полуструктурированных базах данных при помощи иерархии схем документов. «Программирование». Вып. 6, 2005, стр.41–55.
6. Горелов C.C. Модели и алгоритмы для систем поиска в наборах документов. «Информационные технологии». Вып. 1, 2009, стр.61–66.