Правильная ссылка на статью:
Труб И.И..
Вероятностная модель иерархических индексов базы данных
// Программные системы и вычислительные методы. – 2017. – № 4.
– С. 15-31.
Читать статью
Аннотация: Предметом исследования является предложенная автором концепция иерархических bitmap-индексов. Она заключается в том, что в целях повышения производительности обработки запросов по фильтру времени индексы поддерживаются не только для значений основной единицы времени, но и произвольных более крупных кратных единиц. Объектом исследования является построение аналитической вероятностной модели таких индексов для частного случая экспоненциального распределения случайного потока занесения записей в базу данных. Автор уделяет основное внимание такому аспекту как вычисление дискретного распределения количества индексов, участвующих в обработке запроса. Методологией исследования являются теория вероятностей, методы комбинаторики, теория меры, вычислительный эксперимент. Кроме того, показано, что для исследования особенностей предложенной модели могут быть использованы новейшие понятия теории клеточных автоматов, такие как окрестность Зайцева. Основные результаты работы можно сформулировать следующим образом: введена оригинальная, интуитивно понятная концепция построения индексов; сформулированы новые, содержательные задачи оптимизации для выбора системы иерархических индексов; построена и верифицирована математическая модель, позволяющая оценить эффективность использования выбранной иерархии индексов. Показано, что в предельном случае модель естественным образом стремится к множеству фрактальной природы, в частности, одной из разновидностей канторовой пыли, для которой выведена формула вычисления ее размерности Хаусдорфа-Безиковича через прикладные параметры исходной задачи.
Ключевые слова: иерархические bitmap-индексы, случайный поток событий, экспоненциальное распределение, полная вероятность, фрактальное множество, Канторова пыль, размерность Хаусдорфа-Безиковича, дизъюнкция, исключающее ИЛИ, окрестность Зайцева
Библиография:
McNutt B. The Fractal Structure of Data Reference: Application to the Memory Hierarchy. - Kluwer Academic, Boston, 2000. - 132 p.
Bulut A., Singh A.K. Indexing and Querying Data Streams.-In book DataStreams: Models and Algorithms (edited by Charu C. Aggarwal).-Springer, 2007, 373 p.-pp.237-259.
Труб И.И. О распределении количества bitmap-индексов для произвольного потока занесения записей в базу данных //Программные системы и вычислительные методы.-2017.-№ 1.-с.11-21. DOI: 10.7256/2454-0714.2017.1.21790
Труб И.И. Аналитическое вероятностное моделирование bitmap-индексов //Программные системы и вычислительные методы.-2016-№ 4.-с.315-323. DOI: 10.7256/2305-6061.2016.4.2109
Мандельброт Б. Фрактальная геометрия природы.-Москва, Институт компьютерных исследований, 2002.-656 с.
Градштейн И.С., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений.-СПб, БХВ, 2011, 7-е изд.-1232 с.
Деменюк С.Л. Фрактал: между мифом и ремеслом.-Академия исследования культуры РИНВОЛ, СПб, 2011.-296 с.
Кроновер