Аннотация: Предметом исследования является вероятностная модель иерархических
битовых индексов баз данных. Объектом
исследования являются выходные данные модели - трехпараметрическое дискретное распределение количества индексов для реализации запросов
к базе данных, параметризуемое интенсивностью занесения записей в базу, средней длиной запроса и размером крупного индекса.
Автор рассматривает такие аспекты темы как выбор гипотезы
из известных теоретических распределений, методика проверки гипотезы,
подбор функций для приближения зависимости математического
ожидания от третьего параметра, подбор функции для приближения
зависимости точки минимума математического ожидания по третьему
параметру от первых двух. Исследование таких зависимостей
объясняется тем, что оптимальный выбор именно третьего параметра
является целью проектировщика, а первые два - это исходные данные модели.
Методологией исследования являются методы математической статистики,
в частности, оценка параметров и критерий Пирсона проверки гипотез,
методы построения наилучших приближений, в частности, метод наименьших квадратов, теория кривых третьего порядка.
Основные выводы проведенного исследования: наилучшей
аппроксимацией для исследуемого семейства распределений является
распределение Пойа; наилучшими приближениями для
зависимости математического ожидания от третьего параметра являются модель Бэкона-Уаттса и теплоемкостная модель. Особым вкладом автора в исследование темы является вывод эмпирической формулы, имеющей практическое значение. Она позволяет проектировщику на основе первых двух параметров сразу, без использования громоздких расчетов по модели, получить приближенное оптимальное значение третьего параметра и построить таким образом индекс базы данных оптимального размера. Новизна исследований заключается в получении приближенных зависимостей для нового вида распределения, которое невозможно описать замкнутой формулой.

Abstract: The subject of the study is a probabilistic model of hierarchical bit indexes of databases. The object of the study is the output of the model — a three-parameter discrete distribution of the number of indexes for implementing queries to the database, parametrized by the intensity of recording records in the database, the average query length, and the size of a large index. The author considers such aspects of the topic as the choice of a hypothesis from known theoretical distributions, a method for testing a hypothesis, selection of functions for approximating the dependence of the expectation on the third parameter, selection of a function for approximating the dependence of the minimum point of the expectation for the third parameter from the first two. The study of such dependencies is explained by the fact that the optimal choice of the third parameter is the goal of the designer, and the first two are the initial data of the model. The methodology of the research is the methods of mathematical statistics, in particular, the estimation of parameters and the Pearson criterion of testing hypotheses, methods for constructing the best approximations, in particular, the method of least squares, the theory of curves of the third order. The main conclusions of the study: the best approximation for the studied family of distributions is the Polya distribution; The best approximations for the dependence of the expectation on the third parameter are the Bacon-Watts model and the heat capacity model. A special contribution of the author to the study of the topic is the derivation of an empirical formula that has practical significance. It allows the designer on the basis of the first two parameters at once, without using cumbersome calculations on the model, to obtain an approximate optimal value of the third parameter and thus construct an index of the database of the optimal size. The novelty of the research lies in obtaining approximate dependencies for a new type of distribution that cannot be described by a closed formula.

Аннотация: Предметом исследования является предложенная автором концепция
иерархических bitmap-индексов. Она заключается в том, что в целях повышения производительности обработки запросов по фильтру времени индексы поддерживаются не только для значений основной единицы времени, но и произвольных более крупных кратных единиц. Объектом исследования является построение вероятностной модели, позволяющей оценить эффективность принятия решения: какую побитовую операцию применить на очередном уровне иерархии при построении результирующей выборки - дизъюнкцию или исключающее ИЛИ. Автор уделяет основное внимание обоснованию валидности модели и сравнению результатов с построенной ранее минимаксной моделью, в которой принятие решения выполнялось по заранее установленному правилу и не зависело от текущего состояния системы.
Методологией исследования являются теория вероятностей, методы
многокритериальной оптимизации и вычислительный эксперимент, а также
сопутствующие им методы интуитивной оценки правдоподобия результатов.
Основные выводы проведенного исследования: построена и верифицирована аналитическая модель динамического выбора индексной операции; показано, что предложенная дисциплина выбора дает более высокую производительность в сравнении с минимаксной моделью и разработано программное обеспечение, позволяющее получить численную оценку этой разности; предложена модель оценки расходов на динамическое принятие решения и весовая функция, позволяющая при том или ином выборе весов оценить эффективность модели с принятием решений и сделать выбор в пользу одной из двух моделей.

Abstract: The subject of the study is the concept of hierarchical bitmap-indexes proposed by the authors. In order to improve the processing performance of queries on the time filter, the indices are supported not only for the values of the basic unit of time, but also for arbitrary larger multiple units. The object of the study is to construct a probabilistic model that makes it possible to evaluate the effectiveness of decision making: what bitwise operation to apply at the next level of the hierarchy when constructing the resulting sample is a disjunction or an exclusive OR. The author focuses on justifying the validity of the model and comparing the results with the previously constructed minimax model, in which the decision was made according to a pre-established rule and did not depend on the current state of the system. The methodology of the study is probability theory, methods multicriteria optimization and computational experiment, as well as related methods of intuitive evaluation of the likelihood of the results. Main conclusions of the study: an analytical model of the dynamic selection of an index operation has been constructed and verified; It is shown that the proposed discipline of choice gives higher productivity in comparison with the minimax model and software is developed to obtain a numerical estimate of this difference; a model for estimating the costs of dynamic decision making and a weight function that allows one to evaluate the efficiency of the model with decision making and to choose one of the two models is proposed for this or that choice of weights.

Аннотация: Предметом исследования является предложенная автором концепция иерархических bitmap-индексов. Она заключается в том, что в целях повышения производительности обработки запросов по фильтру времени индексы поддерживаются не только для значений основной единицы времени, но и произвольных более крупных кратных единиц. Объектом исследования является построение аналитической вероятностной модели таких индексов для частного случая экспоненциального распределения случайного потока занесения записей в базу данных. Автор уделяет основное внимание такому аспекту как вычисление дискретного распределения количества индексов, участвующих в обработке запроса. Методологией исследования являются теория вероятностей, методы комбинаторики, теория меры, вычислительный эксперимент. Кроме того, показано, что для исследования особенностей предложенной модели могут быть использованы новейшие понятия теории клеточных автоматов, такие как окрестность Зайцева. Основные результаты работы можно сформулировать следующим образом: введена оригинальная, интуитивно понятная концепция построения индексов; сформулированы новые, содержательные задачи оптимизации для выбора системы иерархических индексов; построена и верифицирована математическая модель, позволяющая оценить эффективность использования выбранной иерархии индексов. Показано, что в предельном случае модель естественным образом стремится к множеству фрактальной природы, в частности, одной из разновидностей канторовой пыли, для которой выведена формула вычисления ее размерности Хаусдорфа-Безиковича через прикладные параметры исходной задачи.

Abstract: The subject of the study is the concept of hierarchical bitmap-indexes proposed by the author. It is that in order to improve the processing performance of queries on the time filter, the indices are supported not only for the values of the basic unit of time, but also for arbitrary larger multiple units. The object of the study is the construction of an analytic probability model of such indices for the particular case of the exponential distribution of a random stream of recording records in a database. The author focuses on such an aspect as the calculation of the discrete distribution of the number of indices involved in the processing of the query. The methodology of the study is probability theory, combinatorial methods, measure theory, computational experiment. In addition, it is shown that the latest concepts of the theory of cellular automata, such as the Zaitsev's neighborhood, can be used to study the features of the proposed model. The main results of the work can be formulated as follows: introduced an original, intuitive concept of building indexes; new, meaningful optimization problems for selecting a hierarchical index system are formulated; a mathematical model is constructed and verified, allowing to estimate the efficiency of using the chosen hierarchy of indices. It is shown that in the limiting case the model naturally tends to a set of fractal nature, in particular, one of the varieties of Cantor dust, for which the formula for calculating its Hausdorff-Besicovitch dimension is derived through the application parameters of the initial problem.

Аннотация: Предметом исследования является задача вычисления для интервала времени заданной длины распределения вероятностей количества единичных интервалов, на которых происходит по крайней мере одно событие некоторого случайного потока, заданного произвольным распределением вероятностей. Прикладное значение данной задачи заключается в том, что ее решение дает оценку количества bitmap-индексов, попадающих в результат запроса к базе данных, отфильтрованного по диапазону времени. Объектом исследования является математическая модель задачи, построенная средствами теории вероятностей, и методы получения с ее помощью численных результатов. Методологией исследования является детальная декомпозиция случайного потока событий с учетом прикладной логики решаемой задачи и вывод на основе методов теории вероятностей уравнений, которым удовлетворяет искомая функция распределения. Важным элементом методологии является использование аппарата преобразований Лапласа и применение теоремы о свертке. Основным результатом работы является постановка оригинальной задачи теории массового обслуживания и получение ее решения в виде системы интегральных рекуррентных уравнений для набора вспомогательных кусочно-непрерывных функций, совокупность которых позволяет получить итоговую функцию. Сформулирован вычислительный алгоритм решения полученной системы. Показано, что для случая экспоненциального распределения непосредственно получаемое ввиду его простоты решение удовлетворяет системе интегральных уравнений.

Abstract: The subject of the study is the problem of calculating distribution of probabilities of the number of unit intervals for a time interval of a given length, on which at least one event of some random flow predetermined by arbitrary probability distribution occurs. The applied value of this task is that its solution gives an estimate of the number of bitmap-indexes falling into the result of a query to a database filtered by a time range. The object of the study is the mathematical model of the problem constructed by means of the theory of probability, and the methods of obtaining numerical results with its usage. The methodology of the research is a detailed decomposition of the random flow of events, taking into account the applied logic of the problem being solved and the derivation on the basis of methods of probability theory of equations satisfied by the desired distribution function. An important part of the methodology is the use of the Laplace transform apparatus and the application of the convolution theorem. The main result of the study is the formulation of the original problem of queuing theory and the derivation of its solution in the form of a system of integral recurrence equations for a set of auxiliary piecewise continuous functions whose totality allows to obtain the final function. The author formulates a computational algorithm for solving the resulting system. The article shows that, for the case of an exponential distribution, the solution immediately obtained, because of its simplicity, satisfies the system of integral equations.

Аннотация: Объектом исследования являются двоичные (bitmap)-индексы как средство повышения эффективности обработки поисковых запросов и построения отчетов в современных СУБД. Предметом исследования является математическая модель зависимости количества индексов, необходимых для построения выборки, удовлетворяющей запросу, от интенсивности добавления записей в базу данных и заданного диапазона значений запроса. Данная характеристика является наиболее значимой для оценки производительности обработки запроса, так как определяет количество операций дизъюнкции над битовыми строками, которое необходимо выполнить для получения результирующей выборки. Данная задача возникла целиком из практических потребностей ввиду критического влияния быстродействия построения отчетов на потребительскую ценность коммерческих продуктов - приложений СУБД.
Методологией исследования является вероятностное аналитическое моделирование на основе представления исходных данных в виде пуассоновских процессов, а также использование аппарата математического анализа (интегральное исчисление и суммирование рядов) для получения конечных результатов. Новизна исследования заключается в разработке математической модели, предложенной для данного объекта исследования, которая позволяет ставить широкий спектр задач анализа и оптимизации. Поставленная задача решена - получены формулы для распределения количества индексов и среднего количества индексов в одном запросе. Для каждого результата проведена оценка его достоверности на основе альтернативного подхода или правдоподобных рассуждений. Поставлены задачи построения вероятностной модели для распределений произвольного вида и оптимизации обработки запросов с помощью иерархических bitmap-индексов. Следует отметить, что сформулированная в работе задача и полученные результаты имеют и самостоятельное теоретическое значение в рамках теории массового обслуживания безотносительно к прикладной области.

Abstract: The study is devoted to bitmap-indexes as a tool of improving efficiency of processing search queries and reporting in the current database. The subject of research is mathematical model of dependence of the number of indexes, required to build a sample that meets the request, on the intensity of adding records to the database and query the specified range of values. This characteristic is most significant for evaluating query processing performance because it determines the number of disjunction operations on bit strings, required to get a result set. This problem arose entirely from the practical needs due to the critical impact of the speed of building of reports on customer value commercial products - database applications. The methodology of this study is probabilistic analytical modeling based on representations of the original data in the form of Poisson process and the use of the apparatus of mathematical analysis (integral calculus and summation rows) to get the final results. The novelty of the research is to develop a suggested mathematical model, which allows to put a wide range of problems of the analysis and optimization. The problem is solved – the author presents the formula for the distribution of the number of indexes, and the average number of indexes in a single query. For each result author evaluated reliability on the basis of an alternative approach or plausible reasoning. The paper sets the tasks of constructing a probabilistic model for the distribution of any type of query processing and optimization using hierarchical bitmap-indexes. It should be noted, that formulated problem and the results obtained have an independent theoretical value within the queuing theory without regard to the application area.