Моделювання та оптимізація доступу до інформації файлів баз даних

Abstract

This thesis addresses to investigation of the efficiency of the main methods of information search in database files, construction of the optimal method schemes, and development of new approaches to the information search in large database files. Since in many information processing systems the case of uneven distribution probabilities of request to records are typical, investigation of the efficiency and construction of the optimal method schemes is done both for the even distribution probabilities of request to records, and the cluster of laws of uneven distribution. Such close to the reality of distribution laws, as Zipf law and distribution roughly satisfying rule “80-20” are among them. Such approach allows not only to investigate the efficiency of any given method of search, and to construct the optimal scheme for any concrete law of distribution probabilities of request to records, but also to get a picture of dependency of the efficiency of the method on the change of law of distribution of probabilities. For the methods of successive revision, and one-level, two-level, r – level (r > 2) block search and binary search, formula for computing mathematical expectation of the number of comparisons, which are necessary for records search in case of different laws of distribution probabilities of requests to records, are presented. For each method of search a separate picture of mathematical expectation dependency on the change of law of distribution probabilities of request to records, and on the change of the number of file records, is presented. For the methods mentioned the values of parameters are defined, under which mathematical expectation of the number of comparisons, necessary for request to records, reaches its minimum. In case of one-level, two-level, r – level (r > 2) block search, optimal method schemes for different laws of distribution of request to records probabilities (i.e. schemes, under which mathematical expectation reaches its minimum) are constructed. Optimal number of levels for r – level block search for all considered laws of distribution probabilities of request to records is defined. General comparative analysis of the efficiency of different methods of information search in database files for the mentioned laws of distribution of request to records probabilities is conducted. In addition, a separate best search method for each concrete distribution law is worked out. New approaches to information search in database files are also suggested. In particular, a new method for the information search in database files is proposed, in which distribution of probabilities of request to records is taken into consideration. Comparative analysis of the efficiency of the method suggested for different laws of distribution probabilities of request to records, and also comparative analysis with the known information search methods in case of concrete laws of distribution probabilities of request to records are made. A new approach to the construction of approximation methods of information search in database files, based on continuous functions, is suggested. In this approach approximation of the key value, by which database file recordings are characterized, is used. Approximation functions for the real database file are constructed. Comparative analysis of the efficiency of this approach is made. For the examined laws of distribution of request to records probabilities a comparative analysis of the efficiency of suggested approaches, with the known methods of information search, has been worked out. A DBMS has been designed and implemented, in which at the time of information search in database files the laws of distribution probabilities of request to records are taken into consideration.Диссертация посвящена исследованию эффективности основных методов поиска информации в файлах БД, построению оптимальных схем методов и разработке новых подходов к поиску информации в файлах больших БД. Впервые проведено исследование ефективности методов последовательного просмотра, одноуровневого, двухуровневого, r - уровневого (r > 2) блочного и двоичного поиска для разных законов распределения вероятностей обращения к записям (равномерного, “бинарного”, Зипфа и других). Для методов одноуровневого, двухуровневого, r - уровневого (r > 2) блочного поиска построены оптимальные схемы. Определено оптимальное количество уровней для r - уровневого блочного поиска для всех рассмотренных законов распределения вероятностей обращения к записям. Предложены новые подходы к поиску информации в файлах баз данных. Проведен сравнительный анализ эффективности предложенных подходов с известными методами поиска информации для рассмотренных законов распределения вероятностей обращения к записям. Построены оптимальные схемы доступа к информации последовательных и индексно-последовательных файлов для различных законов распределения вероятностей. Приведена зависимость этих схем от изменения закона распределения вероятностей. Реализована СУБД, в которой поиск информации осуществляется с учетом законов распределения вероятностей обращения к записям.Дисертація присвячена дослідженню ефективності основних методів пошуку інформації у файлах баз даних, побудові оптимальних схем методів і розробці нових підходів до пошуку інформації у файлах великих БД. Вперше проведено дослідження ефективності методів послідовного перегляду, однорівневого, дворівневого, r - рівневого (r > 2) блочного та двійкового пошуку для різних законів розподілу ймовірностей звертання до записів (рівномірного, “бінарного”, Зіпфа та інших). Побудовано оптимальні схеми однорівневого, дворівневого, r - рівневого (r > 2) блочного пошуку. Визначено оптимальну кількість рівнів для r – рівневого блочного пошуку для усіх розглянутих законів розподілу ймовірностей звертання до записів. Запропоновано нові методи пошуку інформації у файлах БД, досліджено ефективність цих методів в порівнянні з відомими методами пошуку. Побудовано оптимальні схеми доступу до інформації послідовних і індексно-послідовних файлів для розглянутих законів розподілу ймовірностей звертання до записів. Встановлено залежність цих схем від зміни закону розподілу ймовірностей. Розроблено СКБД, в якій для кожного конкретного закону розподілу ймовірностей звертання до записів використовується найефективніший метод.