RU2325690C1 - Multivariate database and method of access to multivariate database - Google Patents
Multivariate database and method of access to multivariate database Download PDFInfo
- Publication number
- RU2325690C1 RU2325690C1 RU2006133631/09A RU2006133631A RU2325690C1 RU 2325690 C1 RU2325690 C1 RU 2325690C1 RU 2006133631/09 A RU2006133631/09 A RU 2006133631/09A RU 2006133631 A RU2006133631 A RU 2006133631A RU 2325690 C1 RU2325690 C1 RU 2325690C1
- Authority
- RU
- Russia
- Prior art keywords
- address
- record
- source data
- records
- along
- Prior art date
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Description
Изобретение относится к упорядочным массивам информации, логически организованным в многомерные базы данных.The invention relates to orderly arrays of information logically organized into multidimensional databases.
Известно несколько моделей данных, отличающиеся способами организации, внутренней связи, принципов кодирования, управления доступом к данным:Several data models are known that differ in organization methods, internal communications, coding principles, data access control:
- плоская, или файловая - самый ранний и сегодня не используемый практически способ организации баз данных (БД);- flat, or file - the earliest and practically not used today method of organizing databases (DB);
- иерархическая (HDBMS = Hierarchical DBMS), основная особенность этой модели состоит в организации подчиненных связей между данными и их группами, такой, что у каждой записи есть только одна подчиненная запись. Такая модель имеет много недостатков и, поэтому, используется редко. Пример HDBMS - IMS от IBM;- hierarchical (HDBMS = Hierarchical DBMS), the main feature of this model is the organization of subordinate relationships between data and their groups, such that each record has only one subordinate record. Such a model has many drawbacks and, therefore, is rarely used. An example of HDBMS is IBM IMS;
- сетевая (MDBMS = Network DBMS), наиболее типичным представителем является CODASYL - конференцией по языкам систем управления данными (The Conference on Data Systems Languages), созданной в 1957 г. при ФБР (CODASYL was responsible for developing COBOL);- network (MDBMS = Network DBMS), the most typical representative is CODASYL - The Conference on Data Systems Languages, created in 1957 under the FBI (CODASYL was responsible for developing COBOL);
- реляционная РСУБД (RDBMS = Relational DBMS), - система управления базой данных (СУБД), построенная на реляционной модели Е.Ф.Кодда, наиболее распространенный класс СУБД в настоящее время. Наиболее известные реализации - «DB2» (IBM), «ADABAS» (Software AG), «SYBASE» (Sybase), «ORACLE» (Oracle), «MySQL» (MySQL), «PostgreSQL» (PostgreSQL.org), «InterBase» (Borland) и ее разновидности - «FireBird» и «Yaffil», а также ряд других менее известных СУБД.- relational RDBMS (RDBMS = Relational DBMS), - database management system (DBMS), built on the relational model of EF Kodda, the most common class of DBMSs at present. The most famous implementations are “DB2” (IBM), “ADABAS” (Software AG), “SYBASE” (Sybase), “ORACLE” (Oracle), “MySQL” (MySQL), “PostgreSQL” (PostgreSQL.org), “ InterBase ”(Borland) and its variants -“ FireBird ”and“ Yaffil ”, as well as a number of other less well-known DBMSs.
РСУБД оперируют с данными, организованными в таблицы, состоящие из чисел, строк и иногда ссылок на некие объекты, которые связывают данные между собой отношениями (реляциями). Расширение набора видов данных объектами другой структуры (ссылками на внешние объекты, изображениями, другими мультимедийными данными и проч.) образует подкласс РСУБД - объектно-реляционные СУБД. К классу ОРСУБД относится большинство вышеупомянутых систем.RDBMSs operate with data organized into tables consisting of numbers, rows, and sometimes references to certain objects that relate data to each other by relations (relations). Expanding the set of data types with objects of a different structure (links to external objects, images, other multimedia data, etc.) forms a subclass of RDBMS - object-relational DBMS. Most of the above systems belong to the class of ORDBMS.
Несколько особенным видом реляционных СУБД стоит постреляционная (post-relational) СУБД «CACHE'» (Intersystems Ltd).A somewhat special kind of relational DBMS is the post-relational DBMS “CACHE '” (Intersystems Ltd).
В «CACHE'» впервые появились специальные «серверные страницы» (Cache' Server Pages), представляющие собой выборки данных, предварительно вычисленные для прогнозируемых запросов, и выдаваемые по запросу без повторного вычисления над БД, что существенно увеличивает реактивность СУБД даже по сравнению с кэшированием части данных БД в оперативной памяти.For the first time, special “Cache 'Server Pages” appeared in CACHE. These are data samples pre-computed for predicted queries and issued on request without re-computing over the database, which significantly increases the DBMS reactivity even compared to caching parts of database data in RAM.
Вторая особенность «CACHE'» - это «CATs» (Cache' Application Tags), или программы, исполняемые на стороне сервера БД для записи и считывания, расчетов, циклических действий, координации и т.п., расширяемые "гиперсобытиями" (Hyper-Eventsтм Cache') - сборками (агрегатами) элементарных событий, обычно сохраняемых как элементы традиционных БД.The second feature of “CACHE '” is “CATs” (Cache' Application Tags), or programs executed on the server side of the database for writing and reading, calculations, cyclic actions, coordination, etc., expandable by "hyper events" (Hyper- Events tm Cache ') - assemblies (aggregates) of elementary events that are usually saved as elements of traditional databases.
Эти дополнительные механизмы выгодно отличают «CACHE'» от других СУБД (за исключением похожей технологии Server Data Blades в СУБД «INFORMIX» (Informix)), а именно в ее исполнительном ядре «ILLUSTRA».These additional mechanisms distinguish CACHE from other DBMSs (with the exception of the similar Server Data Blades technology in INFORMIX DBMS (Informix), namely in its ILLUSTRA executive kernel.
Традиционные СУБД хорошо обрабатывают наборы данных, организованные в таблицы с достаточно регулярной структурой по так называемой реляционной модели и ее расширениям - например, объектно-реляционной или динамической объектно-реляционной. В таких СУБД эффективно реализованы механизмы поиска, отбора, агрегирования представлений данных, и транзакции. То есть каждая БД такого рода - это статическая картина состояния информационной области. Единственная разновидность движения, которая может присутствовать в базе, это запись истории выполняемых движений как событий без применения рекурсии - вычисления и записи в БД результатов таких движений.Traditional DBMSs handle data sets well organized in tables with a fairly regular structure according to the so-called relational model and its extensions - for example, object-relational or dynamic object-relational. In such DBMSs, the mechanisms of searching, selecting, aggregating data representations, and transactions are effectively implemented. That is, each database of this kind is a static picture of the state of the information area. The only kind of movement that may be present in the database is the recording of the history of executed movements as events without recursion — the calculation and recording of the results of such movements in the database.
Для преодоления этого ограничения и используют дедуктивные БД - в них данные или события составляют логическую (экстенциональную) компоненту БД, а правила для логического вывода новых событий и их представлений - содержательную (интенциональную) ее компоненту. Дедуктивные БД в основном существуют в настоящее время только в виде теоретических моделей.To overcome this limitation, deductive databases are also used - in them data or events make up the logical (extensional) component of the database, and the rules for the logical output of new events and their representations make up the content (intentional) component of it. Deductive databases basically exist at present only in the form of theoretical models.
Требование вычисляемости (рекурсии) налагает повышенные требования к функциям СУБД, что приводит на практике к тому, что реальные СУБД могут только записывать, хранить, редактировать и представлять данные, а самостоятельная вычислительная способность СУБД остается недостижимой.The requirement of computability (recursion) imposes increased requirements on the DBMS functions, which leads in practice to the fact that real DBMSs can only record, store, edit and present data, and the independent computing ability of the DBMS remains unattainable.
Все вышеперечисленное приводит к невозможности эффективного управления большими массивами функционально связанных данных и их сборок (агрегатов), а также невозможности работы в целевых системах со слабо структурированными данными очень большой размерности, не всегда представимыми в виде таблиц и взаимных отношений между элементами.All of the above leads to the impossibility of efficiently managing large arrays of functionally related data and their assemblies (aggregates), as well as the impossibility of working in target systems with poorly structured data of very large dimensions, not always representable in the form of tables and mutual relations between elements.
Все без исключения известные СУБД в этом смысле являются статическими, то есть не обладают встроенным свойством хранения истории изменения значений хранимых данных в функции от других данных. В некоторых из упоминаемых выше СУБД хранение истории достигается специальной организацией и обработкой структуры таблиц и методов доступа к ним с получением в итоге очень ограниченных возможностей по изменению истории.Without exception, all known DBMSs in this sense are static, that is, they do not have the built-in property of storing the history of changes in the values of stored data in functions of other data. In some of the DBMSs mentioned above, history storage is achieved by special organization and processing of the table structure and access methods to them, resulting in very limited possibilities for changing the history.
В результате на известных СУБД очень сложно реализовать сколько-нибудь сложную задачу функционально связанного изменения данных, например, в функции времени и каких-либо действий над данными, а также наблюдение таких изменений в зависимости от других данных. Не меньшую трудность в реализации представляет задача отражения в СУБД данных очень большой, в частности неизвестной размерности, а также в условиях, когда тип большого числа данные заранее не известен.As a result, it is very difficult to implement any complex task of functionally related data change on well-known DBMSs, for example, as a function of time and any actions on data, as well as observing such changes depending on other data. No less difficult to implement is the task of reflecting very large data, in particular of unknown dimension, in a DBMS, and also in conditions when the type of a large number of data is not known in advance.
Резюмируя вышеуказанное, можно отметить, что построение систем, работающих с функционально связанными данными, на платформе современных СУБД сопряжено с существенными трудностями описания функциональных связей, вычисления результатов взаимодействия описываемых данными процессов и отражения их результатов в динамике.Summarizing the above, it can be noted that the construction of systems that work with functionally related data on the platform of modern DBMSs is associated with significant difficulties in describing functional relationships, calculating the results of the interaction of the processes described by data and reflecting their results in dynamics.
Многомерная модель данных обладает существенными преимуществами над другими известными логическими моделями данных, включая наиболее распространенные реляционные модели данных.A multidimensional data model has significant advantages over other well-known logical data models, including the most common relational data models.
Использование многомерной модели данных позволяет отказаться от обязательного преобразования (нормализации) исходных данных в формат реляционных таблиц, существенно увеличивающего время обработки исходных данных и объем хранимой в базе информации, а также от необходимости выполнения ресурсоемких операций соединения большого количества реляционных таблиц в процессе формирования аналитических отчетов.Using a multidimensional data model allows you to abandon the mandatory conversion (normalization) of source data to a relational table format, which significantly increases the processing time of the source data and the amount of information stored in the database, as well as the need to perform resource-intensive operations of connecting a large number of relational tables in the process of generating analytical reports.
Однако многомерная модель данных, логически представляемая в виде гиперкуба, обладает принципиальным недостатком - при увеличении количества измерений объем многомерного массива исходных данных экспоненционально возрастает.However, a multidimensional data model, logically represented as a hypercube, has a fundamental drawback - with an increase in the number of measurements, the volume of a multidimensional array of source data exponentially increases.
Увеличивающийся объем многомерной базы данных вынуждает использовать вычислительные устройства с большой оперативной памятью и высокой производительностью, что ведет к росту стоимости обработки информации.The increasing volume of a multidimensional database forces the use of computing devices with large random access memory and high performance, which leads to an increase in the cost of processing information.
Техническим результатом настоящего изобретения является повышение производительности и снижение стоимости обработки информации в составе многомерной базы данных за счет отказа от логического представления многомерного массива исходных данных в виде гиперкуба.The technical result of the present invention is to increase productivity and reduce the cost of processing information in a multidimensional database due to the rejection of the logical representation of a multidimensional array of source data in the form of a hypercube.
Заявленный технический результат достигают за счет организации прямого адресного доступа к единичным записям массива исходных данных без формирования логической структуры в виде гиперкуба или иного многомерного логического массива.The claimed technical result is achieved by organizing direct address access to individual records of the source data array without forming a logical structure in the form of a hypercube or other multidimensional logical array.
Сущность заявляемого способа поиска состоит в следующем.The essence of the proposed search method is as follows.
Логическая структура многомерной базы данных сформирована в виде множества отдельных записей данных, каждая из которых логически представляет многомерный вектор, включающий собственно значение данного и координаты его расположения относительно осей измерений логического пространства многомерного массива данных.The logical structure of a multidimensional database is formed in the form of many separate data records, each of which logically represents a multidimensional vector, including the actual value of this and its location coordinates relative to the measurement axes of the logical space of the multidimensional data array.
Исходные данные многомерной базы данных поступают в виде записей разной размерности. Идентификацию исходных данных производят на основании метаданных - системных словарей, справочников и классификаторов, содержащих эталонные символьные или цифровые обозначения наименований реквизитов данных - координат многомерных векторов.The initial data of a multidimensional database comes in the form of records of different dimensions. The initial data are identified on the basis of metadata - system dictionaries, reference books and classifiers containing standard symbolic or digital designations of names of data attributes - coordinates of multidimensional vectors.
Система индексации исходных данных основана на присвоении каждой координате многомерного вектора индекса, логически соответствующего наименованию измерения, например порядковому номеру оси измерения, и значению координаты измерения, например порядковому номеру метки на оси измерений.The initial data indexing system is based on assigning to each coordinate a multidimensional index vector that logically corresponds to the name of the measurement, for example, the serial number of the measurement axis, and the value of the measurement coordinate, for example, the serial number of the label on the measurement axis.
Метаданные, включающие наименования осей измерений, состав и количество значений их координат, позволяют описать структуру и логические взаимосвязи составляющих элементов многомерной базы данных, квалифицировать и систематизировать исходные данные.Metadata, including the names of the measurement axes, the composition and number of values of their coordinates, allows you to describe the structure and logical relationships of the constituent elements of a multidimensional database, qualify and systematize the source data.
В процессе эксплуатации массивы данных физически размещают в оперативной и долговременной памяти вычислительной установки.During operation, the data arrays are physically placed in the operational and long-term memory of the computing installation.
Формируют логическую среду, состоящую из массивов данных различной размерности. Для получения дополнительных преимуществ предлагаемого метода логическую среду физически предпочтительно располагать в оперативной памяти вычислительного устройства. Организуют хранение данных в виде файлов. Для получения дополнительных преимуществ предлагаемого метода предпочтительно физически хранить данные в долговременной памяти вычислительного устройства.Form a logical environment, consisting of data arrays of various dimensions. To obtain additional advantages of the proposed method, the logical environment is physically preferable to be located in the RAM of the computing device. Organize data storage in the form of files. To obtain additional advantages of the proposed method, it is preferable to physically store the data in the long-term memory of the computing device.
Оперативная и долговременная память вычислительного устройства оснащены устройствами физического доступа к ячейкам или блокам памяти, в которые записываются данные.The operational and long-term memory of a computing device is equipped with physical access devices to cells or memory blocks into which data is written.
Исходные данные логически представляют в виде многомерного гиперкуба, состоящего из ячеек, в которых располагают значения исходных данных. Метаданные логически представляют в виде двухмерных векторов, соответствующих осям измерений гиперкуба.The source data is logically represented in the form of a multidimensional hypercube, consisting of cells in which the values of the source data are located. Metadata is logically represented in the form of two-dimensional vectors corresponding to the measurement axis of the hypercube.
Способ доступа к отдельным записям исходных данных в многомерной базе основан на логическом сечении многомерного гиперкуба одной или несколькими плоскостями, проходящими через координаты осей измерений, соответствующие ключу информационного запроса пользователя.The way to access individual records of source data in a multidimensional database is based on the logical section of a multidimensional hypercube with one or more planes passing through the coordinates of the measurement axes corresponding to the user’s information request key.
В ячейки, расположенных в плоскости логического сечения гиперкуба, линий пересечения плоскостей, производят запись, чтение, изменение или удаление значений исходных данных.In cells located in the plane of the logical section of the hypercube, the lines of intersection of the planes, write, read, modify or delete the values of the source data.
Массив исходных данных состоит из последовательного списка многомерных записей (логически представляющих собой многомерные векторы), логически связанных между собой значениями координат по осям измерений.The source data array consists of a sequential list of multidimensional records (logically representing multidimensional vectors) logically interconnected by coordinate values along the measurement axes.
Все необходимые метаданные (словари, классификаторы) в виде двухмерных матриц (логически - двумерных векторов) постоянно поддерживают в оперативной памяти вычислительной установки для увеличения скорости доступа. Одна из строк каждой двухмерной матрицы содержит уникальные идентификаторы исходных данных, например символьные наименования данных. Другая строка - соответствующие им значения исходных данных, являющиеся значениями координат одной из осей измерений. Ячейки строк матриц метаданных логически объединены в пары «идентификатор данного - координата».All the necessary metadata (dictionaries, classifiers) in the form of two-dimensional matrices (logically - two-dimensional vectors) are constantly supported in the RAM of a computing installation to increase access speed. One row of each two-dimensional matrix contains unique identifiers of the source data, for example, symbolic names of the data. The other line is the corresponding values of the source data, which are the coordinate values of one of the measurement axes. The cells of the rows of metadata matrices are logically combined into pairs “given identifier - coordinate”.
Кроме того, для каждого массива исходных данных дополнительно организована двухмерная матрица системных счетчиков, каждая строка которой содержит координаты исходных данных (координаты по осям измерений многомерных векторов), другая строка - физические адреса расположения наиболее поздних поступивших записей в массиве исходных данных по каждой оси измерений. Фактически самая поздняя запись является наиболее удаленной от начала массива при последовательной записи данных. Ячейки строк матрицы системных счетчиков логически объединены в пары «индекс координаты - адрес расположения».In addition, for each source data array, a two-dimensional matrix of system counters is additionally organized, each row of which contains the coordinates of the source data (coordinates along the measurement axes of multidimensional vectors), the other line contains the physical addresses of the location of the latest received records in the array of source data on each measurement axis. In fact, the latest record is the farthest from the beginning of the array when sequentially writing data. The cells of the rows of the matrix of the system counters are logically combined into pairs “coordinate index - location address”.
В качестве адреса расположения записи используют физический адрес начала единичной записи, отсчитываемый от начала записи массива исходных данных.As the address of the recording location, use the physical address of the start of a single record, counted from the start of the recording of the source data array.
В состав единичных записей исходных данных дополнительно включено поле адресных указателей, каждый из которых ассоциативно связан с одной из координат по оси измерения исходного данного. В адресном указателе указывают ближайшее значение адреса более ранней записи со значением координаты, совпадающим с текущим по соответствующей оси измерения. Фактически это означает, что указывают координату записи, расположенной ближе к началу массива исходных данных.The structure of individual records of source data additionally includes a field of address pointers, each of which is associated with one of the coordinates along the measurement axis of the source data. In the address pointer indicate the nearest address value of an earlier record with a coordinate value that matches the current value on the corresponding measurement axis. In fact, this means that they indicate the coordinate of the record located closer to the beginning of the source data array.
Если для некоторой единичной записи в массиве исходных данных нет более ранних записей с совпадающим значением координаты по какой-либо оси измерений, в ее соответствующий адресный указатель помещают ссылку на адрес системных счетчиков с совпадающим значением координаты по той же оси измерения.If for a single record in the source data array there are no earlier records with a matching coordinate value on any measurement axis, a link to the address of the system counters with a matching coordinate value on the same measurement axis is placed in its corresponding address pointer.
Способ доступа к многомерной базе данных на этапах записи, чтения, удаления или изменения единичных записей исходных данных организован в следующем порядке.The way to access a multidimensional database at the stages of writing, reading, deleting or changing single records of the source data is organized in the following order.
На этапе записи исходных данных в состав базы в адресные указатели координат по осям измерений первой по порядку единичной записи включают ссылки на адреса совпадающих значений координат по тем же осям измерений системных счетчиков.At the stage of recording the initial data in the database, the address coordinates of the coordinates along the measurement axes of the first in order unit record include links to addresses of coincident coordinate values along the same measurement axes of the system counters.
При включении первой единичной записи в состав базы данных адрес начала записи имеет значение «0». Адрес окончания первой записи, равный адресу начала второй записи, имеет значение «0+ длина первой записи». Адрес начала записи (в случае первой записи, равный «0») и координаты по всем имеющимся у первой записи осям измерений (например, в виде индексов) заносят в системный счетчик.When you include the first single record in the database, the start address of the record is set to "0". The end address of the first record, equal to the start address of the second record, has the value "0+ length of the first record." The start address of the recording (in the case of the first recording, equal to "0") and the coordinates along all the measurement axes available for the first record (for example, in the form of indices) are entered into the system counter.
При включении каждой последующей единичной записи в состав базы и определения адреса начала записи (в виде величины физического смещения начала записи относительно начала массива исходных данных) из системного счетчика переписывают в адресные указатели адреса записей с совпадающим значением координат по осям измерений, а адрес текущей записи включают в системный счетчик в связи с адресом каждой из координат единичной записи по всем его имеющимся осям измерений. Для вновь появившихся измерений в системном счетчике добавляют новую запись, для уже имеющихся, изменяют адрес начала записи на адрес текущей записи.When each subsequent single record is included in the database and the record start address is determined (in the form of the physical shift of the record start relative to the beginning of the source data array), the address of the records with the same coordinate values along the measurement axes is copied from the system counter into address pointers, and the address of the current record includes to the system counter in connection with the address of each of the coordinates of a single record along all its available measurement axes. For newly appeared measurements, a new record is added to the system counter; for existing ones, the start address of the record is changed to the address of the current record.
На этапе чтения исходных данных для поиска записей, соответствующих заданным пользователем критериям поиска в виде значений или интервала значений координат по одной или нескольким осям измерений, поиск единичных записей в массиве исходных данных производят путем сравнения между собой значений всех имеющихся адресов координат по всем измерениям искомого многомерного вектора для определения наименьшего среди них значения.At the stage of reading the source data to search for records matching user-defined search criteria in the form of values or an interval of coordinate values along one or several measurement axes, the search for single records in the source data array is carried out by comparing the values of all available coordinate addresses for all dimensions of the desired multidimensional vectors to determine the smallest value among them.
На первом шаге поиска адреса всех самых последних записей с заданными координатами по осям измерений определяют из соответствующих системных счетчиков. В результате сравнения между собой значений адресов координат выбирают адрес, наиболее приближенный к началу массива исходных данных (т.е. имеющий наименьшее значение). По этому адресу осуществляют переход к единичной записи исходных данных. У найденной записи проверяют соответствие координат по осям измерений критериям поиска. При совпадении значение записи используют для анализа (выбирают для аналитического отчета).In the first step of the search, the addresses of all the most recent records with given coordinates along the measurement axes are determined from the corresponding system counters. As a result of comparing the coordinate address values with each other, the address is selected that is closest to the beginning of the source data array (i.e., having the smallest value). At this address, a transition to a single record of source data is carried out. For the found record, the correspondence of the coordinates along the measurement axes is checked with the search criteria. If they match, the value of the record is used for analysis (selected for the analytical report).
На втором и последующих шагах поиска сравнивают между собой значения адресных указателей выбранной единичной записи и, используя минимальное значение как адрес, выполняют переход к следующей единичной записи, наиболее приближенной к началу массива исходных данных.At the second and subsequent steps of the search, the values of the address pointers of the selected unit record are compared with each other and, using the minimum value as the address, they proceed to the next unit record, which is closest to the beginning of the source data array.
Выбор единичных записей по указанному алгоритму в порядке приближения к началу массива исходных данных производят вплоть до обнаружения единичной записи, один или несколько адресных указателей которой имеют адресацию на ячейки системных счетчиков. На этом процесс поиска считают завершенным.The selection of single records by the specified algorithm in order of approximation to the beginning of the source data array is carried out until the detection of a single record, one or more address pointers of which are addressed to the cells of system counters. On this, the search process is considered complete.
Для ускорения чтения записей исходных данных, в случае отсутствия у найденной единичной записи полного набора координат, соответствующим критериям поиска, на втором и последующих шагах осуществляют дополнительную выборку из массива исходных данных единичных записей, содержащих указанные координаты и расположенных по адресам, записанным в адресных указателях единичных записей, определенных на предыдущем шаге поиска.To speed up the reading of the source data records, if the found unit record does not have a full set of coordinates corresponding to the search criteria, in the second and subsequent steps, additional records are selected from the source data array containing the specified coordinates and located at the addresses recorded in the address indices of the individual records defined in the previous search step.
Значения адресных указателей единичных записей, дополнительно выбранных из массива исходных данных, используют в процессе сравнения со значениями адресных указателей первоначально выбранной единичной записи для определения минимального значения в качестве искомого адреса следующей единичной записи, т.е. наиболее приближенной к началу массива исходных данных.The values of the address pointers of individual records, additionally selected from the array of source data, are used in the process of comparing with the values of the address pointers of the initially selected unit record to determine the minimum value as the desired address of the next unit record, i.e. closest to the beginning of the source data array.
На этапе удаления записей исходных данных из состава базы на первом шаге производят поиск удаляемой единичной записи и связанных с ней ссылками следующих за ней по порядку единичных записей и/или системных счетчиков (в случае наличия ссылок на них). Для этого адреса всех самых последних записей с заданными координатами по осям измерений определяют из соответствующих системных счетчиков. В результате сравнения между собой значений адресов выбирают адрес, наиболее приближенный к началу массива исходных данных (т.е. имеющий наименьшее значение). По этому адресу осуществляют переход к единичной записи исходных данных. У найденной записи проверяют соответствие координат по осям измерений критериям поиска. При совпадении запись помечают для удаляения.At the stage of deleting records of source data from the database, at the first step, they search for the deleted individual record and the links of the following subsequent records in order of unit records and / or system counters (if there are links to them). For this, the addresses of all the most recent records with the given coordinates along the measurement axes are determined from the corresponding system counters. As a result of comparing the address values with each other, the address is selected that is closest to the beginning of the source data array (i.e., having the smallest value). At this address, a transition to a single record of source data is carried out. For the found record, the correspondence of coordinates along the measurement axes is checked with the search criteria. If matched, the record is marked for deletion.
На втором шаге в адресные указатели найденных единичных записей, связанных с удаляемой ссылками и следующих по порядку за удаляемой, записывают значения адресных указателей и ссылки на системные счетчики, содержащиеся в удаляемой записи.At the second step, the address pointers and links to the system counters contained in the deleted record are written to the address pointers of the found single entries associated with the deleted links and following the order of the deleted one.
Если имелись ссылки в системных счетчиках, то на третьем шаге в системные счетчики записывают адреса единичных записей следующих после удаляемой записи и связанных с удаляемой записью ссылками (вместе с координатами по соответствующим осям измерений).If there were links in the system counters, then in the third step, the addresses of the individual records following the deleted record and the links associated with the deleted record (together with the coordinates along the corresponding measurement axes) are recorded in the system counters.
На четвертом шаге удаляемую запись исключают из состава массива исходных данных.In the fourth step, the deleted record is excluded from the initial data array.
На этапе изменения исходных данных в составе базы в части корректировки числа и значений координат многомерного вектора без увеличения длины и размерности единичной записи выполняют следующие шаги.At the stage of changing the initial data in the database, in terms of adjusting the number and coordinate values of a multidimensional vector without increasing the length and dimension of a single record, the following steps are performed.
На первом шаге выполняют поиск единичной записи, назначенной к изменению, связанных с изменяемой ссылками следующих за ней единичных записей и записей системных счетчиков, в случае наличия ссылок на них. Для этого адреса всех самых последних записей с заданными координатами по осям измерений определяют из соответствующих системных счетчиков. В результате сравнения между собой значений адресов выбирают адрес, наиболее приближенный к началу массива исходных данных (т.е. имеющий наименьшее значение). По этому адресу осуществляют переход к единичной записи исходных данных. У найденной записи проверяют соответствие координат по осям измерений критериям поиска. При совпадении запись помечают для изменения.In the first step, they search for a single record assigned to the change associated with the mutable links of the following single records and system counter records, if there are links to them. For this, the addresses of all the most recent records with the given coordinates along the measurement axes are determined from the corresponding system counters. As a result of comparing the address values with each other, the address is selected that is closest to the beginning of the source data array (i.e., having the smallest value). At this address, a transition to a single record of source data is carried out. For the found record, the correspondence of coordinates along the measurement axes is checked with the search criteria. If matched, the record is marked for change.
На втором шаге в адресные указатели единичных записей, связанных с изменяемой ссылками и следующих за изменяемой, и в системные счетчики записывают значения адресных указателей и ссылки на системные счетчики, содержащиеся в изменяемой записи.At the second step, in the address pointers of single records associated with the variable links and following the variable, and in the system counters write the values of the address pointers and links to the system counters contained in the variable record.
На третьем шаге вносят корректировки в число и значения координат изменяемой единичной записи.In the third step, adjustments are made to the number and coordinate values of the variable unit record.
На четвертом шаге производят поиск единичных записей, связанных с измененной ссылками, следующих за измененной, и системных счетчиков (в случае наличия ссылок на них). Для этого адреса всех самых последних записей с заданными координатами по осям измерений определяют из соответствующих системных счетчиков. В результате сравнения между собой значений адресов выбирают адрес, наиболее приближенный к началу массива исходных данных (т.е. имеющий наименьшее значение). По этому адресу осуществляют переход к единичной записи исходных данных. У найденной записи проверяют соответствие координат по осям измерений критериям поиска. При совпадении запись помечают для изменения ссылок.In the fourth step, they search for single entries associated with the changed links following the changed one and system counters (if there are links to them). For this, the addresses of all the most recent records with the given coordinates along the measurement axes are determined from the corresponding system counters. As a result of comparing the address values with each other, the address is selected that is closest to the beginning of the source data array (i.e., having the smallest value). At this address, a transition to a single record of source data is carried out. For the found record, the correspondence of coordinates along the measurement axes is checked with the search criteria. If matched, the record is marked for changing links.
На пятом шаге в адресные указатели скорректированных координат измененной единичной записи записывают значения адресных указателей и ссылки на системные счетчики, содержащиеся в единичных записях, следующих за измененной.At the fifth step, the address pointers of the corrected coordinates of the changed unit record record the values of the address pointers and links to system counters contained in the unit records following the changed one.
На шестом шаге в адресные указатели единичных записей, следующих за измененной, записываются адреса скорректированных координат измененной записи.At the sixth step, the addresses of the corrected coordinates of the changed record are recorded in the address pointers of single records following the changed one.
На седьмом шаге в системные счетчики записывают адреса индексов измененной единичной записи.At the seventh step, the addresses of the indexes of the changed unit record are written to the system counters.
Внесение изменения в единичную запись исходных данных в части корректировки числа и значений координат многомерного вектора с изменением (преимущественно увеличением) длины единичной записи включает следующие шаги.Making changes to a single record of the source data in terms of adjusting the number and coordinates of a multidimensional vector with a change (mainly an increase) in the length of a single record includes the following steps.
На первом шаге выполняют удаление записи в соответствии с алгоритмом удаления исходных данных.In the first step, delete the record in accordance with the algorithm for deleting the source data.
На втором шаге выполненяют запись скорректированной записи как новой в соответствии с алгоритмом записи исходных данных.In the second step, the corrected record is recorded as new in accordance with the initial data recording algorithm.
Внесение изменения в единичную запись в части корректировки значения исходного данного без изменения числа и значений координат многомерного вектора и без изменения (преимущественно увеличения) длины записи производят в следующей последовательности.Making changes to a single record in terms of adjusting the value of the original given without changing the number and coordinate values of the multidimensional vector and without changing (mainly increasing) the length of the record is performed in the following sequence.
На первом шаге выполняют поиск и считывание корректируемой записи. Для этого адреса всех самых последних записей с заданными координатами по осям измерений определяют из соответствующих системных счетчиков. В результате сравнения между собой значений адресов выбирают адрес, наиболее приближенный к началу массива исходных данных (т.е. имеющий наименьшее значение). По этому адресу осуществляют переход к единичной записи исходных данных. У найденной записи проверяют соответствие координат по осям измерений критериям поиска. При совпадении запись помечают для изменения.In the first step, search and reading of the corrected record is performed. For this, the addresses of all the most recent records with the given coordinates along the measurement axes are determined from the corresponding system counters. As a result of comparing the address values with each other, the address is selected that is closest to the beginning of the source data array (i.e., having the smallest value). At this address, a transition to a single record of source data is carried out. For the found record, the correspondence of coordinates along the measurement axes is checked with the search criteria. If matched, the record is marked for change.
На втором шаге производят корректировку значения записи исходного данного.In the second step, the record value of the source data is adjusted.
На третьем шаге осуществляют сохранение исправленной записи на исходное место (логически и физически) его расположения в массиве исходных данных.In the third step, the corrected record is saved to its original place (logically and physically) of its location in the source data array.
Предлагаемые структура многомерной базы данных и способ доступа к ней на этапе чтения единичных записей проиллюстрированы на примере исходных данных и метаданных трехмерной базы данных.The proposed structure of a multidimensional database and the method of access to it at the stage of reading single records are illustrated by the example of source data and metadata of a three-dimensional database.
Исходные данные.Initial data.
Измерение 1 = покупатели.Dimension 1 = buyers.
Измерение 2 = регионы.Dimension 2 = regions.
Измерение 3 = виды товаров.Dimension 3 = types of goods.
Значение данных = количество проданных товаров.Data value = quantity of goods sold.
Единичные записи массива исходных данных содержат следующие реквизиты.Single entries in the source data array contain the following details.
В качестве адреса единичной записи указана условная величина смещения данной единичной записи относительно начала массива в виде целого числа предшествующих ей единичных записей.As the address of a single record, the conditional offset value of this single record relative to the beginning of the array is indicated as an integer number of single records preceding it.
В поле адресных указателей символом М обозначена ссылка на номер системного счетчика, совпадающий со значением соответствующей координаты (указанной после символа М). Цифра без символа М обозначает адрес предыдущей единичной записи (расположенной ближе к началу массива исходных данных) с таким же значением такой же координаты. Наклонная черта является разделителем адресов по координатам.In the field of address pointers, the symbol M denotes a reference to the number of the system counter that matches the value of the corresponding coordinate (indicated after the symbol M). A digit without the M symbol denotes the address of the previous unit record (located closer to the beginning of the source data array) with the same value of the same coordinate. The slash is a delimiter of addresses by coordinates.
В поле координат первая цифра обозначает порядковый номер оси измерения, две последующие цифры обозначают значение координаты на оси измерения. Наклонная черта является разделителем координат.In the coordinate field, the first digit indicates the serial number of the measurement axis, the next two digits indicate the value of the coordinate on the measurement axis. The slash is a coordinate delimiter.
В поле значений данных приведено количество проданных товаров одного вида (см. таблицу).The data value field shows the number of goods of one type sold (see table).
В общем случае исходные данные - многомерные векторы (обладающие собственными наборами измерений в пределах общего базиса измерений многомерной базы данных) могут иметь переменную длину своих логических записей, что определяет необходимость формирования в структуре массива исходных данных последовательного списка логических записей без его преобразования в двухмерную матрицу, приведенную в примере для наглядности.In the general case, the initial data — multidimensional vectors (having their own sets of measurements within the general basis of measurements of a multidimensional database) can have a variable length of their logical records, which determines the need for a sequential list of logical records in the structure of the source data array without converting it into a two-dimensional matrix, given in the example for clarity.
В рассматриваемом примере логические записи массива системных счетчиков содержат следующие поля:In this example, the logical entries of the system counter array contain the following fields:
Массив системных счетчиков включает три двухмерных матрицы (соответствующие количеству осей измерений приведенной базы данных), каждая из которых состоит из строки координат и строки системных счетчиков.The array of system counters includes three two-dimensional matrices (corresponding to the number of measurement axes of the database), each of which consists of a coordinate line and a line of system counters.
В строках координат указывают все значения координат единичных записей, включенных в массив исходных данных. В строках системных счетчиков указывают адреса расположения координат единичных записей, наиболее удаленных от начала массива исходных данных.In the coordinate lines indicate all the coordinate values of individual records included in the array of source data. The lines of the system counters indicate the location addresses of the coordinates of individual records that are farthest from the beginning of the source data array.
Процесс организации выборки информации из массива исходных данных показан на следующем примере.The process of organizing the selection of information from an array of source data is shown in the following example.
В соответствии с информационным запросом пользователя необходимо определить количество товаров вида 3.15, проданных в регионе 2.26 покупателю под номером 1.39.In accordance with the user's information request, it is necessary to determine the amount of goods of type 3.15 sold in the region 2.26 to the buyer under the number 1.39.
В соответствии со значениями системных счетчиков адрес (смещение) записи с координатой 3.15 равен 15, адрес записи с координатой 2.26 - 21 и адрес записи с координатой 1.39 - 20. Ввыполняют переход к единичной записи по адресу 15, координата которой (3.15) имеет минимальное значение среди адресов в системных счетчиках по заданным критериям (минимум из чисел 15, 21, 20), т.е. наиболее приближена к началу массива исходных данных. Эта логическая запись соответствует ключу поиска, заданному пользователем.In accordance with the values of the system counters, the address (offset) of the record with coordinate 3.15 is 15, the address of the record with coordinate 2.26 - 21, and the address of the record with coordinate 1.39 - 20. The transition to a single record at address 15, whose coordinate (3.15) has a minimum value among addresses in system counters according to specified criteria (minimum of numbers 15, 21, 20), i.e. closest to the beginning of the source data array. This logical record corresponds to the search key specified by the user.
Поиск данных далее продолжают, анализируя адресные указатели координат по осям измерений найденной единичной записи: 1.39 -11, 2.26 - 14 и 3.15 - 10. Из массива исходных данных выбирают единичную запись с адресом 10 (минимум из 11, 14, 10). Найденная запись не полностью соответствует ключу поиска. В поле адресных указателей этой записи по координате 1.39 соответствует ссылка на адрес 2 в массиве исходных данных.The data search is then continued by analyzing the address coordinates of the coordinates along the measurement axes of the found single record: 1.39 -11, 2.26 - 14 and 3.15 - 10. From the array of source data, select a single record with address 10 (minimum of 11, 14, 10). The record found does not fully match the search key. In the field of address pointers of this record at coordinate 1.39 there corresponds a link to address 2 in the source data array.
Проверка единичной записи по адресу 2 позволяет определить в ее поле адресных указателей ссылки на системные счетчики, что указывает на завершение процедуры выборки информации из массива исходных данных.Checking a single record at address 2 allows you to determine in its field of address pointers links to system counters, which indicates the completion of the procedure for selecting information from an array of source data.
Результатом выборки информации является количество товаров, проданных покупателю под номером 1.39, равное 54 единицам.The result of the selection of information is the number of goods sold to the buyer under the number 1.39, equal to 54 units.
Таким образом, в структуре массива исходных данных проведены многомерный поиск и выборка информации по координатам исходных данных (координатам многомерных векторов) без формирования дополнительного многомерного логического массива в виде гиперкуба.Thus, in the structure of the source data array, a multidimensional search and retrieval of information by the coordinates of the source data (coordinates of multidimensional vectors) was carried out without the formation of an additional multidimensional logical array in the form of a hypercube.
Поиск проведен в три шага, что в восемь раз меньше общего количества единичных записей в массиве исходных данных. Эффективность применения предлагаемой многомерной базы данных в отличие от известных возрастает при увеличении числа измерений и количества единичных записей.The search was carried out in three steps, which is eight times less than the total number of single entries in the source data array. The effectiveness of the proposed multidimensional database, in contrast to the known ones, increases with an increase in the number of measurements and the number of individual records.
Источники информацииInformation sources
1. «Distributed Database Management Systems Issues and Approaches». Автор: Amjad Dinar, Издатель University of Michigan College of Engineering, 1988, стр.46.1. "Distributed Database Management Systems Issues and Approaches." Author: Amjad Dinar, Publisher of the University of Michigan College of Engineering, 1988, p. 46.
2. «Database Management Systems»; Авторы: Raghu Ramakrishnan, Johannes Gehrke, Издатель McGraw-Hill Professional, 2002, стр.1104.2. “Database Management Systems”; Authors: Raghu Ramakrishnan, Johannes Gehrke, Publisher McGraw-Hill Professional, 2002, p. 1104.
3. «Rules in Database Systems»; Автор: Sellis, Издатель Springer, 1995, стр.373.3. "Rules in Database Systems"; Posted by Sellis, Springer Publisher, 1995, p. 373.
Claims (4)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| RU2006133631/09A RU2325690C1 (en) | 2006-09-21 | 2006-09-21 | Multivariate database and method of access to multivariate database |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| RU2006133631/09A RU2325690C1 (en) | 2006-09-21 | 2006-09-21 | Multivariate database and method of access to multivariate database |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| RU2006133631A RU2006133631A (en) | 2008-04-10 |
| RU2325690C1 true RU2325690C1 (en) | 2008-05-27 |
Family
ID=39586695
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| RU2006133631/09A RU2325690C1 (en) | 2006-09-21 | 2006-09-21 | Multivariate database and method of access to multivariate database |
Country Status (1)
| Country | Link |
|---|---|
| RU (1) | RU2325690C1 (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| RU2676018C2 (en) * | 2015-05-13 | 2018-12-25 | Хуавэй Текнолоджиз Ко., Лтд. | System and method for creating selective snapshots of database |
-
2006
- 2006-09-21 RU RU2006133631/09A patent/RU2325690C1/en not_active IP Right Cessation
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| RU2676018C2 (en) * | 2015-05-13 | 2018-12-25 | Хуавэй Текнолоджиз Ко., Лтд. | System and method for creating selective snapshots of database |
| US10417097B2 (en) | 2015-05-13 | 2019-09-17 | Huawei Technologies Co., Ltd. | System and method for creating selective snapshots of a database |
Also Published As
| Publication number | Publication date |
|---|---|
| RU2006133631A (en) | 2008-04-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6973452B2 (en) | Limiting scans of loosely ordered and/or grouped relations using nearly ordered maps | |
| CN103366015B (en) | A kind of OLAP data based on Hadoop stores and querying method | |
| CN108369587B (en) | Creating tables for exchange | |
| US20100106713A1 (en) | Method for performing efficient similarity search | |
| CN107103032B (en) | A massive data paging query method that avoids global sorting in a distributed environment | |
| US20110213775A1 (en) | Database Table Look-up | |
| KR20010083096A (en) | Value-instance-connectivity computer-implemented database | |
| US20050165733A1 (en) | System and method for an in-memory roll up-on-the-fly OLAP engine with a relational backing store | |
| WO2021232645A1 (en) | Aggregation index structure and aggregation index method for improving aggregate query efficiency | |
| Joshi et al. | Materialized sample views for database approximation | |
| AU2018345147B2 (en) | Database processing device, group map file production method, and recording medium | |
| RU2325690C1 (en) | Multivariate database and method of access to multivariate database | |
| Alam et al. | Performance of point and range queries for in-memory databases using radix trees on GPUs | |
| JP2001216307A (en) | Relational database management system and storage medium stored with same | |
| CN110399396B (en) | Efficient data processing | |
| US20240220470A1 (en) | Data storage device and storage control method based on log-structured merge tree | |
| Engle et al. | Evaluation Criteria for Selecting NoSQL Databases in a Single Box Environment | |
| CN112286995B (en) | Data analysis method, device, server, system and storage medium | |
| Han et al. | PI-Join: Efficiently processing join queries on massive data | |
| JP2000517448A (en) | Database system and method of organizing n-dimensional data set | |
| CN117555904B (en) | Method and system for quickly constructing and acquiring accurate data section in heterogeneous environment | |
| CN117540056B (en) | Method, device, computer equipment and storage medium for data query | |
| SEMI-STRUCTURED et al. | Mohamad Hasan Evgeny Panidi Vladimir Badenko | |
| CN115794960A (en) | Management method and device of relational database | |
| JP2024086652A (en) | Optimizing text filtering queries on graph data |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| MM4A | The patent is invalid due to non-payment of fees |
Effective date: 20080922 |