注释,注释: Предметом исследования является предложенная автором концепция
иерархических 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 research is the mathematical model in the form of recurrent integral relation system that describes the distribution of unit intervals where at least one random stream event with the arbitrary distribution function has happened. The author of the article examines numerous aspects of the numerical implementation of this system such as the Laplace transformation access method, numerical integration near discontinuity points, stability of calculations, validity check results, and particularities of real number machine arithmetic. Trub pays special attention to the connection between calculation data and semantics of the applied problem which solution is represented by these data. The methodology of the research is based on the probability theory (distribution types and qualities), numerical mathematics methods (numerical integration, interpolation, Laplace transformation), software implementation of the mathematical model and computing experiment conduction. The main conclusions of this research is the validity and numerical implementability of the mathematical model created by the author of the article as well as substantiation of the numerical solution for arbitrary distribution of the random stream events distribution. The novelty of the research is caused by the fact that the author develops a numerical solution of the bitmap-indices distribution for Weibull distribution, gamma distribution, logarithmically normal distribution, etc., and analyzes dependencies of different kinds such as the indices density function and average number of indices for the specified interval length. 

注释,注释: Предметом исследования является задача вычисления для интервала времени заданной длины распределения вероятностей количества единичных интервалов, на которых происходит по крайней мере одно событие некоторого случайного потока, заданного произвольным распределением вероятностей. Прикладное значение данной задачи заключается в том, что ее решение дает оценку количества 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.