WO2013039420A2

WO2013039420A2 - Relational database and operation mode of relational database

Info

Publication number: WO2013039420A2
Application number: PCT/RU2012/000011
Authority: WO
Inventors: Andrey Evgenevich Vasilev
Original assignee: Andrey Evgenevich Vasilev
Priority date: 2011-09-16
Filing date: 2012-01-17
Publication date: 2013-03-21
Also published as: WO2013039420A3; RU2011137977A

Abstract

A relational database is disclosed, made in the form of a linked data structure, comprising blocks of header, relations, domain names and attributes as components, located respectively at the entry point, root, nodes and leaves of the search tree, tuples comprising a hierarchical multiset of attributes with variable composition, and binary fragments. Binary fragments comprising identifiers, data types IDs and codes of database, relations, domain names and attributes. A relational database control method is also disclosed, based on versioned execution of write, change, delete transactions, and compression of data in the mode of competitive access to the database, as well as on recovery of completeness and consistency of data after abnormal DB termination without use of data backup.

Description

Relational database and operation mode of relational database .

DESCRIPTION

FIELD OF THE INVENTION

The invention relates to ordered arrays of information that are logically organized into relational databases stored on nonvolatile media, and to methods of relational database control realized on the basis of software processed via computers .

Relational Database (further - DB) comprises metadata, data search trees and binary fragments of information.

Metadata comprise attributes that represent characteristic of DB objects subject area, domains to which attributes of the same type belong to and relations defined in domains. _

Data represents informational pattern of the subject area and is realized in the form of tuples, each consisting of a number of attributes. Attributes in tuples are represented by their identifiers (IDs) that correspond to names, numbers and other designation indicators of subject area objects characteristics. Identifiers are assigned data types- in order to process information with computers.

Tuples are united into relations. Relations comprise headers that represent relations schemes and consist of domains' id's that correspond to names of subject area objects characteristics types. One or more attributes within the^" tuple are external keys that logically link different relations. Each relation can comprise several sections each including a composition of tuples. Identifiers of relations correspond to names of subject area objects types.

Search tree is a hierarchical structure, comprising entry point with permanent (constant) position within the hierarchic structure. Said entry point comprising pointer to the root, Ί

and the root, nodes and leaves themselves with variable positions within hierarchic structure and containing descriptors. Positions of the root, nodes and leaves vary depending on search keys composition, said composition comprising metadata identifiers as said keys.

Descriptors of search tree elements comprises metadata identifiers, pointers to search tree elements located on a lower hierarchy level and links to data.

Search tree root is located at the upper level of hierarchy, nodes - on middle levels and leaves - on the lowest hierarchy level. Root and nodes divide the search tree into left and right sub-trees. Search keys are sorted in descending order in left subtrees and in ascending order in right subtrees.

Binary fragments comprise unstructured data, in a form of text, graphics, audio, video, etc.

Persistent values of metadata, data, search trees and binary fragments are stored in separate files on media and are united into a DB with links comprising filenames.

RAM maintains metadata temporal values that are intended for acceleration of DB access.

DB control method comprises performing of data writing, changing, deletion, reading and compression as well as restoring completeness and consistency thereof after the abnormal termination of access to DB.

All operations are performed as transactions, i.e., logical units of information processing. Transaction consists of groups of consequent actions that meet requirements of atomicity, consistency, insularity and durability of data.

In order to provide competitive access to the database operations of data writing, changing or deletion are performed in form of separate data versions.

Completeness and consistency of information is provided by performing of each transaction in delayed processing mode - only after completion of data backup into transactions log. In a case of abnormal termination of translations during backup, the information is not stored into the database. In a case of abnormal termination on subsequent steps the information is to be restored from backup copy and saved to DB.

PRIOR ART.

The subject of the invention relates to relational databases and methods of control thereof. The database control system IBM System R, disclosed in /l/, 12/ , /3/ is chosen as prior art .

The prior art DB comprises data structures of two types:

Two-dimensional array, i.e., a table;

Hierarchic structure, i.e., a logical tree.

Metadata is stored in relations table where lines comprise identifiers of relations and links to domains tables' files, and in domains tables where lines represent identifiers of domains, links to files of search trees and alternative links to data tables files. Headers of domains' tables comprise types of data of attributes identifiers.

Each search tree corresponds to one of a number of domains. Said each domain is indexed within the relation. Entry point is located at the beginning of the search tree file. Roots, nodes and leaves are placed in their order of writing to the search tree file and comprise fixed descriptors sets.

Descriptors of search tree elements are composed of attributes identifiers, pointers to search tree elements on a lower hierarchy level, links to data tables' files and data tables' line numbers that comprise tuples with coinciding attributes identifiers.

In case of domains indexation waiving, data search is made by direct access to data tables files from domain tables and consequent examination of all data table lines.

The data is presented by attributes tuples stored in data tables, each corresponding to one relation. Tables' headers correspond to relations schemes, columns in tables - to domains that define relations, and lines in tables - to tuples .

Attributes tuples are presented by their identifiers. Attributes identifiers comprise undefined values (NULL values) that are unknown at the moment of writing information to the DB.

Tuples related to the same relation comprise constant set of attributes and do not comprise repeating attributes related to the same domains. Hierarchy of attributes is maintained by inclusion of additional attributes into the tuples, identifiers of said additional attributes comprise order of main attributes nesting into the tuple.

In case of storing of (information) objects images of subject area in the database, said objects images comprising variable sets of repeated characteristics (multi-sets) , the input information is normalized by dividing thereof into several tuples each comprising permanent sets of unique attributes (simple sets) included into two or more data tables .

In order to organize parallel access to the DB, each data table can comprise a number of sections, physically located on separate media.

Tuples also include attributes, comprising identifiers acting as links to binary fragments that contain unstructured data and are stored in the DB as files with various record formats .

DB contains additional data structure - transactions log, for backup copying and temporary storing of data copies and metadata. In a case of supporting competitive access to DB, the transactions log also temporarily stores latest versions of the data for providing required isolation level of transactions . In order to accelerate access to the DB, RAM of the computer stores metadata temporal values in a form of copies of relations and domains tables.

The prior art DB control method is based on version-based execution of transaction of writing, changing, deletion, reading and compression of data in competitive mode as well as restoring completeness and consistency of information after abnormal termination of access to DB via backups copying.

Each transaction of data writing, changing or deletion is made in the mode of delayed action - the first step is information backup copying to transactions log, the second step is writing, changing or deleting information within the metadata, data, or search trees themselves.

Metadata and data are written to new added lines in tables or to existing lines in tables that are marked as unused. Data into search trees is written into previously created or newly created trees elements. Binary fragments are recorded into separate files.

Information in metadata tables is changed or deleted by changing or deleting values in corresponding tables lines.

Information in data tables is deleted by marking lines with deleted tuples as unused. Information in data tables is changed by writing new versions of tuples, including full set of new, changed and unchanged attributes, into new or marked as unused lines in tables.

Information in search trees is changed or deleted by adding new or freeing existing tree elements, as well as altering or deleting values of descriptors in tree elements.

Binary fragments are changed by new files recording, binary fragments are deleted by deleting existing files.

Data is read via search trees examining or by scanning of data tables, in case of refusal to index domains which attributes are included into search key. Data is compressed by deleting unused tables lines and search trees elements from files.

Restoring completeness and consistency of information after abnormal termination of access to DB is performed as follows: in case of abnormal termination of access to DB during writing into transaction log, the backup copy of information is deleted from transaction log file;

in case of abnormal termination of access to DB during writing into metadata tables, data tables and search trees, the information is restored basing on its backup copy stored in the transactions log.

The prior art has the following disadvantages.

The database comprises a large number of data structures copies stored in separate files. Consequently, it greatly increases the number of hits to the media causing low speed of data reading/writing.

The absence of support for variable content and multi-sets of attributes in tuples makes necessary to use normalization of input data, thus multiply increasing the number of data table files.

Attributes hierarchy in tuples is maintained by additional attributes including thus increasing DB volume.

Attributes of tuples that are multiply repeated in data tables lines are represented by their identifiers with possible record length from several bytes to several hundred bytes, thus increasing DB volume.

Storing of tuples versions with complete attributes sets also leads to increasing DB volume.

Organization of parallel access to DB files by dividing each table into sections stored on different media has significant limitations due to the necessity to use media with non-unified volume of data recording, corresponding to the size of data table sections, related to various relations and differing in number of columns and lines. Search trees require balancing their elements in case of descriptors fixed sets overflow in search trees elements or attributes sets changing in domains. Balancing can be performed on up to half elements of search tree. During balancing, data tables remain accessible only in data scanning mode .

Information compression by deleting data tables lines and search trees elements from files causes data table and search trees blocking during the whole compression period.

The presence of plurality of types and data structures copies, as well as alternative ways of access to data tables causes the necessity for backup copying with use of transactions log, that slows database access.

Technical result of the disclosed invention lies in decreasing DB volume and DB access time.

BRIEF DESCRIPTION OF THE INVENTION

Technical result is achieved by making a DB as a linked data structure and by denial of data backup copying.

Search tree is represented in the solitary instance. Header block is located in the entry point, relations block - in the root, domains blocks - in nodes and attributes blocks - in leaves .

Blocks of the header, relations, domains and attributes, tuples and binary fragments comprised the linked data structure .

Header block comprises the following elements:

- front-end descriptor including pointer to the start point of linked data structure and size thereof;

- root descriptor comprising pointer to start point of relations block and its size.

Metadata in blocks of relations and domains are represented by descriptors. Each of said descriptors corresponds to single metadata and contains pointer to the beginning of block and size of the block placed on a lower hierarchy level. Metadata in attributes' blocks are represented by descriptors. Each of said descriptors corresponds to single metadata and comprises pointer to beginning of last tuple, its size and number of all tuples containing descriptors with coinciding attributes codes.

Positions of descriptors in blocks correspond to metadata codes values that are equal to index numbers of relations and domains within the DB, as well as index numbers of attributes within domains.

Tuples are composed of attributes hierarchies and can include repeating attributes or groups of attributes. The same relation tuple may contain variable number of attributes;

Each attribute within the tuple is represented by its descriptor which comprises:

initial address of descriptor in the linked data structure; index number of data write, change or deletion transaction; domain code;

attribute code;

level of descriptor hierarchy in the tuple;

pointer to the beginning of previous tuple comprising descriptor with coinciding codes of domain and attribute;

size of previous tuple containing descriptor with coinciding codes of domain and attribute;

number of previous tuples containing descriptor with coinciding codes of domains and attributes.

Descriptors in the tuple are ordered in ascending order by hierarchy levels and are grouped by subsets of repeating descriptors with coinciding codes of domains.

Descriptors with null values of attributes codes located on upper levels of tuple hierarchy define positions of descriptors with defined values of codes of attributes located on lower levels of tuple hierarchy. Value of descriptor attribute code located in the first hierarchy level of tuple is equal to index number of the tuple within the relation.

Binary fragments comprise identifiers, identifiers data types and codes of database, relations, domains and attributes.

Tuples are linked to binary fragments with assigned descriptors of tuples which hierarchy levels, domains codes and attributes codes comprise null values, binary fragments addresses and binary fragments size correspondingly.

Database may comprise several linked data structures, each of said structures further comprising units of headers, relations, domains and attributes, group of tuples included into all relations and grouped in accordance with values of digits in lower positions of tuples index numbers, and binary fragments linked to tuples. Value of DB code within the binary fragment comprise lower position digits in index numbers of tuples ordered by ascending power.

DB control method is based on versioned execution of transaction of data writing, changing, deletion, reading and compression in competitive mode as well as restoring of data completeness and consistency after abnormal termination of access to DB. All transactions are made in the direct (monopolistic) access to database mode without use of data backup .

Data writing is performed in the following way:

writing of header, relations, domains and attributes blocks; replacement of domains and attributes identifiers with codes of descriptors in tuples;

writing tuples and binary fragments;

changing values of descriptors in attributes blocks;

changing size value of linked data structure of front-end descriptor in header block.

Data changing or deletion is performed in the following way: writing of new versions of header block, relations, domains and attributes blocks;

writing of derived versions of tuples comprising new, altered and/or deleted descriptors of parent versions of tuples and new versions of binary fragments;

changing of descriptors values in attributes blocks;

Information reading is performed in the following way:

search for and consolidation of parent and child versions of tuples ;

search for binary fragments linked to consolidated tuples; replacement of descriptors codes with identifiers of domains and attributes in consolidated tuples.

Information is compressed in the following way:

switching to database exclusive access mode;

writing null value into pointer to the beginning of linked data structure of front-end descriptor in old version of header block;

writing new versions of header block, relations, domains and attributes blocks;

switching to database competitive access mode;

searching for and consolidation of tuples and binary fragments linked to old versions of blocks of header, relations, domains and attributes;

writing consolidated tuples and binary fragments along with linking them to new versions of blocks of header, relations, domains and attributes;

reading tuples and binary fragments, that have not been consolidated, with old versions of blocks of header, relations, domains and attributes;

writing new incoming tuples and binary fragments and linking them to new versions of blocks of header, relations, domains and attributes; changing, deletion and reading- of consolidated and new incoming tuples and binary fragments with use of new versions of blocks of header, relations, domains and attributes;

changing values of descriptors in new versions of attributes blocks ;

changing size value of linked data structure of front-end descriptor in new version of header block.

deleting from file data located before new version of header block in linked data structure.

Restoring completeness and consistency of data after abnormal termination of access to DB is performed using the following steps:

reading descriptors of block of header, relations, domains, tuples index numbers and attributes blocks linked thereto.

reading tuple located with the biggest shift in relation to the beginning of linked data structure in accordance with value of attributes block descriptor pointer, said pointer having code, which coincides with index number of tuple and binary fragment linked thereto;

estimation of linked data structure size;

reading tuples written with positive offset to estimated value of linked data structure size;

deleting tuples written during latest transaction with positive offset to estimated value of linked data structure size and binary fragments linked thereto;

adjustment of descriptors values of attributes blocks with the beginning, size value and the number of tuples written with positive offset to estimated value of linked data structure size;

changing size value of linked data structure in the front- end descriptor header block.

BRIEF DESCRIPTION OF DRAWINGS

Fig. 1. Linked data structure diagram.

Fig. 2. Relation and tuple content diagram. Fig. 3. Tuple versions diagram.

Fig. 4. Tuple grouping diagram.

DETAILED DESCRIPTION OF INVENTION

SYSTEM DESCRIPTION

Technical result in respect of system is achieved by making a DB as a linked data structure comprising the following components :

header block;

relations block;

domains block;

attributes block;

tuples ;

binary fragments.

Linked data structure in stored in a file as contiguous sequence of components thereof.

Header block is located in the beginning of linked data structure coinciding with BOF. Blocks of relations, domains and attributes, tuples and binary fragments are contained in linked data structure in order of their writing to file.

Header block is located at the entry point into linked data structure and serves for further passage to search tree root. Blocks of relations, domains and attributes are located in root, nodes and leaves of the search tree correspondingly that are interlinked with pointers. Blocks of attributes are linked by pointers with tuples that were last written to the linked data structure.

Tuples of the same relation comprising descriptors with coinciding domains and attributes codes are interlinked with pointers. Tuples of different relations are united by external keys, said keys comprising one or more descriptors with coinciding codes of domains and attributes.

Tuples are linked to binary fragments containing identifiers, identifiers data types and codes of DB,. relations, domains and attributes. Index numbers of relations and domains within DB and index numbers of attributes within domains are used as codes for relations, domains and attributes. Values of unified criteria of grouping for tuples within DB are used as DB codes.

Blocks of header, relations, domains and attributes comprise of descriptors that define position of lower hierarchy level components in the linked data structure.

Header block comprises descriptors of the following types: front-end descriptor including pointer to the start of linked data structure and size of linked data structure;

root descriptor comprising pointer to start and size of relations block.

Relations block comprises descriptors of one type, each descriptor comprising pointer to the beginning of domains block and size of domains block for which the relation is defined. Descriptors in the block occupy fixed positions according to values of relations codes.

Domains blocks comprise descriptors of one type, each one comprising pointer to the beginning of attributes block and size of attribute block within the domain. Descriptors in blocks are located in fixed positions according to domains codes values.

Attributes blocks comprise descriptors of one type, each one comprising pointer to the beginning of the last tuple written, size of the last tuple written and number of tuples comprising descriptors with coinciding attributes codes. Descriptors in the blocks are located in fixed positions according to attributes codes values.

Blocks of relations, domains and attributes comprise a fixed number of descriptors defined for each kind of blocks separately. Fixed number of descriptors can be increased by writing new versions of blocks. Fixed number of descriptors can be decreased by changing content of metadata during DB replicatio . Tuples are compete information images of subject area objects and do not require normalization of input information.

Tuples comprise descriptors of one type corresponding to tuple attributes. Each descriptor comprises:

descriptor initial address in linked data structure;

index number of write, change or deletion transaction;

domain code;

attribute code;

descriptor hierarchy level in the tuple;

pointer to the beginning of previous tuple comprising descriptor with coinciding codes of domain and attribute,"

size of previous tuple comprising descriptor with coinciding codes of domain and attribute;

number of previous tuples comprising descriptors with coinciding codes of domains and attributes;

Initial address is unique for each copy of descriptor. Initial address is assigned during first writing of descriptor copy and is stores (stays) permanent within all versions of the tuple.

Index number of writ, change or deletion transaction is assigned in the order tuples are written to DB. Transaction index number is used for consolidation of tuple versions in accordance to their writing to DB order. Transaction index number is also used for data reading in order to select from DB tuples actual at the moment of beginning of data reading.

Number of tuples contained in descriptors of attributes blocks and tuples blocks is used for data search optimization in a case of presence of two or more descriptors with various repetition rate within DB in search key.

Tuples descriptors hierarchy levels are numbered from the upper level. Descriptors with attributes codes equal to index numbers of tuples within relations are located on the topmost hierarchy level. Hierarchy levels of other descriptors correspond to hierarchy levels of characteristics of typical objects of DB subject area.

Descriptors of tuples are ordered in ascending order by hierarchy levels and are grouped by subsets of repeating descriptors with coinciding codes of domains.

Descriptors with null values of attributes codes located in upper levels of tuples, corresponding to the relation scheme and designating absent subject area characteristics, hierarchy define positions of descriptors with defined values of codes of attributes located in lower levels of tuples hierarchy.

Tuples are linked to binary fragments with assigned tuples descriptors. Domains codes and attributes codes of assigned tuples descriptors comprise binary fragments addresses and size thereof correspondingly. Each assigned tuple descriptor comprises null value of hierarchy level that is the indicator of descriptor assignment.

The biggest value of the whole range of positive integers of defined precision is normally used as null value in descriptors of blocks and tuples. A plurality of positive integers from 1 to the value previous to the biggest value is used for defined values. Zero is used for identifying deleted descriptors of blocks and tuples as well as a code (indicator) for service relation, code (indicator) for service domain of tuples index numbers and code (indicator) of attribute of service tuple descriptor located in the first hierarchy level. During data compression, zero values of blocks descriptors are replaced with null values symbolizing readiness of descriptors for linking to new incoming components located at a lower hierarchy level of linked data structure.

Structure of each relation is presented as a service tuple with complete set of descriptors containing defined values of domains codes and null values of attributes codes. As an exception, the value of descriptor attribute code on first hierarchy level equals to zero. The DB additionally comprises a service relation with tuples linked to binary fragments. Said binary fragments comprising identifiers, identifiers types and DB codes, relations, domains and attributes. Service relation is defined at service domain of index numbers of tuples and service domain of metadata types. Service domain of metadata types comprises attributes which have following values of identifiers: "Database", "Relation", "Domain", and "Attribute".

Service tuple of service relation comprises two descriptors which domains codes correspond to service domain of metadata types. First descriptor located at a relatively higher hierarchy level of the tuple contains attribute code value corresponding to "Domain" metadata type. Second descriptor located at a lower hierarchy level of the tuple contains attribute code value corresponding to "Attribute" metadata type.

Descriptors with null domains codes values are not included into service tuples.

Besides identifiers, identifiers data types and metadata codes, binary fragments comprise delimiters. Binary fragments can also comprise variants of writing identifiers in various national languages, encoding standards, allowable identifiers attributes, logical conditions of including attributes into domains, etc.

Identifiers, data types and index numbers codes of tuples are not part of binary fragments due to coinciding of their values and data types of identifiers and codes.

Linked data structure may comprise binary fragments linked to tuples that are not part of service relation and that in their turn comprise other kinds of unstructured data.

In order to organize parallel access to data, the database can comprise several linked data structures, each stored in a separate file and further comprises:

header, relations, domains and attributes blocks; group of tuples included into all relations and grouped according to values of digits in lower positions of tuples xindex numbers and binary fragments;

binary fragments linked to tuples.

DB codes within binary fragments of linked data structures comprise lower positions of tuples index numbers placed in digits ascending order and being values of united grouping criteria .

Grouping of all tuples with use of united grouping criterion allows to evenly distribute information in separate files and to use media with unitized recording capacity.

Linked data structure diagram is shown in fig 1.

In the diagram, vertical DOWN arrows interlink hierarchy levels of the linked data structure. Vertical UP arrow represents size of the linked data structure in front-end descriptor of header block. Diagonal arrows link tuples comprising descriptors with coinciding codes of domains and attributes .

Horizontal arrows correspond to external keys that logically link tuples of different relations.

Root descriptor of the header block is linked to relations block. Descriptors of relations block are linked to domains blocks that define relations. Descriptors of each domains block are linked to attributes blocks included into the domain. Descriptors of each attributes block are linked to last tuples comprising descriptors with coinciding attributes codes. Tuples are linked to previous tuples comprising descriptors with coinciding codes of domains and attributes. Tuples are also linked to binary fragments.

Relation and tuple content diagram are shown in fig 2.

Scheme of relation comprising personal data is shown as an example. Scheme of relations is represented by a service tuple. Additionally, a tuple is shown that represents an information image of a certain object of subject area. For convenience values of identifiers for domains and attributes are shown within tuples descriptors.

The set of service tuple descriptors corresponds to full set of domains that define the relation. Descriptors of the service tuple are located at the hierarchy levels corresponding to hierarchy levels of typical object characteristics of subject area. The descriptor corresponding to index number of tuple within the relation where attribute code value is zero is located on the first level of hierarchy. On other hierarchy levels attributes codes of descriptors are assigned null values.

The tuple set that represents data image of a certain object in subject area comprises repeating descriptors groups, with coinciding values of hierarchy levels and codes of domains and differing in values of attributes codes. Tuple descriptors hierarchy levels correspond to hierarchy of descriptors of service tuple with coinciding domains codes. All descriptors of tuple have defined values of attributes codes, except for the descriptor taking 15^th (fifteenth) position in the tuple and having null value of attribute code. This descriptor serves to localize within the tuple other descriptors located on lower hierarchy levels.

Tuple versions diagram is shown in fig. 3.

The diagram shows parent and child versions of tuple. Names and values of initial addresses, domains codes and attributes codes within descriptors of tuple versions are shown for convenience .

Parent version of the tuple comprises the set of descriptors included into linked data structure at first recording of the tuple to file.

The child version of tuple comprises:

permanent descriptor of parent tuple located on the first hierarchy level, the hierarchy code of said descriptor is equal to index number of parent tuple within the relation; deleted descriptor of parent tuple the initial address of which is equal to 20, attribute code value has been changed from 57 to 0 (indicator of deletion);

changed descriptor of parent tuple which initial address is equal to 32, attribute code value is changed from 22 to 98;

supplemental descriptor of child tuple with initial address 40, value of domain code 29 and value of attribute code 62; supplemental descriptor of child tuple with initial address 38, value of domain code 28 and null attribute code value, serving for localization of descriptor with initial address 40.

Tuple grouping diagram is shown in fig. 4.

The diagram shows tuples grouping according to values of digits in lower positions of index numbers of tuples 0 to 9. As a result of grouping 10 (ten) linked data structures appear .

Each linked data structure comprises complete set of blocks of header, relations, domains and attributes and a part of tuples and binary fragments. Index numbers of tuples written to the first linked data structure end with 0, index numbers of tuples written to the second linked data structure end with 1, and so forth to tenth linked data structure where index numbers end with 9.

OPERATION DESCRIPTION.

Technical result in the part of device operation method is achieved by performing all kinds of transactions in DB direct access mode without data backup copying.

Denial to use data backup is based on writing new data only to the end of linked data structure and on leading data writing mode in relation to metadata writing.

Header, relations, domains and attributes blocks are written to file firstly. Number of descriptors in blocks is assigned with regards to possible expansion of metadata during DB operation . Header block is written with defined values of front-end descriptors and null values of root descriptor.

Relations block is written with null values of descriptors. Upon finishing of relations block writing null values are replaced with defined values in root descriptor of header block and the size of the linked data structure in front-end descriptor of header block is changed.

Domains blocks are written with null values of descriptors. Upon finishing of domains blocks writing null values are replaced with defined values in relations block and the size of the linked data structure in front-end descriptor of header block is changed.

Attributes blocks are written with null values of descriptors. Upon finishing of attributes blocks writing null values are replaced with defined values in domains blocks and the size of the linked data structure in front-end descriptor of header block is changed.

On the second step, tables of metadata comprising temporal values of identifiers, types of identifiers data and metadata codes are formed in computer's RAM. After writing temporal values of metadata to tables, their persistent values are written to a linked data structure within binary fragments.

Each metadata table corresponds to one of domains. The table comprises the header and one or more pairs of columns. Each pair of columns corresponds to one national language for identifiers writing. Each paired column comprising the identifiers themselves is sorted by metadata codes in ascending order. The paired column comprising the identifiers codes is sorted by metadata codes in ascending order.

In case of adding identifiers of metadata, number of lines in tables increases. In case of deleting metadata identifiers corresponding lines in tables are assigned the lowest possible identifiers values, and metadata codes values ^remain unchanged. After finishing the data compression, tables lines that correspond to previously deleted identifiers are assigned the highest possible identifiers values, their positions becomes the reserve for future writing of new identifiers values without increasing number of lines in the table.

This metadata table header contains:

type of identifiers data;

total number of lines in the table;

number of lines in the table comprising deleted identifiers values ;

number of lines in table comprising reserved positions for writing new values of identifiers.

Each table of tuples index numbers, unlike other metadata tables, corresponds to one of relations. The table header comprises the total number of used index numbers of tuples. The table comprises one column of metadata codes. Lines of the table comprise reserve positions for assigning index numbers to new written tuples. After assigning index numbers to tuples, lines corresponding thereto are erased from the table.

In computer' s RAM, there is a counter of index numbers of write, change or delete transactions. Temporal value of the counter is equal to the latest used index number of transaction. After temporary interruption of access to DB, temporal value of the counter is restored basing on persistent values of index numbers of tuples descriptors latest recorded to DB.

Besides metadata tables and transactions index numbers counter, RAM can comprise second copies of metadata blocks, said metadata blocks comprising temporal values of blocks descriptors. Modification of temporal values of descriptors of second copies is made before modification of persistent values of descriptors of first copies of blocks stored in file. In order to reduce number of hits to media, modification of persistent values of descriptors is made at a preliminarily assigned periodicity, e.g., once per 24 hours. Conformity of transactions with the requirements of accordance, insularity and durability of data in this case is provided by:

actualization of persistent value of the size of the linked data structure of front-end descriptor in first copy of header block during restoration of completeness and consistency of data after abnormal termination of DB access;

supporting of temporal values of descriptors permanence in second copies of relations blocks and domains within the period between modifications of persistent values of descriptors in first copies of relations blocks and domains; reflecting of temporal values of descriptors containing in second copies of attributes blocks, in values of tuples descriptors recorded to file.

Compliance of transactions with requirements of data atomicity within the period between modifications of persistent values of descriptors of first copies of blocks is supported by consequent writing of tuples within their own transactions. This kind of support of atomicity is unavailable in tuples within the last transaction.

The third step comprises consequent reading values of header block, relations, domains, up to reading values of block of attributes intended for reflecting of new written tuples in descriptors.

Forth step comprises forming tuples and binary fragments linked thereto in computer's RAM. In accordance with identifiers and metadata codes tables, domains identifiers and attributes are replaced with descriptors codes in tuples.

Fifth step comprises writing of tuples and binary fragments to file.

At the sixth step, null values are replaces with defined in descriptors of attributes blocks (when writing the first tuple) or attributes blocks descriptors are changed (in case of writing posterior tuples.) Lastly, size of the linked data structure in front-end descriptor of header block is changed.

Alteration and/or deletion of metadata in DB is performed by changing values of blocks descriptors (in case of sufficient number of descriptors in blocks) or by writing of new versions of blocks (in case of insufficient number of descriptors in blocks) .

Alteration or deletion of data in DB is made by increment writing of parent and child versions of tuples. Each preceding version of tuple appears to be parent to the next version in the order of tuples writing.

Child versions of tuple comprise additional and/or modified descriptors of previous parent versions of tuple as well as permanent descriptor of index number of the tuple located at the first hierarchy level.

Permanent descriptors of child versions of tuples are assigned index numbers of write, change or delete transactions previous to read transaction of parent versions of tuples. Additional and modified descriptors of child versions of tuples are assigned current numbers of write, change or delete transactions .

Parent and child versions of tuples are logically interlinked by index numbers of tuples and initial addresses of modified descriptors.

Information is read from DB in the following way:

forming search key comprising descriptors with definite codes of domains and attributes and applied to relations with defined codes .

reading of descriptors of header, relations and domains block in accordance with the search key;

reading of descriptors of attributes blocks in accordance with search key, selection of descriptor with the least value of tuples quantity written to the linked data structure; reading of the last tuple written into linked data structure, reading and consolidation of parent and child versions of last tuple in accordance with tuple index number; comparison of codes values of descriptors of the consolidated tuple with codes values of search key descriptors, in case of coincidence thereof - replacement of descriptors codes with identifiers of domains and attributes, inclusion of consolidated tuple into search report;

selecting the descriptor within the consolidated tuple that corresponds to search key and has the least number of previous versions of tuples, repetition of these actions in order of approximation to the beginning of the linked data structure up to reading descriptor of consolidated tuple that corresponds to search key and having null value in the field of number of previous tuples.

To provide the consistency of data included into two or more relations the database search report comprises tuples with index numbers of descriptors do not exceed numbers of information write, change or delete transaction previous to read transaction.

Compression of data in the DB is based on inclusion of complete set of new versions of the block of header, relations, domain names and attributes, binding of data with new versions of blocks and subsequent removal of data associated with older versions of blocks into a linked data structure .

On the first step the DB is temporarily switched to

exclusive access mode and null value is written into pointer to the beginning of linked data structure of front-end

descriptor in older version of header block, that is an

indicator for DB switching over to data compression mode. The unchanged value of linked data structure size in front-end descriptor of old version of the header block acts as a

pointer to new version of header block. (Comment. In databases description, the term "null value" means "value unknown at the moment of writing to database". Arithmetic size of null value is equal to the biggest value from the range of numbers of the assigned capacity. For instance, when using 64-bit capacity, the null value is equal to eighteen nines in decimal

numeration) .

On the second step new versions of blocks of header, relations, domains and attributes is written, the size of linked data structure in initial and final descriptor of new version of header block is changed and a competitive access mode to database is restored.

At the third step consolidation of tuples and binary fragments linked to old versions of blocks of header, relations, domains and attributes is made. The selection of tuples for inclusion into data compression is made in ascending order of values of descriptors identifiers in old versions of blocks of relations, domains and attributes. Selection of domains blocks is limited by blocks of tuples index numbers .

At fourth step consolidated tuples and binary fragments are written (in background mode) along with linking of consolidated tuples to new versions of blocks of header, relations, domains and attributes.

Simultaneously, the execution of the following transactions is supported in priority mode:

reading tuples and binary fragments, that have not been consolidated, via old versions of block;

writing new incoming tuples and binary fragments along with linking them to new versions of blocks;

changing, deletion and reading of consolidated and new incoming tuples and binary fragments with use of new versions of block;

changing values of descriptors of new versions of attributes blocks. Compression is finished by changing the linked data structure size in the front-end descriptor of new version of header block and deleting the data located in linked data structure placed just before the new version of header block.

New versions of blocks, consolidated tuples and new incoming tuples written before the deleting data from file, comprise descriptors with values belonging to address space of linked data structure formed before deleting data from file. Thus, the assigning - of values to descriptors of blocks and tuples after deleting data from file is made with consideration to offset value of new header version in relation to the beginning of linked data structure before deleting data from file. The offset value is reflected in the pointer to the beginning of linked data structure of the front-end descriptor of new version of header block;

Restoration of completeness and consistency of information after abnormal DB access termination is based on procedure for defining the calculated the of linked data structure and adjusting values of attributes blocks descriptors with actual values of tuples descriptors recorded with positive offset from calculated value of linked data structure size.

Use of calculated size value of the linked data structure is dictated by the necessity to restore completeness and consistency of data, recorded in the size field of linked data structure descriptor of front-end descriptor of header block before abnormal termination of DB access.

Restoring is started with reading descriptors of blocks of header, relations, domains and attributes. Service domains of tuples index numbers are used in this case for reading process only .

Basing on values of pointers to beginning of last tuples and on size thereof contained in descriptors of attributes blocks, the tuple recorded with the biggest offset from the beginning of linked data structure and related binary fragment is read. The estimated size of the linked data structure is determined by summing the values of the index at the beginning of the last tuple and the size thereof, contained in the descriptor of attributes block, and pointer to the beginning of the binary fragment and the size thereof, contained in the descriptor of the last tuple.

Then tuples recorded with a positive offset from the calculated value of the linked data structure are read.

Tuples that were written within last transaction with positive offset from the calculated value of a linked data structure, and binary fragments associated therewith are removed from linked data structure.

Values of descriptors of attributes blocks are synchronized with the starting address, size value and number of tuples written with positive offset to calculated value of linked data structure size.

Restoration of data completeness and consistency is finalized by changing size value of a linked data structure in front-end descriptor.

In case of dividing database into several linked data structures, restoring of data completeness and consistency is made in each linked data structure separately. At the same time, deleting tuples constituent the last transaction with positive offset to calculated size value of one of linked data structures is made in all linked data structures simultaneously .

REALIZATION EXAMPLE

Example of implementation of this invention is a telephone network database. Conventionally in brackets metadata codes are shown.

DB contains relations of subscribers (1) and operators (2), and the following domains:

domain of tuples index numbers (0);

domain of subscribers' last names (5) ; domain of subscribers' first names (6);

domain of cities (7);

domain of streets (8);

domain of houses (8);

domain of PSTN operators names (10);

domain of PSTN operators phone codes (11);

domain of subscribers' phone numbers (12).

Scheme of subscribers' relations includes domains located on the following hierarchy levels:

1 level - domain of tuples index numbers

2 level - domain of subscribers' last names

3 level - domain of subscribers' first names

2 level - domain of cities

3 level - domain of streets

4 level - domain of houses

2 level - domain of PSTN operators phone codes

3 level - domain of subscribers' phone numbers

Scheme of operators' relations comprises domains located on the following hierarchy levels:

1 level - domain of tuples index numbers

2 level - domain of PSTN operators' names;

3 level - domain of PSTN operators phone codes

Attribute set of tuples is shown in an example record. Paragraphs starting with 1.1 correspond to the beginning of tuples, lines of paragraphs correspond to tuples descriptors. Lines represent identifiers and domains and attributes codes. Symbol "/" separates identifiers and codes. Symbol "." separates domains codes and attributes codes, as well as domains identifiers and attributes identifiers.

Subscribers' relation 1;

0.1 / Tuple index number. 1

5.1 / Last name. Kuznetsov

6.1 / First name. Alexander 7.1 / City. Moscow

8.1 / Street. Tsvetochnaya

9.1 / House number. -128

11.1 / Operator telephone code. 324

12.1 / Subscriber number. 208473

11.2 / Operator telephone code. 698

12.2 / Subscriber number. 593451

Operators' relation 2;

0.1 / Tuple index number. 1

10.1 / Operator name. Alpha Telecom

11.1 / Operator telephone code. 324

0.2 / Tuple index number. 2

10.2 / Operator name. Omega Telecom

11.2 / Operator telephone code. 698

The example shows search process for names of PSTN operators that provide service to telephone numbers that belong to a subscriber with an askable last name. Search is performed without use of second copies of metadata blocks with temporal descriptors values.

The search is performed in accordance with the following search key:

Relation 1, domain 5, attribute 1

Information included into final report:

Relation 2, domain 10, attribute "*"

At the first step, root descriptor of header block is read, located in the beginning of the file. Basing on pointer to the beginning of relations block and code of relation the location of relation descriptor in file, with code value equal to 1 is defined .

At the second step, the relation descriptor is read. Basing on the pointer to the beginning of domains block and code of domain the location of domain descriptor in file, with code value equal to 5 is defined. At the third step, the domain descriptor is read. Basing on the pointer to the beginning of attribute block and code of attribute the location of attribute descriptor in file, with code value equal to 1 is defined.

At the fourth step, the attribute descriptor is read and the value is defined for the pointer to the beginning of last tuple, size thereof and the number of tuples written into the attribute descriptor.

At the fifth step, basing on the pointer to the beginning of the last tuple and size thereof, the last tuple is read. In accordance with the tuple number, a search is performed for parent and child versions of the tuple. The consolidated tuple is included into interim search report. In the tuple descriptor, where the value of codes for domain and attribute is equal to 5 and 1, the value of pointer to the beginning of previous tuple, size of previous tuple and number of previous tuples, are defined.

At the sixth and consequent steps, basing on pointers to the beginning and size of previous tuple, previous tuples are read, repeating actions from step 5 up to reaching the tuple where the pointer to the beginning of the previous tuple has null value.

External key logically linking relations 1 and 2 comprises attributes included into domain 11. Interim search report comprises one tuple in which one or several attributes codes, contained in descriptors with domain code 11, are defined. There are two such values in the example - .324 and 698. Along with required value of descriptor domain code equal to 10 they form additional search key.

At the seventh step the root descriptor in header block is read again. Basing on the pointer to the beginning of relations block and on the code of relation, the location of relation descriptor in file, with code value equal to 2 is defined . At the eighth step, the relation descriptor is read. Basing on the pointer to the beginning of domains block and on the code of domain, the location in the domain descriptor file with code value equal to 10, is defined.

At the ninth step, the domain descriptor is read. Basing on the pointer to the beginning of attribute block and on the code of attribute, the location of attribute descriptor in file with code value equal to 324, is defined.

At the tenth step, attribute descriptor is read and value for the pointer to the beginning of the last tuple, size thereof and the number of tuples are defined.

At eleventh step, basing on pointer to the beginning of the last tuple and size thereof, the last tuple is read. In accordance with the tuple number, a search is performed for parent and child versions of the tuple. Consolidated tuple is included into search report. In the tuple descriptor, where values of codes for domain and attribute are equal to -10 and 324 correspondingly, the value of the pointer to the beginning of previous tuple, size of the previous tuple and the number of previous tuples are defined.

At twelfth and consequent steps, basing on the pointers to the beginning of the previous tuple and on the size thereof, previous tuples are read, repeating from step 11 up to reaching the tuple where the pointer to the beginning of the previous tuple and the size of the previous tuple has null values .

The same set of actions within the relation 2 is made with the use of additional search key descriptor, with value of domain and attribute codes equal to 10 and 698, correspondingly.

As a result, the interim search report comprises tuples 1 and 2, included into the relation 2. Searched descriptors are selected within the tuple, descriptors codes are replaced with domains and attributes identifiers with the use of metadata tables, and thus the final search report is formed:

Relation Last Name Name

Subscriber Kuznetsov

Operator Alpha Telecom

Omega Telecom

INDUSTRIAL APPLICABILITY.

The disclosed inventions are industrially applicable, because they comprise industrially-produced hardware and use industrially manufactured software tools known in the art. Declared technical solutions may be repeated in industry by using description and claims presented.

CITED DOCUMENTS.

1. Astrahan M.M. et al. System R: A Relational Data Base Management System. IEEE Computer, volume 12, issue 5 May 1979. ISSN 0018-9162;

2. Blasgen M.W. et al. System R: An architectural overview. IBM Systems Journal, volume 20, issue 1 March 1981. ISSN 0018- 8670;

3. Chamberlin D.D. et al. A History and Evaluation of System R. Communications of ACM, volume 24, issue 10 October 1981. ISSN 0001-0782.

Claims

1. Relational database, comprising

- metadata, said metadata further comprising a) attributes, compliant with the characteristics of the subject area; b) domains combining attributes of one type; and c) relations defined on said domain, data represented by tuples of said attributes and included into said relations,

- search tree, comprising entry point, root, nodes and leaves, and

- binary fragments comprising unstructured data, said relational database is made in the form of a linked data structure, components of said structure are

- header block located in the entry point,

- relations block located in the root,

- domains blocks located in nodes,

- attributes blocks located in leaves,

tuples consisting of a hierarchical multi-sets of attributes of variable composition, and

- binary fragments comprising identifiers, identifiers data types and codes of said database, said relations, said domain names and said attributes.

2. Relational database as recited in claim 1, wherein header block comprises:

front-end descriptor comprising pointer to the starting address of linked data structure and the size thereof;

- root descriptor comprising pointer to the starting .address of said relations block and the size thereof.

3. Relational database as recited in claim 2, wherein said relations block further comprises descriptors, each of said descriptors corresponds to one of said relations and comprises a pointer to the starting address of said domain block and the size of said domain block, and said descriptors are ordered in codes ascending order, value of said each code is equal to the index number of said corresponding relation within said database .

4. Relational database as recited in claim 3, wherein said domains blocks further comprise descriptors, each of said descriptors corresponds to one of the domain and comprises a pointer to the starting address of said attribute block and the size of said attribute block, and descriptors are ordered in codes ascending order, value of said each said code is equal to the index number of said corresponding domain within said database .

5. Relational database as recited in claim 4, wherein said attributes blocks further comprises descriptors, each of said descriptors corresponds to one of the domain attribute and comprises a pointer to the starting address of the last said tuple and the size of said last tuple and number of all tuples comprising descriptors with coinciding codes of said attributes, said descriptors are ordered in codes ascending order, value of said each code is equal to the index number of said corresponding attribute within said domain.

6. Relational database as recited in claim 5, wherein said tuples further comprise descriptors, each of said descriptors corresponds to one of said attributes of said tuple and comprises descriptor primary address in linked data structure, index number of write transaction, data change or deletion, domain code, attribute code, descriptor level of hierarchy in said tuple, a pointer to the starting address of the previous tuple, size of said previous tuple and the number of said previous tuples comprising descriptors with matching codes of domains and attributes; said descriptors are ordered in hierarchy levels ascending order and are grouped in subsets o-f repeating descriptors with coinciding codes of domains;

said descriptors with null values of said attributes codes located on upper levels of hierarchy define positions of descriptors with defined values of codes of attributes located on lower levels of said tuples hierarchy;

said value of descriptor attribute code located in the first hierarchy level is equal to index number of said tuple within said relation.

7. Relational database as recited in claim 6, wherein said tuples are linked to said binary fragments via assigned descriptors of tuples, said assigned descriptors of tuples hierarchy levels, domains codes and attributes codes comprising null values, binary fragments' addresses and binary fragments' sizes correspondingly.

8. Relational database as recited in claim 7, further comprising a plurality of linked data structures, each said data structure comprising header, relations, domains and attributes blocks, group of tuples included into all said relations and grouped in accordance with values of digits in lower positions of tuples index numbers, and binary fragments linked to said tuples, the value of said database code within said binary fragment comprises low-order digits of said tuple index number, placed in digits ascending order.

9. Relational database control method for relational database control as recited in claim 8, providing versioned execution of write, change, delete transactions, and data compression in the competitive access mode to database, recovery of completeness and consistency of data after abnormal database termination,

wherein said transactions are performed in versioned direct access mode with the single copy of said database.

10. Relational database control method as recited in claim 9 wherein the data is written using the following steps:

writing of header, relations, domains and attributes blocks; replacement of identifiers of said domains and said attributes with codes of descriptors in said tuples;

writing of said tuples and said binary fragments;

changing values of said descriptors in said attributes blocks; changing size value of said linked data structure of front-end descriptor in said header block.

11. Relational database control method as recited in claim 10 wherein data is changed or deleted using the following steps: writing the new versions of said relations, said domains and said attributes blocks;

writing the derived versions of said tuples comprising new, changed or deleted descriptors of parent versions of said tuples and new versions of said binary fragments;

changing values of said descriptors in said attributes blocks; changing size value of linked data structure of front-end descriptor in said header block.

12. Relational database control method as recited in claim 11 wherein the data is read using the following steps:

searching for said parent and derived versions of tuples and consolidation thereof;

searching for binary fragments linked to said consolidated tuples ;

replacement of descriptors codes with domains' identifiers and attributes in said consolidated tuples.

13. Relational database control method as recited in claim 12 wherein data is compressed using the following steps:

switching to database exclusive access mode;

writing null value into said pointer to the starting address of said linked data structure of front-end^' descriptor in the old version of said header block;

writing new versions of header, relations, domains and attributes blocks;

switching to database competitive access mode; searching for said tuples and said binary fragments linked to old versions of said blocks of header, relations, domains and attributes and consolidation thereof;

writing said consolidated tuples and said binary fragments along with conjunction them to said new versions of blocks of header, relations, domains and attributes;

reading said tuples and binary fragments that have not been consolidated, said reading is performed with the use of old versions of said blocks of header, relations, domains and attributes ;

writing new incoming tuples and binary fragments along with conjunction them to new versions of said blocks of header, relations, domains and attributes;

changing, deletion and reading of said consolidated and new incoming tuples and said binary fragments with use of new versions of said blocks of header, relations, domains and attributes;

changing values of said descriptors in the new versions of said attributes blocks;

changing the size value of said linked data structure of front-end descriptor in the new version of said header block; deleting data comprising linked data structure; said data to be deleted is located in the file just before the new version of header block data.

14. Relational database control method as recited in claim 13 wherein the completeness and consistency of data after abnormal termination is restored using the following steps:

reading descriptors of block of header, block of relations, block of domains, tuples index numbers and attributes blocks linked to said tuples.

reading said tuple located with the biggest offset in relation to the starting address of the linked data structure according to the value of attributes block descriptor, with code of said attribute block coinciding with said tuple index number and binary fragment linked thereto; estimation of linked data structure size;

reading said tuples written with positive offset in relation to estimated value of said linked data structure size;

deleting said tuples written during the latest transaction with positive offset to estimated value of said linked data structure size and binary fragments linked thereto;

synchronizing of values of said descriptors of attributes blocks with starting address, size and number of tuples written with positive offset in relation to said estimated value of said linked data structure size;

changing the size value of said linked data structure of front-end descriptor of said header block.