Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

Trub I.I. Analytical probabilistic modeling of bitmap-indexes

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.


Keywords:

integration and summation, balance equations, queueing theory, poisson distribution, fetch request, database, combinatorics, disjunction, bitmap-indexes, analysis and optimization


This article can be downloaded freely in PDF format for reading. Download article


References
1. Bitmap-indeksy v Cache na globalakh. URL: https://habrahabr.ru/company/intersystems/blog/174657/ (data obrashcheniya 16.11.2016)
2. Trub I.I. SUBD Cache: rabota s ob'ektami. M.: Dialog-MIFI, 2006. 480 s.
3. Sharma V. Bitmap-indeks ili B*tree-indeks: kakoy i kogda primenyat'? URL: http://citforum.ru/database/oracle/bb_indexes/ (data obrashcheniya 16.11.2016)
4. Trub I.I. Ob optimal'noy strategii generirovaniya rezul'tatov zaprosov k Internet-serveru baz dannykh // Avtomatika i telemekhanika. 2003. № 6. S. 95-103.
5. Kleynrok L. Vychislitel'nye sistemy s ocheredyami. M.: Mir, 1979. 595 s.
6. SUBD Oracle. Administrirovanie, razrabotka i programmirovanie. Indeksy. URL: http://oracledb.ru/sql/ddl-i-obekty-sxemy/indeksy.html (data obrashcheniya 16.11.2016)
7. Kleynrok L. Teoriya massovogo obsluzhivaniya. M.: Mashinostroenie, 1979. 432 s.
8. Kirsten V., Iringer M., Kyun M., Rerig B. SUBD Cache 5: ob'ektno-orientirovannaya razrabotka prilozheniy. 2-e izd. M.: Binom, 2005. 416 s.
9. Gradshteyn I.S., Ryzhik I.M. Tablitsy integralov, summ, ryadov i proizvedeniy. 4-e izd. M.: Gosudarstvennoe izdatel'stvo fiziko-matematicheskoy literatury, 1963. 1100 s.
10. Artamonov G.T., Brekhov O.M. Analiticheskie veroyatnostnye modeli funktsionirovaniya EVM. M.: Energiya, 1978. 368 s.