Классика баз данных - статьи
к XML, конечно, не мог
Текущий интерес к XML, конечно, не мог не коснуться XML-аппроксимации, оценок размера результатов запросов и других родственных проблем. Полуструктурированная природа XML сама по себе не приспособлена к применению аппроксимации на основе гистограмм, поскольку отсутствует непосредственное многомерное пространство, которое может разбиваться на бакеты, и требуется формировать некоторые численные характеристики XML. В подходе StatiX [] используется информация XML Schema для определения потенциальных источников структурного скашивания, а затем строятся одномерные гистограммы для большей части проблемных мест схемы, позволяя аппроксимировать распределения идентификаторов родительских узлов для различных элементов. В подходе XPathLearner [] используются марковские гистограммы (первого порядка) [], где частоты обходов всех путей длины 2 сохраняются в двумерных гистограммах. Измерения всегда представляют узлы `from' и `to' путей в графе XML; в первой гистограмме оба узла/измерения являются тегами XML, в то время как во второй гистограмме узел/измерение `from' является тегом XML, а узел/измерение `to' - это значение. При наличии достаточного объема памяти для всех пар тег-тег частоты поддерживаются точно, поскольку их очень немного. В отличие от этого, пары <тег, значение> помещаются в гистограмму, основанную на двумерной версии ограничения разделения "compressed" с использованием частоты как параметра источника. В другом подходе к оценке размеров результатов запроса к XML-данным также строится позиционная гистограмма на двухмерном пространстве, но здесь оба измерения прямо или косвенно связываются с нумерацией каждого узла в предопределенном порядке обхода графа XML []. Наконец, гистограммы используются также для цели аппроксимации XML в комбинации с другими структурами данных (или в их составе). Достаточно эффективным основанным на графах подходом является XSketch, в котором предпринимается попытка фиксировать как структурные характеристики файлов XML, так и характеристики значений [, ].Гистограммы используются в различных частях XSketch для фиксации статистических корреляций элементов и значений в заданных окрестностях Xsketch-графа.
В дополнение к использованию для графов XML, предлагается также применять их для фиксации степеней узлов в графах общего вида, что может служить способом сравнения графов и оценки их близости [].
