WO2024157776A1 - データ処理装置、データ処理方法、及びプログラム - Google Patents

データ処理装置、データ処理方法、及びプログラム Download PDF

Info

Publication number
WO2024157776A1
WO2024157776A1 PCT/JP2024/000399 JP2024000399W WO2024157776A1 WO 2024157776 A1 WO2024157776 A1 WO 2024157776A1 JP 2024000399 W JP2024000399 W JP 2024000399W WO 2024157776 A1 WO2024157776 A1 WO 2024157776A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
virtual
mapping
column
data structure
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2024/000399
Other languages
English (en)
French (fr)
Inventor
晋二 古庄
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Individual
Original Assignee
Individual
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Individual filed Critical Individual
Priority to JP2024572949A priority Critical patent/JPWO2024157776A1/ja
Priority to CN202480009105.5A priority patent/CN120584343A/zh
Priority to KR1020257027169A priority patent/KR20250133955A/ko
Priority to EP24747107.1A priority patent/EP4657274A4/en
Publication of WO2024157776A1 publication Critical patent/WO2024157776A1/ja
Priority to US19/280,646 priority patent/US20250355848A1/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/21—Design, administration or maintenance of databases
    • G06F16/211—Schema design and management
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/221—Column-oriented storage; Management thereof
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2272—Management thereof
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2282—Tablespace storage structures; Management thereof
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2455—Query execution
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/248—Presentation of query results
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/25—Integrating or interfacing systems involving database management systems
    • G06F16/258—Data format conversion from or to a database
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models

Definitions

  • This disclosure relates to a data processing device, a data processing method, and a program.
  • This disclosure has been made in consideration of the above points, and provides technology that allows indexes that enable sorting, searching, and aggregation of real table-format data to be inherited by virtual table-format data.
  • a data processing device has a data manipulation unit that performs a sort operation, a search operation, or an aggregation operation on virtual tabular data composed of virtual columns having a second data structure obtained by converting a first data structure of one or more columns included in one or more tabular data by a predetermined mapping, using the second data structure as an index.
  • FIG. 1 is a diagram for explaining an example of virtual table-format data hierarchically constructed starting from D5A that holds values.
  • FIG. FIG. 13 is a diagram for explaining an example (part 1) of mapping A.
  • FIG. 13 is a diagram for explaining an example (part 2) of mapping A.
  • FIG. 13 is a diagram for explaining an example of allocation.
  • FIG. 13 is a diagram for explaining an example of an allocation method using enumeration mapping.
  • FIG. 13 is a diagram for explaining an example of an allocation method using linear function mapping.
  • FIG. 2 illustrates an example of a source column and a virtual column.
  • FIG. 2 is a diagram showing an example of a source column, a transposed structure, and a virtual transposed structure;
  • FIG. 13 is a diagram for explaining an example of layout mapping of two-level virtual table-format data.
  • FIG. 13 is a diagram illustrating an example of a virtual transposed structure of two-level virtual tabular data.
  • 1 is a diagram illustrating an example of the overall configuration of a system including a data processing device according to an embodiment of the present invention.
  • FIG. 1 is a diagram illustrating an example of a hardware configuration of a data processing device according to an embodiment of the present invention.
  • 13 is a flowchart showing an example of the flow of a process for creating virtual tabular data.
  • 13 is a flowchart showing an example of the flow of a sort process on virtual table-format data.
  • 13 is a flowchart showing an example of the flow of a search process in virtual table-format data.
  • 13 is a flowchart showing an example of the flow of a counting process for virtual table-format data.
  • D5A data called tabular data
  • D5A data called tabular data
  • a method for creating new virtual tabular data from D5A or other virtual tabular data and a method for inheriting indexes of (real) tabular data to sort, search, and aggregate the virtual tabular data will be described. It will also be described how indexes can be inherited even when the virtual tabular data is constructed hierarchically.
  • a data processing device 10 that can create such virtual tabular data and sort, search, and aggregate it will be described.
  • Archive data such as IoT (Internet of Things) data, various observation data, and log data is being accumulated daily.
  • IoT Internet of Things
  • tabular data is compiled into one at regular intervals, such as daily or monthly, and added to the archive.
  • Tabular data added to the archive can be considered read-only.
  • Tabular data in such archives can be huge, and is often distributed over LANs (Local Area Networks) and the Internet.
  • the first step is to generate new tabular data.
  • New tabular data is created by UNIONing or JOINing multiple pieces of tabular data, or by extracting only the necessary columns. This can take a long time if the original tabular data is huge or distributed over a wide area network such as the Internet. Also, if the new tabular data is large, a large memory area is required to store it.
  • the second step involves sorting, searching, and aggregating.
  • the newly created tabular data is not indexed, so sorting, searching, and aggregating takes time.
  • the sorting results when the new tabular data is large, the search results when the number of hits is large, and the aggregation results when they are large all require a large amount of storage space.
  • the tabular data to be operated on may be, for example, one trillion records or 100,000 columns. Furthermore, combinations such as UNIONS and JOINS of the tabular data to be operated on may be stacked hierarchically. Furthermore, the tabular data to be operated on may be distributed on a LAN, or may be distributed on multiple HTTP (Hypertext Transfer Protocol) servers on the Internet.
  • HTTP Hypertext Transfer Protocol
  • a network system for mapping archive data can be constructed using D5A, a file format for tabular data with indexes on all columns that speed up sorting, searching, and aggregation; virtual tabular data that inherits values directly or indirectly from the D5A file; and virtual indexes on the virtual tabular data that use a data structure that is automatically established by directly or indirectly inheriting the data structure used by the D5A file index.
  • the virtual tabular data and virtual indexes are immediately available for use simply by connecting them directly or indirectly to D5A, and they consume only a small amount of storage space.
  • sorting results, search results, and aggregation results obtained using virtual indexes require only a small amount of storage space, no matter how large they are.
  • This kind of network of mapping of archive data using D5A makes it possible for users to create virtual tabular data for each purpose and use the archive data distributed on the network interactively in a new way of using archive data. For example, it makes it possible for each organization to use archive data distributed to each department within the organization for various purposes, and on the Internet it makes it possible to combine and extract archive data such as IoT data from all over the world and use it in a variety of linked ways.
  • D5A is a file format for table format data in which all columns have indexes that speed up sorting, searching, and aggregation.
  • virtual table format data is table format data that inherits values from a D5A file (a file in D5A format) or other virtual table format data.
  • the table format data from which it is inherited is called source table format data.
  • a column on D5A is called a D5A column, and an index that speeds up sorting, searching, and aggregation of a D5A column is called a D5A index.
  • virtual table format data is called a virtual column and virtual index.
  • source table format data is called a source column and source index.
  • the data structure used by a D5A index is called a transposed structure
  • the data structure used by a virtual index is called a virtual transposed structure
  • the data structure used by a source index is called a source transposed structure.
  • virtual table format data may be called “mapped table format data” or the like, and similarly, virtual columns may be called “mapped columns” or the like.
  • the first step is a step of generating new tabular data by performing UNION or JOIN or extracting only the necessary columns
  • the second step is a step of sorting, searching, and aggregating.
  • the reason why the first step takes time is because it takes time to read, compare, and store the values. Therefore, instead, an approach can be considered in which there is tabular data that will be the source tabular data, and a mapping defined by a correspondence table and rules that defines which cells in the source tabular data are mapped to which cells in the newly created tabular data is used to create new tabular data using that mapping.
  • a mapping defined by a correspondence table and rules that defines which cells in the source tabular data are mapped to which cells in the newly created tabular data is used to create new tabular data using that mapping.
  • the new tabular data does not need to have values, which is an advantage especially when the new tabular data is huge.
  • the new tabular data can be displayed in just the short time it takes to load the mapping definition, and only a small amount of memory is required to hold the mapping definition. This new tabular data does not hold values, but inherits values from the original tabular data, so it is virtual tabular data.
  • the problem in the first step can be solved with such virtual tab
  • the second step takes time because there are no indexes on the columns of the newly created tabular data, and because it takes time to write out the sort results, search results, and aggregation results, which are often huge.
  • the time-consuming problem is solved by the fact that every column of the virtual tabular data above automatically has a virtual index that speeds up the sorting, searching, and aggregation of that column, and because this virtual index can hold even huge sort results, search results, and aggregation results with only a small amount of memory space, thereby reducing the write time.
  • the virtual index only uses a small amount of memory space to store these results, the storage space problem is also solved. In this way, the problem in the second step can be solved by virtual indexes.
  • the D5A file which is expressed in a storage format for tabular data called D5A, holds the values that form the basis of this virtual tabular data and the data structure that forms the basis of the data structure used by the virtual index.
  • ⁇ D5A Storage format of tabular data that serves as a source of values and indexes>
  • Virtual tabular data inherits values from one or more source tabular data.
  • the source tabular data is either another virtual tabular data or tabular data called a D5A file.
  • the virtual tabular data inherits values from yet another source tabular data, and finally arrives at a D5A file. Therefore, it can be said that the virtual tabular data is hierarchically structured, directly or indirectly inheriting values from the D5A file.
  • the virtual index uses a virtual transposed structure to speed up sorting, searching, and aggregation.
  • the virtual transposed structure is established automatically by inheriting one or more source transposed structures.
  • a source transposed structure is either a virtual transposed structure on another virtual tabular data, or a transposed structure on a D5A file.
  • the virtual transposed structure inherits yet another source transposed structure, and finally arrives at a transposed structure on a D5A file. Therefore, it can be said that the virtual transposed structure is established hierarchically by directly or indirectly inheriting the transposed structure on a D5A file.
  • D5A is a storage format for tabular data that provides values to virtual tabular data and provides transpose structures to virtual transpose structures, with a D5A index that holds values and uses transpose structures for all its columns.
  • FIG. 1 shows a process for combining meteorological observation data from Sunday to Saturday for each region of Tokyo, Osaka, and Nagoya. This process is performed in two stages, first combining seven daily data for each region into weekly data, and then juxtaposing the weekly data into one table format data.
  • 21 daily data for one week for three regions on the left side of FIG. 1 are stored in a 55A file.
  • the three table format data for each region in the center of FIG. 1 are virtual table format data.
  • Each of these virtual table format data uses the seven D5A files for one week on the left side of FIG. 1 as source table format data, extracts necessary columns from them, and then performs a UNION.
  • One virtual table format data on the right side of FIG. 1 juxtaposes the three virtual table format data for each region in the center of FIG. 1 as source table format data.
  • the mapping network for archive data starts with the D5A file, with virtual tabular data built hierarchically on top of it.
  • virtual tabular data is automatically equipped with virtual indexes, allowing any column to be sorted, searched, and aggregated in a short time, and only a small amount of memory is required to store the sort results, search results, and aggregation results.
  • This type of virtual tabular data can be created and used by users themselves, and it is expected to promote widespread use of archive data.
  • mapping> D5A virtual tabular data, and virtual indexes are all described as a combination of mappings from a continuous interval of natural numbers starting from 0 to some value (also often a natural number).
  • This mapping can be expressed as a one-dimensional array (Array) with subscripts (indexes) starting from 0, so it is called A-mapping.
  • Array one-dimensional array
  • indexes indexes
  • A-maps can be created by combining A-maps in various ways.
  • A-map S which represents the result string of a search
  • A-map C- A which represents column A
  • A-map C- B which represents column B
  • A-map representing the search results of column B can be obtained.
  • S can be any A-map that represents a result string
  • C -A and C- B can be any A-map that represents columns. They can exist on a local storage device or on a network.
  • Such a combination of A-maps can be said to be an algebraic combination.
  • a virtual A mapping is an A mapping that uses one or more A mappings as the combining source, has a known overall size, and allows for the extraction of any i-th part from the combining source. Since a virtual A mapping is also an A mapping, it is possible to combine virtual A mappings to create further virtual A mappings hierarchically.
  • a column of virtual tabular data is a type of virtual A mapping, and can be created hierarchically.
  • An index is a mechanism that is realized by a data structure for indexing and an algorithm that uses that data structure.
  • a virtual index is an index that uses one or more virtual A mappings as the data structure for indexing, and can be created hierarchically.
  • the second advantage of the A-map is that it can be decomposed to create a new A-map.
  • decomposing the A-map it is possible to create and use a new A-map with functions that were not present in the A-map before decomposition.
  • One particularly effective decomposition is the LP decomposition (decomposition into A-map L and A-map P) of the A-map M that defines the correspondence (mapping) between cells in tabular data.
  • Decomposing M into L and P makes it possible to search for elements efficiently using a bisection search in L, and to find the inverse mapping in P.
  • M can be any A-map that defines the mapping, and L automatically becomes an A-map that allows for a bisection search, and P automatically becomes an A-map with an inverse. Since the decomposition of the A-map produces a new A-map, it can be said to be an algebraic decomposition.
  • D5A a storage format for tabular data in which every column has an index that allows for high-speed sorting, searching, and aggregation.
  • D5A and the A mapping it is possible to define virtual tabular data.
  • This virtual tabular data is automatically provided with a virtual index that uses one or more A mappings as the data structure for the index. This makes it possible to realize a network system of archive data mappings that allows archive data distributed across the network to be used in various combinations.
  • mapping can be expressed as a one-dimensional array, but when discussing its mapping aspect it is called a mapping, and when discussing its operations it is called an array. Accordingly, when treated as a mapping it will be called a domain and value range, and when it is an array containing columns or tabular data it will be called a record number and value. However, the notation for the A mapping will be as much as possible as an array.
  • Notation 2 When specifying the domain n of A mapping A, write it as A (n) . According to this notation, a column is written as, for example, C (R) where R is the total number of records.
  • a (n) [i] The i-th element of the A-map A (n) is written as A (n) [i]. Therefore, A (n) ⁇ (A (n) [0], A (n) [1], ..., A (n) [n-1]).
  • index operator that combines A-maps>
  • a (n) ⁇ B (m) (n) (A (n) [B (m) (n) [0]], ..., A (n) [B (m) (n) [m- 1]])
  • Formula (1) The above index operator has the following properties 1 to 3.
  • Property 2 The size of the array that represents the combination result is the size of the array on the right.
  • Property 3 The data type of the array representing the join result is the data type of the left array.
  • the number of types of values that can appear in the A mapping obtained as a result of combining A mappings with the index operator is equal to or less than the size of the smallest A mapping among the A mappings combined with the index operator. This is an index similar to the rank in a matrix.
  • unique decomposition methods are of special value, as they make it possible to speed up sorting and searching, and to find inverse mappings.
  • unique decomposition methods SN decomposition, LP decomposition, and spectral decomposition.
  • SN decomposition This is a method of decomposing one A mapping into two, and there is only one way in which the left A mapping of the two resulting A mappings holds only the values that appear in the left A mapping, and holds these values uniquely and in ascending order. This decomposition is called SN decomposition.
  • the first item on the right-hand side which is unique and ascending, is called the SVL (Sorted Value List).
  • SVL (Alice, Bob, Cathy).
  • C (R) SVL (K) ⁇ NNC (R) (K) ; i, j ⁇ 0,...,K-1 and i ⁇ j ⁇ SVL (K) [i] ⁇ SVL (K) [j] Equation (2)
  • the upper part indicates that column C (R) is decomposed into SVL (K) and NNC (R) (K)
  • the lower part indicates that the elements of SVL (K) are arranged in ascending order.
  • NNC (R) (K) is an A-map of size R whose elements are natural numbers 0, ..., K-1, as can be seen from the notation.
  • Step 1-1 Add the position in the A mapping to each value of (Bob, Alice, Cathy, Bob) to create ((Bob, 0), (Alice, 1), (Cathy, 2), (Bob, 3)).
  • Step 1-2 Sort the values and positions while evaluating their relative magnitude to obtain ((Alice, 1), (Bob, 0), (Bob, 3), (Cathy, 2)).
  • LP decomposition When LP decomposition is performed, it is possible to use L to determine the presence or absence of elements in M and their order, and to use P to find the inverse. Note that LP decomposition can be performed using the same algorithm as SN decomposition.
  • Spectral decomposition The above notation 7 expresses the position (index) on the A map where each value appears as a new A map. This is called the spectral decomposition of the A map. Spectral decomposition makes it possible to view the A map from the range to the domain, enabling various algorithms. Below is an example showing how spectral decomposition of a column, which is an A map, makes it easy to sort, search, and aggregate the column.
  • the sorting is performed by removing values from the spectral decomposition of the column Alice: (1) + Bob: (0, 3) + Cathy: (2) to obtain (1) + (0, 3) + (2), and performing the concatenation defined in Notation 5 to obtain the sorted result string (1, 0, 3, 2).
  • Search result C (R)
  • R is the total number of records
  • ⁇ is a key value
  • w is the number of transposed record numbers belonging to the key value ⁇
  • X is an array of transposed record numbers.
  • Step 2-1 Add the position in the A mapping to each value of (Bob, Alice, Cathy, Bob) to create ((Bob, 0), (Alice, 1), (Cathy, 2), (Bob, 3)).
  • Step 2-2 Sort the values and positions while evaluating their relative magnitude to obtain ((Alice, 1), (Bob, 0), (Bob, 3), (Cathy, 2)).
  • Step 2-3 Grouping the positions in the A map with the same values completes the spectral decomposition Alice: (1) + Bob: (0, 3) + Cathy: (2).
  • A-maps can be classified according to four criteria: associativity, searchability, whether they represent a set, and whether their inverse can be easily found. Keeping these classifications in mind will help you understand the following explanations, so we will explain them here.
  • A-maps with natural numbers as elements can be placed on both sides of an index operator.
  • A-maps without natural numbers can only be placed on the left side of an index operator.
  • An A-map whose elements are arranged in ascending order can be used to efficiently search for whether a particular element exists and, if so, where it is located, using a bisection search. Such an A-map is called an ascending array.
  • An A-map whose elements are unique and ascending order can be searched for a certain value, and if a match exists, it will be the only one. Such an A-map is called a unique ascending array.
  • Symmetric arrays form a group with respect to the index operator. Therefore, there exists an identity and an inverse.
  • the inverse of P is used to identify cells in the source tabular data from cells in the virtual tabular data.
  • an index is established when the size W of the sort/search/aggregation results of the target column is known, and when i ⁇ 0, 1, ..., W-1 is specified, the i-th row of the sort/search/aggregation results can be read in approximately O(log(R)) or less time.
  • CSV Common Separated Values
  • D5A is a collection of D5A columns, which are columns of D5A with the same structure. Each D5A column is a juxtaposition of the two structures described below.
  • the first structure is for obtaining column values, and is the part enclosed by the dashed line in Figure 4.
  • This structure can be configured to either (a) store the column, which is the A mapping, as is, (b) store the SVL and NNC obtained by SN decomposition of the column, or (c) store both.
  • (a) storing as is the performance of reading values improves, but algorithms using NNC cannot be used.
  • (b) storing SVL and NNC algorithms using NNC can be used, but the performance of reading values decreases.
  • the size of the D5A file increases. In this embodiment, the case of (b) will be explained.
  • the second structure is for the D5A index, and is the part enclosed by the dashed line in Figure 4.
  • This structure consists of SVL, ACM, and INV, and is called the transposed structure.
  • the transposed structure is the spectral decomposition of the D5A column described above rewritten in the form of an A mapping. The details of the transposed structure will be described later.
  • a transposed structure i.e., the second structure
  • it will be combined with the first structure above to form a D5A column, and collecting the D5A columns will result in D5A.
  • the structure for obtaining the column values can be created by SN decomposition of column C (R) .
  • the following information 1 to 4 can also be obtained from the SVL.
  • the number of different values in a column, K can be determined from SVL (K) . For example, in the example shown in FIG.
  • a bisection search of SVL can tell you whether a value v exists in a column. Also, if the value v exists, you can tell what number value v is.
  • SVL is the aggregation dimension. Note that previously, sorting was required to create an aggregation dimension.
  • transposed structure is a structure for the D5A index.
  • spectral decomposition of a column allows for high-speed sorting, searching, and aggregation, but there are two difficult points to handle with spectral decomposition. The first is that it is not made of A mapping, so it cannot be accessed using an index operator (first problem).
  • first problem when trying to obtain the i-th item in the sorted result column, it is necessary to search for the i-th item while adding w 0 , w 1 , ... (second problem).
  • the transposed structure is the result of converting the spectral decomposition into three A mappings, which solves these two points. Below, we will explain its definition and how to create it.
  • transposition structure Definition of transposition structure and method of creating it from spectral decomposition
  • the definition of the transposition structure is shown below.
  • SVL (K) is the A-map obtained by simply arranging the value parts of the spectral decomposition in equation (3), ⁇ 0 , ⁇ 1 , ..., ⁇ K -1 . It is also the same as SVL (K) obtained by equation (4).
  • Step 3-2 ACM (K) (R+1) is
  • INV is a record number corresponding to ⁇ 0 ⁇ 1 ⁇ . . . ⁇ K ⁇ 1
  • INV is an array of transposed record numbers.
  • the transposed structure is ⁇ (Alice, Bob, Cathy): (1, 3, 4), (1, 0, 3, 2)>.
  • Spectral decomposition is not an A-map, and requires an addition operation of w i to obtain the i-th element of the sorted result sequence.
  • the transposed structure derived from spectral decomposition is a structure consisting of three A-maps, which can solve the first problem, and since the i-th element of the sorted result sequence can be obtained with INV[i], the second problem can also be solved.
  • the spectral decomposition can be obtained from the transposed structure in D5A in the following manner.
  • ⁇ i SVL (K) [i]. Also, if we predetermine that ACM[ ⁇ 1] ⁇ 0, then
  • the i-th term of the spectral decomposition can be obtained as follows.
  • the first term of the spectral decomposition is given by:
  • the following information 5 to information 8 can also be obtained.
  • the i-th record number in the sorted result can be read as follows:
  • i-th record number of sorted result INV[i] Formula (9)
  • the record numbers with the ith smallest value can be read out as the following array.
  • Equation (10) Let i0 be the smallest i0 that satisfies v0 ⁇ SVL[ i0 ], and let i1 be the largest i1 that satisfies SVL[ i1 ] ⁇ i1 , (INV (R) (R) [ACM (K) [ i0-1 ]], ...,INV (R) (R) [ACM (K) [ i1 ]-1]) Equation (10) For example, in the example shown in FIG.
  • An index can be created with a transposed structure
  • the requirement for an index to be valid is that the size W of the sorted, searched, and tabulated results is known, and when i ⁇ 0, 1, ..., W-1 is specified, the i-th row of the sorted, searched, and tabulated results can be read in approximately O(log(R)) or less.
  • search The case of formula (10) will now be described.
  • the size of the search result is found to be ACM (K) [ i1 ]-ACM (K )[ i0-1 ].
  • the i-th element of the search result can be read in O(1) using (INV (R) (R) [ACM (K) [ i0-1 ]], ...,INV (R) (R) [ACM (K) [ i1 ]-1])[i].
  • ICV (R) (R) [ACM (K) [ i0-1 ]] ...,INV (R) (R) [ACM (K) [ i1 ]-1]
  • i] (0, 3, 2)[i].
  • the inverted structure meets the requirements for creating an index for searching.
  • the size of the aggregation result is known to be K from information 1 above.
  • the i-th value of the aggregation result is given by information 2 above, and can be obtained in O(1).
  • the number of occurrences of the i-th value of the aggregation result is given by equation (8), and can be obtained in O(1). Therefore, the transposed structure meets the requirements for creating an index on aggregation.
  • the above makes it possible to create a D5A index that uses a transposed structure to speed up sorting, searching, and aggregation.
  • sort results The results of sorting, searching, and aggregation using the D5A index require only a small amount of storage space (sort results).
  • the sorted results are already stored in INV, and no new storage area is required.
  • search results The case of formula (10) will be described.
  • the search results are given as an array (INV (R) (R) [ACM (K) [ i0-1 ]], ..., INV (R) (R) [ACM (K) [ i1 ]-1]).
  • INV and ACM have already been created, and the memory area required to hold the search results is only the storage area for i0 and i1 , regardless of the number of hits.
  • the i-th value of the counted result is given by the above information 2, and does not require any new storage area.
  • the number of occurrences of the i-th value of the counted result is given by equation (8), and does not require any new storage area.
  • D5A has the role of supplying values to virtual table data and indexes to virtual indexes.
  • SVL and NNC obtained by SN decomposition of a column
  • information 1 to information 4 listed above.
  • a D5A index can be created using a transposed structure (in other words, a transposed structure can be used as a data structure for indexes in sorting, searching, and aggregation).
  • a D5A index not only speeds up sorting, searching, and aggregation, but can also hold the results of sorting, searching, and aggregation in only a small amount of memory space.
  • ⁇ Virtual tabular data> For example, when performing a JOIN or UNION in an RDB (Relational Database), the source tabular data is read, compared, the data to be written is created, the storage location is determined, and the data is written to a newly secured storage area. This requires time and storage space. This is the first step in trying to utilize archived tabular data. The larger the newly generated tabular data is, the more serious this problem becomes. This is because it takes a long time to generate and requires a large storage area. Moreover, often only a small portion of the generated tabular data is used.
  • RDB Relational Database
  • Virtual tabular data solves the above problem by creating the necessary parts when they are needed.
  • the cell in the source tabular data that corresponds to that cell is referenced at that time and displayed.
  • a mapping that defines the correspondence between the cells in the virtual tabular data and the cells in one or more source tabular data must be defined in advance. This mapping can be from virtual tabular data to multiple source tabular data, or conversely, from multiple source tabular data to virtual tabular data; both are essentially the same.
  • the destination of the mapping in the former is a set of two pieces of information, namely, which cell in which source tabular data
  • the latter requires only one piece of information, namely, which cell in the virtual tabular data, and is therefore easier to define. Therefore, the latter will be explained below. Both require an inverse mapping.
  • the virtual index requires an inverse mapping, and in the latter, it is necessary when the virtual tabular data references the source tabular data to obtain a value.
  • an allocation mapping The latter mapping of which cells in each source tabular data correspond to which cells in the virtual tabular data is called an allocation mapping.
  • an actual allocation mapping defines a mapping from each source column, which is a column in the source tabular data, to a virtual column, which is a column in the virtual tabular data.
  • Each source column is divided into one or more intervals, and for each interval, cells in that interval are associated with cells in the virtual column using a correspondence table or rules. This correspondence for each interval is called an interval mapping.
  • An allocation mapping is the sum of all interval mappings.
  • rs indicates the record number on the source table format data
  • rv indicates the record number on the virtual table format data.
  • a virtual column which is a column on virtual table format data, is composed of allocation mappings from one or more source columns.
  • the virtual column is allocated from source column 0 and source column 1.
  • the blank D5A with source column 1 in the bottom left of Figure 5 is a D5A that is automatically generated programmatically when a virtual column is generated.
  • Blank D5A supplies blank values to unassigned cells in the virtual column, so that the virtual column satisfies the bijection condition described below. If the bijection condition is satisfied, a virtual index is automatically provided for the virtual table format data.
  • it is not necessary to sort, search, or aggregate virtual table format data For example, there are cases when you want to use the entire result of a UNION or JOIN as is. In that case, you can of course define and use virtual table format data without considering the bijection condition.
  • Each source column is divided into one or more source intervals.
  • source column 0 is divided into interval 1 and interval 2.
  • There are two types of mappings from each source interval to a virtual column i.e., interval mappings).
  • the first is an enumeration mapping defined by an A-mapping M whose elements are natural numbers and have no duplicates.
  • the second is a linear function mapping defined by a linear function.
  • the former enumeration mapping can define any allocation mapping, but it consumes a lot of memory space.
  • the latter linear function mapping is a mapping in which the M of the enumeration mapping is replaced by a linear function. It consumes only a small amount of memory space and can define even large interval mappings, but it can only handle allocations with regularity.
  • interval mappings have been defined for all source intervals, the allocation mapping is complete.
  • any of the above interval mappings are defined, their inverse mappings and the conditions for the existence of the inverse mappings are also determined.
  • the source interval in which the above inverse mappings exist is identified from the record number of the virtual column, then the inverse mapping of that interval mapping is used to identify the record number in the source column, and the value is obtained from that record number and displayed.
  • ⁇ Interval mapping by enumeration mapping and its inverse mapping> 6 shows an example of allocation by enumeration mapping.
  • Rs is the size of the source column
  • rs is the record number of the source column
  • Rv is the size of the virtual column
  • rv is the record number of the virtual column
  • Q is an interval on the source column
  • q is the start position of interval Q
  • u is the length of interval Q
  • V is an interval on the virtual column corresponding to interval Q
  • v is the start position of interval V
  • w is the length of interval V.
  • M is an A-map whose elements are natural numbers with no duplicates, and can be subjected to LP decomposition.
  • the top line of equation (12) shows the LP decomposition.
  • L is a unique ascending-order array, and a bisection search can be used to determine whether an element exists and, if so, where it appears.
  • Equation (12) shows how to find the position in L where rv appears, and j is its position. If j cannot be found, it means that rv has not accepted the mapping from source section Q, and there is no inverse mapping.
  • Rs represents the size of the source column
  • rs represents the record number of the source column
  • Rv represents the size of the virtual column
  • rv represents the record number of the virtual column
  • Q represents an interval on the source column
  • q represents the start position of interval Q
  • u represents the length of interval Q
  • V represents an interval on the virtual column corresponding to interval Q
  • v represents the start position of interval V
  • w represents the length of interval V.
  • rs (rv-b)/a Formula (14)
  • v ⁇ rv ⁇ v+w is not true
  • rs is not an integer
  • rv is not the range of F.
  • Equation (13) that defines the linear function mapping.
  • Fig. 7 the numbers written beside the source column and virtual column are record numbers.
  • Source interval 1 of source column 0 is interval mapped by linear function type mapping
  • source interval 2 of source column 0 is interval mapped by enumeration type mapping
  • source interval 1 of source column 1 is interval mapped by linear function type mapping.
  • the definition of each interval mapping is as follows.
  • the virtual tabular data is composed of the following information.
  • Step 4-2 If L 0 [i] ⁇ L 1 [j], set i ⁇ i+1 and return to step 4-1. However, if the result of setting i ⁇ i+1 is that i exceeds the maximum value of the index representing the elements of L 0 , it is determined that there is no collision and the process ends.
  • Step 4-3 If L 0 [i]>L 1 [j], set j ⁇ j+1 and return to step 4-1. However, if the result of setting j ⁇ j+1 is that j exceeds the maximum value of the index representing the elements of L 1 , it is determined that there is no collision and the process ends.
  • a 0 and a 1 are integers of 1 or more
  • b 0 and b 1 are integers.
  • Step 5-2 If y0 ⁇ y1 , set x0 ⁇ x0 + MaxInt(1, ( y1 - y0 ) div a0 ) and return to step 5-1. However, if the result of setting x0 ⁇ x0 + MaxInt(1, ( y1 - y0 ) div a0 ) is x0 > MinInt( N0 - 1, LCM( a0 , a1 ) div a0 ), it is determined that there is no collision and the process ends.
  • Step 5-3 If y0 > y1 , set x1 ⁇ - x1 + MaxInt(1, ( y0 - y1 ) div a1 ) and return to step 5-1. However, if the result of setting x1 ⁇ - x1 + MaxInt(1, ( y0 - y1 ) div a1 ) is x1 > MinInt( N1 - 1, LCM( a0 , a1 ) div a1 ), it is determined that there is no collision and the process ends.
  • MaxInt is a function that selects the maximum integer
  • MinInt is a function that selects the minimum integer
  • div is an integer division function (the remainder is truncated)
  • LCM is a function that returns the least common multiple.
  • (v 1 , . . . , v 1 +w 1 -1) is an ascending array of size M.
  • Step 6-3 If y 0 (n) ⁇ y 1 (m), return to step 6-1 with n ⁇ (y 1 (m)-y 0 (n)) diva 0. However, if n ⁇ N as a result of setting n ⁇ (y 1 (m)-y 0 (n)) diva 0 , end the process as "no collision".
  • ⁇ Virtual Index> So far, we have explained a method for creating virtual tabular data that directly or indirectly inherits values from D5A. Below, we will explain why a virtual transposed structure is automatically established on virtual tabular data by directly or indirectly inheriting the transposed structure on D5A.
  • a virtual index that uses it as a data structure for indexing is also automatically established.
  • a virtual index has the same functions and characteristics as a D5A index because it uses the same algorithm as a D5A index, but only uses a virtual transposed structure instead of a transposed structure. In other words, it is possible to speed up sorting, searching, and aggregation of columns, and even huge sorting results, search results, and aggregation results can be held in only a small memory area.
  • the virtual transposed structure is a structure that has a virtual SVL, virtual ACM, and virtual INV.
  • the virtual SVL, virtual ACM, and virtual INV are virtual arrays.
  • a virtual array is a mechanism with the same functionality as an array, in that it does not hold values like virtual tabular data, its size W is known in advance, and when i ⁇ 0,1,...,W-1 is specified, the i-th element can be extracted in approximately O(log(R)) or less.
  • the virtual SVL, virtual ACM, and virtual INV are automatically established if the allocation mapping that defines the virtual tabular data satisfies the following bijective conditions.
  • the source column is bijective If the source column is D5A, it can be said that the source column is bijective. If the source column is a virtual column, it can be said that the source column is bijective if it satisfies 1 to 3 above.
  • a virtual transposed structure can be constructed from multiple transposed structures, and then verify that a virtual index that uses this virtual transposed structure can perform sorting, searching, and aggregation at high speed, and that sort results, search results, and aggregation results can be stored by simply allocating a small amount of new memory space.
  • a virtual index that uses this virtual transposed structure can perform sorting, searching, and aggregation at high speed, and that sort results, search results, and aggregation results can be stored by simply allocating a small amount of new memory space.
  • further virtual transposed structures can be created hierarchically from virtual transposed structures and transposed structures, and that a virtual index that uses this can also perform sorting, searching, and aggregation at high speed, and that sort results, search results, and aggregation results can be stored by simply allocating a small amount of new memory space.
  • we verify that the operation of a hierarchically created virtual transposed structure can be easily understood by using spectral decomposition.
  • FIG. 8 shows a virtual column C V (8) defined from source column #0: C 0 (4) and source column #1: C 1 (4) .
  • the transposed structure of source column #0, the transposed structure of source column #1, and the virtual transposed structure are shown in Fig. 9.
  • SVL, ACM, and INV in the transposed structure of source column #0 are denoted as SVL0 , ACM0 , and INV0 , respectively
  • SVL, ACM, and INV in the transposed structure of source column #1 are denoted as SVL1 , ACM1 , and INV1 , respectively.
  • SVL, ACM, and INV in the virtual transposed structure of the virtual column are denoted as SVLV , ACMV , and INVV , respectively.
  • INV 0 and INV 1 are arrays that store transposed record numbers, and since the record numbers in the source column are mapped to the record numbers in the virtual column by allocation mapping, when reading INV 0 and INV 1 , they must be converted to INV 0 ' and INV 1 ', respectively.
  • INV 0 ' and INV 1 ' can be calculated by the following formula (15).
  • Formula (15)-2 A method for constructing a virtual transposed structure will be described below in the order of virtual arrays SVL V , ACM V , and INV V , using FIG. 9 as an example.
  • v is selected from SVL 0 or SVL 1.
  • this v follows the above rule that determines the magnitude relationship taking into account the order of the source column.
  • the sum j of the number of values smaller than v in SVL 0 and SVL 1 is found. If j ⁇ i, v' larger than v is selected and the above is repeated. The same process is carried out when j>i (but v' smaller than v is selected).
  • the above method of finding SVL V [i] can be done in approximately O(log(K)). Since the size of SVL V is known and the i-th element can be extracted in O(log(R)) or less, it can be considered that a virtual array SVL V exists.
  • a virtual array SVL V (A 0 , B 0 , B 1 , C 0 , C 1 , D 1 ) can be created.
  • ACM V size of ACM V is obtained as the size of SVL V.
  • ACM V [i] can be done in approximately O(log(K)). Then, since the size of ACM V is known and the i-th element can be extracted in O(log(R)) or less, it can be considered that a virtual array ACM V exists.
  • a virtual array ACM V (1, 3, 5, 6, 7, 8) can be created.
  • the size of INV V is known to be R, where R is the sum of the sizes of the source columns.
  • j is the number of the interval on INV V that ACM V determines.
  • ACM V The size of ACM V is defined as K V.
  • K V is the sum of the sizes of ACM 0 and ACM 1.
  • an appropriate j is selected from 0, 1, ..., K V -1, and the interval ACM V [j-1] to ACM V [j]-1 is obtained using the method explained in "Method of constructing virtual array ACM V ".
  • the above method of finding INV V [i] can be performed in approximately O(log(K)). Since the size of INV V is known and the i-th element can be extracted efficiently, it can be considered that a virtual array INV V exists.
  • Sorting with a Virtual Index Let's try sorting with a virtual index using a virtual inverted structure. Since NNC is not shown in Figures 8 and 9, we use C v (8) in Figure 8 instead. The sorting result is as follows.
  • a inverted structure is a data structure for a D5A index, and for similar reasons, we can say that a virtual inverted structure is a data structure for a virtual index.
  • the virtual transposed structure is composed of references to the transposed structure of the source column, but if the source column is a virtual column, the transposed structure is also a virtual transposed structure, so in that case, the virtual transposed structure is constructed hierarchically.
  • FIG. 10 shows an example in which virtual tabular data C V0 (5) is created using D5A files C 0 (3) and C 1 (2) , and further virtual tabular data C V1 (8 ) is created using the virtual tabular data C V0 (5) and D5A file C 2 (3) .
  • the definition of the allocation mapping is shown below.
  • Sorting using a virtual index of hierarchically created virtual table format data Let's try sorting using a virtual index that uses a hierarchically created virtual inverted structure. Since NNC is not shown in Figures 10 and 11, we will use CV1(8) in Figure 10 instead. The sorting result is as follows.
  • C V0(5) A 0 : (3) + B 0 : (2,0)
  • C 1 (2) A 1 : (4) + C 1 (1) Therefore, C V0(5) can be expressed as follows:
  • C V0 (5) and C 2 (3) can be expressed by spectral decomposition as follows.
  • C V0 (5) A 0 :(1)+A 1 :(5)+B 0 :(7,2)+C 1 (3)
  • C 2 (3) A 2 : (4) + B 2 : (6) + D 2 : (0) Therefore, C V1(8) can be expressed as follows:
  • the search result string for "C" is (7, 2, 6, 3). The calculation can be done in the same way as in Table 3 above. Therefore, when doing manual calculations, calculations using spectral decomposition are easy to understand and excellent. It can be seen that...
  • Fig. 12 An example of the overall configuration of a system including a data processing device 10 according to this embodiment is shown in Fig. 12.
  • the data processing device 10 according to this embodiment is communicably connected to database servers that are distributed and arranged on a network 20 such as the Internet.
  • These database servers store at least one of D5A and virtual table format data.
  • the data processing device 10 has a virtual tabular data creation unit 101, a sorting unit 102, a search unit 103, a compilation unit 104, and a memory unit 105.
  • the virtual tabular data creation unit 101, the sorting unit 102, the search unit 103, and the compilation unit 104 are realized, for example, by a process in which one or more programs installed in the data processing device 10 are executed by a processor such as a CPU (Central Processing Unit).
  • the memory unit 105 is realized, for example, by a HDD (Hard Disk Drive), SSD (Solid State Drive), flash memory, etc.
  • the virtual tabular data creation unit 101 creates virtual tabular data having information 1 to 5 described in the above "Virtual tabular data configuration method.” In addition, when defining the interval mapping 5 described in the above “Virtual tabular data configuration method,” the virtual tabular data creation unit 101 determines whether or not there is a collision in the allocation destinations due to the interval mapping (allocation mapping) by the method described in "Detecting collisions of allocations from different intervals.”
  • the sort unit 102 executes sorting with a virtual index using the virtual transposed structure of the virtual table-format data described above. For example, the sort unit 102 uses the virtual column to be sorted of the virtual table-format data and the virtual INV included in the virtual transposed structure of the virtual column, and calculates the sort result by index calculation of those.
  • the search unit 103 When the search unit 103 receives search conditions, it executes a search with a virtual index using the virtual transposed structure of the virtual table-format data described above. For example, the search unit 103 calculates formulas (8) and (10) using the virtual column to be searched in the virtual table-format data, the search conditions for that virtual column, and the virtual INV and virtual ACM included in the virtual transposed structure of that virtual column, and then calculates the search results by index calculation of the virtual column and the calculation results of formulas (8) and (10).
  • the aggregation unit 104 performs aggregation using a virtual index that uses the virtual transposed structure of the virtual table-format data described above. For example, the aggregation unit 104 performs aggregation using the above information 2 and formula (8) using the virtual transposed structure of the virtual column to be aggregated of the virtual table-format data.
  • the storage unit 105 stores various data (e.g., virtual table format data, D5A, sorting results, search results, aggregation results, etc.).
  • data e.g., virtual table format data, D5A, sorting results, search results, aggregation results, etc.
  • FIG. 13 An example of the hardware configuration of the data processing device 10 according to this embodiment is shown in Fig. 13. As shown in Fig. 13, the data processing device 10 according to this embodiment has an input device 201, a display device 202, an external I/F 203, a communication I/F 204, a RAM (Random Access Memory) 205, a ROM (Read Only Memory) 206, an auxiliary storage device 207, and a processor 208. Each of these pieces of hardware is connected to each other via a bus 209 so as to be able to communicate with each other.
  • a bus 209 so as to be able to communicate with each other.
  • the input device 201 is, for example, a keyboard, a mouse, a touch panel, a physical button, etc.
  • the display device 202 is, for example, a display, a display panel, etc. Note that the data processing device 10 does not have to have at least one of the input device 201 and the display device 202, for example.
  • the external I/F 203 is an interface with external devices such as a recording medium 203a.
  • recording media 203a include a CD (Compact Disc), a DVD (Digital Versatile Disk), an SD memory card (Secure Digital memory card), and a USB (Universal Serial Bus) memory card.
  • the communication I/F 204 is an interface for connecting the data processing device 10 to the network 20.
  • the RAM 205 is a volatile semiconductor memory (storage device) that temporarily stores programs and data.
  • the ROM 206 is a non-volatile semiconductor memory (storage device) that can store programs and data even when the power is turned off.
  • the auxiliary storage device 207 is a non-volatile storage device such as an HDD, SSD, or flash memory.
  • the processor 208 is, for example, a CPU or other type of arithmetic device.
  • the hardware configuration shown in FIG. 13 is an example, and the data processing device 10 may have other hardware configurations.
  • the data processing device 10 may have multiple auxiliary storage devices 207 or multiple processors 208, may not have some of the hardware shown in the figure, or may have various hardware other than the hardware shown in the figure.
  • Step S101 First, the virtual table-format data creation unit 101 accepts the number of records of the virtual table-format data and the name and data type of the virtual column (information 1 and 2 described in "Virtual table-format data configuration method" above). Note that the number of records of the virtual table-format data and the name and data type of the virtual column are specified, for example, by the user.
  • Step S102 Next, the virtual tabular data creation unit 101 accepts the specification of the URL or path of one or more source tabular data (the information of 3 described in the "Virtual tabular data configuration method" above).
  • the URL or path of the one or more source tabular data is specified, for example, by the user. Also, the URL or path of one or more columns included in the one or more source tabular data may be specified.
  • Step S103 Next, the virtual tabular data creation unit 101 accepts the definition of the source column and source section in each source tabular data (information 4 described in "Virtual tabular data configuration method" above). Note that the definition of the source column and source section in each source tabular data is specified by, for example, the user.
  • Step S104 Next, the virtual tabular data creation unit 101 accepts the definition of the interval mapping for each source interval (the information in 5 described in the above "Virtual tabular data construction method") and calculates the definition of the inverse mapping. Note that the definition of the interval mapping and its inverse mapping for each source interval is specified, for example, by the user. Also, once the interval mapping is defined, its inverse mapping is automatically determined by equations (12) and (14) and stored in the storage unit 105.
  • Step S105 Finally, the virtual tabular data creation unit 101 stores the information received in steps S101 to S104 above in the storage unit 105 as virtual tabular data.
  • Step S201 The sort unit 102 executes a sort using a virtual index that uses the virtual transposed structure of the virtual column to be sorted among the virtual columns of the virtual table format data.
  • Step S202 Then, the sorting unit 102 stores the sorting result in step S201 in the storage unit 105. However, the sorting unit 102 does not have to store the sorting result.
  • Step S301 First, the search unit 103 accepts search conditions.
  • Step S302 Next, the search unit 103 executes a search in a virtual index using the virtual transposed structure of the virtual column to be searched among the virtual columns of the virtual table format data.
  • Step S303 The search unit 103 then stores the search results from step S302 in the storage unit 105.
  • Step S401 The aggregation unit 104 performs aggregation using a virtual index that uses the virtual transposed structure of the virtual column to be aggregated, among the virtual columns of the virtual table format data.
  • Step S402 The aggregation unit 104 then stores the aggregation result from step S303 in the storage unit 105. However, the aggregation unit 104 does not have to store the aggregation result.
  • new virtual tabular data can be defined by allocation mapping using D5A or already defined virtual tabular data as source tabular data. Moreover, this virtual tabular data can be sorted, searched, and tallied at high speed using virtual indexes.
  • An index is realized by a data structure for indexing and a set of algorithms that use that data structure to speed up processing.
  • a transposed structure can be considered as a data structure for indexing that speeds up sorting, searching, and aggregation.
  • a virtual transposed structure for a column can be created by rearranging the elements of the column from the transposed structure.
  • a virtual transposed structure can also be created from multiple transposed structures.
  • multiple virtual transposed structures can be hierarchically organized to create a further virtual transposed structure. In this way, a virtual transposed structure can be created hierarchically or by rearranging the elements of a column.
  • An index algorithm that uses a transposed structure can also be applied to a virtual transposed structure, which becomes a virtual index. Existing indexes do not have a data structure for indexing that can be combined or hierarchically combined like a transposed structure, so inheritance is not possible when combining or hierarchically.
  • REFERENCE SIGNS LIST 10 Data processing device 20 Network 101 Virtual table format data creation unit 102 Sorting unit 103 Search unit 104 Counting unit 105 Storage unit 201 Input device 202 Display device 203 External I/F 203a Recording medium 204 Communication I/F 205 RAM 206 ROM 207 Auxiliary storage device 208 Processor 209 Bus

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Computational Linguistics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本開示の一態様によるデータ処理装置は、１以上の表形式データに含まれる１以上のカラムが持つ第１のデータ構造を所定の写像により変換した第２のデータ構造を持つ仮想カラムで構成される仮想表形式データに対して、前記第２のデータ構造をインデックスとして利用したソート操作、検索操作又は集計操作を行うデータ操作部、を有する。

Description

データ処理装置、データ処理方法、及びプログラム
　本開示は、データ処理装置、データ処理方法、及びプログラムに関する。
　近年、各種センサ機器や観測機器等の発達により、センシング結果や観測結果等を表す大量のデータ（いわゆる、ビッグデータ）が格納された表形式データが得られるようになった。このため、１つ以上の表形式データから複数のカラムを選択して、自身の利用目的に沿った仮想的な表形式データ（以下、仮想表形式データという。）を作成したいというニーズが増えている。このようなニーズを達成するための１つの方法は、仮想データベース又はデータ仮想化と呼ばれる技術を利用することである（例えば、非特許文献１参照）。これは、利用者からクエリを受け付けると、その背後に分散配置されているデータベースに対してサブクエリを実行するという技術である。
「データハブ vs データレイク vs データの仮想化 - MarkLogic」，インターネット＜ＵＲＬ：https://jp.marklogic.com/product/comparisons/data-hub-vs-data-lake/＞
　しかしながら、仮想データベース又はデータ仮想化と呼ばれる技術では、実データベースのソート、検索、集計を実現するインデックスを仮想データベースに継承させることができない。
　本開示は、上記の点に鑑みてなされたもので、実表形式データのソート、検索、集計を実現するインデックスを仮想表形式データに継承できる技術を提供する。
　本開示の一態様によるデータ処理装置は、１以上の表形式データに含まれる１以上のカラムが持つ第１のデータ構造を所定の写像により変換した第２のデータ構造を持つ仮想カラムで構成される仮想表形式データに対して、前記第２のデータ構造をインデックスとして利用したソート操作、検索操作又は集計操作を行うデータ操作部、を有する。
　実表形式データのソート、検索、集計を実現するインデックスを仮想表形式データに継承できる技術が提供される。
値を保持するＤ５Ａを起点として階層的に構築される仮想表形式データの一例を説明するための図である。 Ａ写像の一例（その１）を説明するための図である。 Ａ写像の一例（その２）を説明するための図である。 Ｄ５Ａの一例を説明するための図である。 割り付けの一例を説明するための図である。 列挙型写像による割り付け方法の一例を説明するための図である。 １次関数型写像による割り付け方法の一例を説明するための図である。 ソースカラムと仮想カラムの一例を示す図である。 ソースカラムと転置構造体と仮想転置構造体の一例を示す図である。 ２階層の仮想表形式データの割り付け写像の一例を説明するための図である。 ２階層の仮想表形式データの仮想転置構造体の一例を説明するための図である。 本実施形態に係るデータ処理装置を含むシステムの全体構成の一例を示す図である。 本実施形態に係るデータ処理装置のハードウェア構成の一例を示す図である。 仮想表形式データの作成処理の流れの一例を示すフローチャートである。 仮想表形式データにおけるソート処理の流れの一例を示すフローチャートである。 仮想表形式データにおける検索処理の流れの一例を示すフローチャートである。 仮想表形式データにおける集計処理の流れの一例を示すフローチャートである。
　以下、本発明の一実施形態について説明する。以下の実施形態では、まず、必要な説明及び定義を行った後、表形式データを表現するＤ５Ａと呼ぶデータを定義する。次に、Ｄ５Ａ又は他の仮想表形式データから新たな仮想表形式データを作成する方法と、（実）表形式データのインデックスを継承して仮想表形式データに対してソート、検索、集計を行う方法とを説明する。また、このとき、仮想表形式データが階層的に構築された場合でもそのインデックスを継承できることについても説明する。そして、最後に、このような仮想表形式データの作成とソート、検索、集計を行うことができるデータ処理装置１０について説明する。
　＜はじめに＞
　ＩｏＴ（Internet of Things）データ、様々な観測データ、ログデータ等のアーカイブデータの蓄積が日々進行している。これらの多くでは表形式データが日次や月次のように一定期間毎に１つにまとめられてアーカイブに追加されていくことが多い。アーカイブに追加された表形式データはＲｅａｄＯｎｌｙと考えてよい。このようなアーカイブの表形式データは巨大になることがあるし、しばしばＬＡＮ（Local Area Network）上及びインターネット上に分散している。
　上記のアーカイブの表形式データを活用しようとすると、一般に、以下の２つのステップを必要とし、いずれのステップでも長い時間が掛かり、また大きい記憶領域を消費することが多い、という問題がある。
　第１ステップは、新たな表形式データを生成するステップである。新たな表形式データは複数の表形式データをＵＮＩＯＮしたりＪＯＩＮしたり必要なカラムのみを抽出したりして作成される。もし元になる表形式データが巨大であったりインターネットのような広域ネットワーク上に分散していたりすると長い時間が掛かる。また、新たな表形式データが大きいとその収容に大きい記憶領域が必要になる。
　第２ステップは、ソートしたり検索したり集計したりするステップである。新たに作成された表形式データにはインデックスが付いておらず、ソート、検索、集計に時間が掛かる。それに加えて、新たな表形式データが大きい場合のソート結果、ヒット件数が大きい場合の検索結果、大きい集計結果はいずれも大きい記憶領域を必要とする。
　上記の２つのステップの問題は今日進行するアーカイブデータの巨大化と分散したアーカイブデータの利用ニーズの高まりにつれて日々深刻化している。
　そこで、上記の２つのステップの操作に要する時間を対話型での操作が成り立つ時間に短縮し、かつ、必要な記憶領域がわずかで済む技術を提案する。その操作対象の表形式データは、例えば、１兆レコードであってもよいし、１０万カラムであってもよい。また、その操作対象の表形式データのＵＮＩＯＮやＪＯＩＮ等の組み合わせを階層的に積み上げてもよい。更に、その操作対象の表形式データはＬＡＮ上に分散していてもよいし、インターネット上の複数のＨＴＴＰ（Hypertext Transfer Protocol）サーバ上に分散していてもよい。
　上記が可能になるのは、Ｄ５Ａというすべてのカラムにソート・検索・集計を高速化するインデックスが付いた表形式データのファイルフォーマットと、Ｄ５Ａファイルから直接又は間接的に値を継承する仮想表形式データと、Ｄ５Ａファイルのインデックスが使うデータ構造を直接又は間接的に継承して自動的に成立するデータ構造を使って成り立つ仮想表形式データ上の仮想インデックスとを用いてアーカイブデータの写像のネットワークシステムが構築できるからである。仮想表形式データと仮想インデックスは直接又は間接的にＤ５Ａと接続するだけで直ちに利用可能になり、それらはわずかな記憶領域しか消費しない。それに加えて、仮想インデックスを使って得られたソート結果、検索結果、集計結果はそれらがどんなに大きいものであってもわずかな記録領域しか必要としない。
　このようなＤ５Ａを用いたアーカイブデータの写像のネットワークは、「利用者が利用目的毎にそれに沿った仮想表形式データを作ってネットワーク上に分散したアーカイブデータを対話型で使う」という新しいアーカイブデータの利用法を可能にする。例えば、各組織においては組織内の各部門に分散するアーカイブデータを様々な目的で利用することを可能にし、インターネット上においては世界各地のＩｏＴデータ等のアーカイブデータを組み合わせたり抽出したりして様々に連係して利用することを可能にする。
　ここで、本明細書中で使用する用語を整理する。まず、Ｄ５Ａとは、すべてのカラムにソート・検索・集計を高速化するインデックスが付いた表形式データのファイルフォーマットのことである。次に、仮想表形式データとは、Ｄ５Ａファイル（Ｄ５Ａフォーマットのファイル）又は他の仮想表形式データから値を継承する表形式データのことである。なお、その継承元の表形式データをソース表形式データと呼ぶ。また、Ｄ５Ａ上のカラムをＤ５Ａカラム、Ｄ５Ａカラムのソート・検索・集計を高速化するインデックスをＤ５Ａインデックスと呼ぶ。仮想表形式データでも同様に、仮想カラム、仮想インデックスと呼ぶ。ソース表形式データでも同様に、ソースカラム、ソースインデックスと呼ぶ。また、Ｄ５Ａインデックスが使用するデータ構造を転置構造体、仮想インデックスが使用するデータ構造を仮想転置構造体、ソースインデックスが使用するデータ構造をソース転置構造体と呼ぶ。なお、仮想表形式データは「写像表形式データ」等と呼んでもよく、同様に仮想カラムは「写像カラム」等と呼んでもよい。
　＜問題の解決方法＞
　上述したように、アーカイブの表形式データを活用しようとすると、一般に、第１ステップと第２ステップの２つのステップを必要とし、いずれのステップでも長い時間が掛かり、また大きい記憶領域を消費することが多い、という問題がある。なお、第１ステップはＵＮＩＯＮしたりＪＯＩＮしたり必要なカラムのみを抽出したりして新たな表形式データを生成するステップ、第２ステップはソートしたり検索したり集計したりするステップである。
　第１ステップに時間が掛かるのは、値を読み出し比較し格納する時間が掛かるためである。そこで、その代わりに、ソース表形式データとなる表形式データが存在し、そのどのセルが、新たに作成される表形式データのどのセルに写されるかという対応表とルールで定義される写像を用いて、その写像で新たな表形式データを作成するというアプローチが考えられる。アーカイブデータの場合、その写像の定義は可能かつコンパクトにまとまるケースが少なくない。その場合、新たな表形式データは値を持つ必要が無く、特に新たな表形式データが巨大なときはこのアドバンテージは大きい。新たな表形式データは写像の定義をロードするわずかな時間だけで表示可能になり、必要とする記憶領域も写像の定義を保持するためのわずかなもので済むためである。この新たな表形式データは値を保持せず、元となる表形式データから値を継承することから、これは仮想表形式データである。第１ステップの問題は、このような仮想表形式データで解決できる。
　第２ステップでは、新たなに作成された表形式データのカラムにインデックスが付いていないことと、しばしば巨大になるソート結果・検索結果・集計結果を書き出すのに時間が掛かること、の２つで時間が掛かる。しかし、上記の仮想表形式データのすべてのカラムにはそのカラムのソート・検索・集計を高速化する仮想インデックスが自動的に存在することと、その仮想インデックスが巨大なソート結果・検索結果・集計結果でもわずかな記憶領域を使うだけで保持できるため書き出し時間を短縮できること、の２つにより時間が掛かる問題は解決される。また、仮想インデックスがそれらの結果の収容にわずかな記憶領域しか使わないことで記憶領域の問題も解決される。このようにして第２ステップの問題は仮想インデックスで解決できる。
　このような仮想表形式データの元になる値と、仮想インデックスが用いるデータ構造の元になるデータ構造とを保持するのがＤ５Ａという表形式データの格納フォーマットで表現されたＤ５Ａファイルである。
　　≪Ｄ５Ａ：値とインデックスの供給源となる表形式データの格納フォーマット≫
　仮想表形式データは、１つ以上のソース表形式データから値を継承する。ソース表形式データは、別の仮想表形式データ、又は、Ｄ５Ａファイルと呼ばれる表形式データ、のいずれかである。前者の場合、その仮想表形式データは更に別のソース表形式データから値を継承し最終的にＤ５Ａファイルに辿り着く。したがって、仮想表形式データは直接的又は間接的にＤ５Ａファイルから値を継承して階層的に成り立っているといえる。
　仮想インデックスは仮想転置構造体を使ってソート・検索・集計を高速化する。その仮想転置構造体は、１つ以上のソース転置構造体を継承して自動的に成立する。ソース転置構造体とは、別の仮想表形式データ上の仮想転置構造体、又は、Ｄ５Ａファイル上の転置構造体、のいずれかである。前者の場合、その仮想転置構造体は更に別のソース転置構造体を継承し最終的にＤ５Ａファイル上の転置構造体に辿り着く。したがって、仮想転置構造体は直接的又は間接的にＤ５Ａファイル上の転置構造体を継承して階層的に成り立っているといえる。
　Ｄ５Ａは、仮想表形式データへ値を供給し、仮想転置構造体へ転置構造体を供給するための表形式データの格納フォーマットであり、値を保持しそのすべてのカラムに転置構造体を使うＤ５Ａインデックスを備える。
　　≪アーカイブデータの写像のネットワークシステムの実現≫
　アーカイブデータの写像のネットワークシステムの簡単な想定例を示し、ここまでに説明したＤ５Ａ、仮想表形式データ、仮想インデックスの使用方法について、図１を参照しながら説明する。図１は、東京、大阪、名古屋の各地域の日曜日から土曜日の気象観測データを１つにまとめる処理を示している。この処理は２段階で行われ、まず地域毎に７つの日次データをまとめて週次データにし、次にそれらの週次データを並置して１つの表形式データにまとめている。ここで、図１の左側にある３地域１週間分の２１個の日次データは５５Ａファイルに収容されている。図１の中央にある地域毎の３つの表形式データは仮想表形式データである。これらの仮想表形式データはそれぞれ図１の左側にある１週間分の７つのＤ５Ａファイルをソース表形式データとして、それらから必要なカラムを抽出した上でＵＮＩＯＮしている。図１の右側にある１つの仮想表形式データは、図１の中央にある地域毎の３つの仮想表形式データをソース表形式データとして、それらを並置している。
　図１に示すように、アーカイブデータの写像のネットワークは、Ｄ５Ａファイルを起点として、その上に仮想表形式データを階層的に構築したものである。既に述べたように、仮想表形式データには仮想インデックスが自動的に備わり、任意のカラムを短時間でソート・検索・集計でき、ソート結果・検索結果・集計結果を記憶するための記憶領域もわずかで済む。このような仮想表形式データは利用者の手元で作成し利用することができ、アーカイブデータの広汎な利用を促進することが期待できる。
　＜Ａ写像＞
　Ｄ５Ａ、仮想表形式データや仮想インデックスはすべて０から始まる自然数の連続区間から何等かの値（これも多くの場合は自然数）への写像の組み合わせで記述される。この写像は添字（インデックス）が０から始まる１次元配列（Ａｒｒａｙ）で表せるので、これをＡ写像と呼ぶ。Ａ写像を用いると対応関係を全体から眺めることが可能になり、その結果、集合や群としての性質を利用したアルゴリズムを導くことが可能になる。以下にＡ写像の利点を説明する。
　Ａ写像の第１の利点は、Ａ写像を様々に結合して新たなＡ写像を作り出せることである。簡単な例を挙げると検索の結果列を表すＡ写像Ｓを、カラムＡを表すＡ写像ＣＡと結合すればカラムＡの検索結果を表すＡ写像が得られ、カラムＢを表すＡ写像ＣＢと結合すればカラムＢの検索結果を表すＡ写像を得ることができる。このとき、Ｓは結果列を表すＡ写像であれば何でもよく、ＣＡ及びＣＢもカラムを表すＡ写像であれば何でもよい。そして、それらはローカルな記憶装置上に存在しても、ネットワーク上に存在してもよい。このようなＡ写像の結合は代数的な結合であるといえる。
　そして、Ａ写像とＡ写像の結合結果は必ずしも記憶領域に書き出される必要は無く、仮想的なＡ写像でもよい。仮想的なＡ写像とは１以上のＡ写像を結合元にして、全体のサイズが分かり、任意のｉ番目の部分だけを結合元から取り出すことができるＡ写像である。仮想的なＡ写像もＡ写像であるため、仮想的なＡ写像を結合して更なる仮想的なＡ写像を階層的に作ることができる。仮想表形式データのカラムは仮想的なＡ写像の一種であり、階層的に作ることができる。インデックスは、インデックスのためのデータ構造とそのデータ構造を使うアルゴリズムで実現される仕組みである。仮想インデックスは１つ以上の仮想的なＡ写像をインデックスのためのデータ構造として使うインデックスであり、階層的に作ることができる。
　Ａ写像の第２の利点は、Ａ写像を分解して新たなＡ写像を作り出せることである。Ａ写像を分解することにより、分解前のＡ写像には無い機能を持った新たなＡ写像を作り出して使うことが可能になる。特に有効な分解の一つは、表形式データ間でセルとセルの対応（マッピング）を定めるＡ写像ＭのＬＰ分解（Ａ写像ＬとＡ写像Ｐへの分解）である。ＭをＬとＰに分解すると、Ｌでバイセクションサーチによる効率の良い要素の検索が可能になり、Ｐで逆写像を求めることが可能になる。このとき、Ｍはマッピングを定めるＡ写像であれば何でもよく、Ｌは自動的にバイセクションサーチが可能なＡ写像になり、Ｐは自動的に逆元を持つＡ写像になる。Ａ写像の分解は新たなＡ写像を生み出すため、代数的な分解であるといえる。
　一方で、Ａ写像が１次元の配列であるため、大きいＡ写像への要素の挿入と要素の削除には時間が掛かる。しかし、アーカイブデータの場合は更新がほとんど無いため、このデメリットは問題にはならない。
　このようなＡ写像を用いると、高速にソート・検索・集計ができるインデックスをどのカラムにも等しく備える表形式データの格納フォーマットであるＤ５Ａを設計することができる。そして、Ｄ５ＡとＡ写像を使って仮想表形式データを定義することができる。その仮想表形式データには１つ以上のＡ写像をインデックスのためのデータ構造として使う仮想インデックスが自動的に備わる。すると、ネットワーク上に分散するアーカイブデータを様々に組み合わせて使える、アーカイブデータの写像のネットワークシステムを実現できる。
　そこで、以下では、まずＡ写像の定義を行い、その表記法を定める。次に、Ａ写像を結合するための演算子であるインデックス演算子を導入する。次に、Ａ写像の分解について述べ、特に重要なＳＮ分解、ＬＰ分解、スペクトル分解を説明する。最後に、Ａ写像を４つの側面で分類する。
　　≪Ａ写像の定義≫
　インデックスが０から始まり、サイズＮの１次元配列を考える。その１次元配列は定義域が０～Ｎ－１の自然数の連続区間、値域が最大Ｎ種類の離散区間である写像と見ることができる。これをＡ写像と呼ぶ。レコードに０から始まる連続するレコード番号が振られていれば、表形式データのカラムもレコード番号を定義域としたＡ写像とみなすことができる。
　例えば、図２に示すように、０番目の要素として「４」、１番目の要素として「０」、２番目の要素として「６」、３番目の要素として「３」が格納されている１次元配列を考える。この１次元配列は０を「４」、１を「０」、２を「６」、３を「３」にそれぞれ対応付けたものであるため、定義域が｛０，１，２，３｝、値域が｛０，３，４，６｝のＡ写像とみなすことができる。
　また、例えば、図３に示すように、０番目の要素として「Ｂｏｂ」、１番目の要素として「Ａｌｉｃｅ」、２番目の要素として「Ｃａｔｈｙ」、３番目の要素として「Ｂｏｂ」が格納されている１次元配列を考える。この１次元配列は０を「Ｂｏｂ」、１を「Ａｌｉｃｅ」、２を「Ｃａｔｈｙ」、３を「Ｂｏｂ」にそれぞれ対応付けたものであるため、定義域が｛０，１，２，３｝、値域が｛Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ｝のＡ写像とみなすことができる。
　なお、Ａ写像は１次元配列で表せるが、その写像としての側面を議論するときは写像といい、その操作を議論するときは配列という。それに伴い、写像として扱うときは定義域、値域といい、カラムや表形式データを含む配列のときはレコード番号、値ということにする。ただし、Ａ写像の表記法は可能な限り配列としての表記法を用いる。
　　≪Ａ写像の表記法≫
　以下に一般的な配列の表記法を取り入れたＡ写像の表記を記載する。
　表記法１．Ａ写像を要素の列挙で定義する場合は（ａ０，ａ１，・・・，ａｎ－１）と記載する。
　表記法２．Ａ写像Ａの定義域ｎを明示する場合はＡ（ｎ）と記載する。この表記法に従い、カラムは、例えば、Ｒを全レコード数としてＣ（Ｒ）等と記載する。
　表記法３．Ａ写像Ａの値域が自然数上にあり、その値域の最大値がｎ－１を超えないことがわかっているとき、値域を明示するためにＡ（ｎ）と記載する。
　表記法４．Ａ写像Ａ（ｎ）のｉ番目の要素をＡ（ｎ）［ｉ］と記載する。したがって、Ａ（ｎ）≡（Ａ（ｎ）［０］，Ａ（ｎ）［１］，・・・，Ａ（ｎ）［ｎ－１］）である。
　表記法５．（ｉ０，ｉ１，・・・），（ｊ０，ｊ１，・・・），・・・の連結を（ｉ０，ｉ１，・・・）＋（ｊ０，ｊ１，・・・）＋・・・と記載する。
　表記法６．Ａ写像の値域上のλが定義域上のｉ０，ｉ１，・・・からの写像を受け入れていることをλ：（ｉ０，ｉ１，・・・）と記載する。例えば、図３に示す例は、Ａｌｉｃｅ：（１），Ｂｏｂ：（０，３），Ｃａｔｈｙ：（２）と記載できる。
　表記法７．λ０：（ｉ０，ｉ１，・・・），λ１：（ｊ０，ｊ１，・・・），・・・を連結してひとまとめにするときは記号＋を使用して、λ０：（ｉ０，ｉ１，・・・）＋λ１：（ｊ０，ｊ１，・・・）＋・・・と表記する。ただし、このとき、λ０＜λ１＜・・・の順に並べる。例えば、図３に示す例は、Ａｌｉｃｅ：（１）＋Ｂｏｂ：（０，３）＋Ｃａｔｈｙ：（２）と記載できる。
　　≪Ａ写像を結合するインデックス演算子≫
　Ａ写像の結合を行って新たなＡ写像を作り出すインデックス演算子（Index Operator）と呼ぶ演算子・を以下で定義する。
　Ａ（ｎ）・Ｂ（ｍ） （ｎ）＝（Ａ（ｎ）［Ｂ（ｍ） （ｎ）［０］］，・・・，Ａ（ｎ）［Ｂ（ｍ） （ｎ）［ｍ－１］］）　　　　式（１）
　上記のインデックス演算子には、以下の性質１～性質３に示す性質がある。
　性質１：結合則が成り立つ。すなわち、（Ａ（ｎ）・Ｂ（ｍ））・Ｃ（ｋ）＝Ａ（ｎ）・（Ｂ（ｍ）・Ｃ（ｋ））が成り立つ。
　性質２：結合結果を表す配列のサイズは右側の配列のサイズである。
　性質３：結合結果を表す配列のデータ型は左側の配列のデータ型である。
　ここで、例を使って結合則を確かめる。Ａ（３）＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）、Ｂ（４）＝（１，０，２，１）、Ｃ（３）＝（０，２，１）とする。このとき、（Ａ（３）・Ｂ（４））・Ｃ（３）＝（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）・（０，２，１）＝（Ｂｏｂ，Ｃａｔｈｙ，Ａｌｉｃｅ）となる。一方で、Ａ（３）・（Ｂ（４）・Ｃ（３））＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）・（１，２，０）＝（Ｂｏｂ，Ｃａｔｈｙ，Ａｌｉｃｅ）となり、両者は一致する。
　上記の性質１及び２により、インデックス演算子によるＡ写像の結合の結果として得られたＡ写像に出現し得る値の種類数は、インデックス演算子が結合したＡ写像中の最小のＡ写像のサイズ以下になる。これは行列におけるｒａｎｋに似た指標となる。
　　≪Ａ写像の分解≫
　インデックス演算子を用いてＡ写像を結合すると、ただ１つのＡ写像が得られる。一方で、１つのＡ写像は様々なＡ写像に分解できる。例えば、（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）は、（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）・（１，０，２，１）と分解することもできるし、（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）＝（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ）・（０，１，２，０）と分解することもできる。
　このような中で一意の分解方法は特別な価値があり、ソートや検索を高速化したり、逆写像を求めたりすることが可能になる。そこで、以下では、その一意の分解方法であるＳＮ分解、ＬＰ分解、スペクトル分解を説明する。
　・ＳＮ分解
　１つのＡ写像を２つに分解する方法で、得られる２つのＡ写像のうちの左側のＡ写像が左辺のＡ写像に出現する値だけを保持し、それらの値をユニークかつ昇順に保持する場合は１通りしか存在しない。この分解をＳＮ分解と呼ぶ。
　例えば、（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）・（１，０，２，１）はＳＮ分解の例である。
　右辺のユニークかつ昇順である第１項をＳＶＬ（Sorted Value List）と呼ぶ。上記の例ではＳＶＬ＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）である。右辺の第２項は左辺の各要素をＳＶＬ中の格納位置で置き換えたものであると考えることができる。これをＮＮＣ（Natural Numbered Column）と呼ぶ。上記の例ではＮＮＣ＝（１，０，２，１）である。
　このようなＳＮ分解を一般的に定義すると以下になる。
　Ｃ（Ｒ）＝ＳＶＬ（Ｋ）・ＮＮＣ（Ｒ） （Ｋ）；
　ｉ，ｊ∈０，・・・，Ｋ－１かつｉ＜ｊ⇒ＳＶＬ（Ｋ）［ｉ］＜ＳＶＬ（Ｋ）［ｊ］
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　式（２）
　式（２）では上段でカラムＣ（Ｒ）がＳＶＬ（Ｋ）とＮＮＣ（Ｒ） （Ｋ）に分解されることを表しており、下段でＳＶＬ（Ｋ）の要素は昇順に並ぶことを表している。なお、ＮＮＣ（Ｒ） （Ｋ）については、その表記から０，・・・，Ｋ－１の自然数を要素とするサイズＲのＡ写像であることがわかる。
　ＳＮ分解を使うと、自然数を要素とするとは限らないＡ写像から自然数を要素とするＡ写像ＮＮＣを取り出すことができる。取り出したＮＮＣを使うと、カウンティングソート等の自然数の性質を使った効率の良いアルゴリズムが利用可能になる。
　　（ＳＮ分解のアルゴリズム）
　ここで、（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）を例にＳＮ分解のアルゴリズムの一例を述べる。ＳＮ分解のアルゴリズムでは、以下の手順１－１～手順１－５が実行される。
　手順１－１：（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）の各値にＡ写像内の位置を添えて、（（Ｂｏｂ，０），（Ａｌｉｃｅ，１），（Ｃａｔｈｙ，２），（Ｂｏｂ，３））を作成する。
　手順１－２：値と位置の組で大小関係を評価しながらソートして、（（Ａｌｉｃｅ，１），（Ｂｏｂ，０），（Ｂｏｂ，３），（Ｃａｔｈｙ，２））を得る。
　手順１－３：各値に対して、その値の小さい順に０から順番に値番号を付与して、ソート結果（（Ａｌｉｃｅ＝０，１），（Ｂｏｂ＝１，０），（Ｂｏｂ＝１，３），（Ｃａｔｈｙ＝２，２））を得る。
　なお、上記の例では同じ値Ｂｏｂが２回出現しているが、いずれのＢｏｂにも値番号１が付与されることに留意されたい。また、上記のソート結果は、（（値＝値番号，Ａ写像内の位置），・・・）という構造である。例えば、上記の例のソート結果における第１要素（Ａｌｉｃｅ＝０，１）では、値はＡｌｉｃｅ、値番号は０、Ａ写像内の位置は１である。
　手順１－４：上記のソート結果を使ってＳＶＬの格納領域（領域のサイズは３）を確保し、「ＳＶＬ［値番号］＝値」として書き込む。すなわち、ＳＶＬ［０］＝Ａｌｉｃｅ、ＳＶＬ［１］＝Ｂｏｂ、ＳＶＬ［２］＝Ｃａｔｈｙとして書き込む。これにより、ＳＶＬ＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）が完成する。
　手順１－５：上記のソート結果を使ってＮＮＣの格納領域（領域のサイズは４）を確保し、「ＮＮＣ［Ａ写像内の位置］＝値番号」として書き出す。すなわち、ＮＮＣ［１］＝０、ＮＮＣ［０］＝１、ＮＮＣ［３］＝１、ＮＮＣ［２］＝２として書き込む。これにより、ＮＮＣ＝（１，０，２，１）が完成する。
　以上により、（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）・（１，０，２，１）が得られる。
　・ＬＰ分解
　ＬＰ分解は、重複のない自然数を要素とするＡ写像Ｍ（Mapping projection）を２つに分解するＳＮ分解の特殊なケースである。例えば、（５，２，７，３）＝（２，３，５，７）・（２，０，３，１）はＬＰ分解の例である。
　ＬＰ分解で得られる右辺の第１項は自然数を要素とし、ユニークかつ昇順になる。これをＬ（seLection）と呼ぶ。上記の例ではＬ＝（２，３，５，７）である。一方で、右辺の第２項は左辺の各要素をＬ中の格納位置で置き換えたものであると考えることができる。これをＰ（Permutation）と呼ぶ。上記の例ではＰ＝（２，０，３，１）である。ＬＰ分解ではＭ、Ｌ、Ｐは同じサイズになる。
　ＬＰ分解を行うと、Ｌを用いてＭ中の要素の有無及び要素の順位を求め、Ｐを用いて逆元を求めることが可能になる。なお、ＬＰ分解はＳＮ分解と同じアルゴリズムで実施できる。
　・スペクトル分解
　上記の表記法７は各値にその値が出現するＡ写像上の位置（インデックス）を新たなＡ写像として表記するものである。これをＡ写像のスペクトル分解と呼ぶ。スペクトル分解により、Ａ写像を値域から定義域に向かって見ることが可能になり、様々なアルゴリズムを可能にする。以下、Ａ写像であるカラムのスペクトル分解によりカラムのソート・検索・集計が簡単にできるようになる例を示す。
　　（ソートの実行）
　図３に示す例で、ソートは、カラムのスペクトル分解Ａｌｉｃｅ：（１）＋Ｂｏｂ：（０，３）＋Ｃａｔｈｙ：（２）から値を外して（１）＋（０，３）＋（２）とし、表記法５で定めた連結を行ってソート結果列（１，０，３，２）を得ることができる。なお、ソート結果はカラムＣ（Ｒ）＝（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）とソート結果列とを以下のように結合して得ることができる。
　ソート結果＝Ｃ（Ｒ）・ソート結果列＝（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）・（１，０，３，２）＝（Ａｌｉｃｅ，Ｂｏｂ，Ｂｏｂ，Ｃａｔｈｙ）
　　（検索の実行）
　図３に示す例で、Ｂｏｂの検索は、カラムのスペクトル分解Ａｌｉｃｅ：（１）＋Ｂｏｂ：（０，３）＋Ｃａｔｈｙ：（２）からバイセクションサーチでＢｏｂのパートを特定し、それを取り出してＢｏｂ：（０，３）を得て、検索結果列（０，３）を得ることができる。なお、検索結果は、カラムＣ（Ｒ）＝（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）と検索結果列とを以下のように結合して得ることができる。
　検索結果＝Ｃ（Ｒ）・検索結果列＝（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）・（０，３）＝（Ｂｏｂ，Ｂｏｂ）
　　（集計の実行）
　図３に示す例で、集計は、カラムのスペクトル分解Ａｌｉｃｅ：（１）＋Ｂｏｂ：（０，３）＋Ｃａｔｈｙ：（２）から値とその出現回数を取り出し、集計結果＝Ａｌｉｃｅ：１回、Ｂｏｂ：２回、Ｃａｔｈｙ：１回を得ることができる。
　　（スペクトル分解の一般式）
　ここで、スペクトル分解を一般的に書き直すと以下となる。
Figure JPOXMLDOC01-appb-M000001
 　式（３）で、Ｒは全レコード数、λはキー値、ｗはキー値λに属する転置レコード番号の数、Ｘは転置レコード番号の配列である。
　例えば、図３に示す１次元配列のソート結果を式（３）の形で書く場合、以下となる。
　Ｒ＝４，λ０＝Ａｌｉｃｅ，λ１＝Ｂｏｂ，λ２＝Ｃａｔｈｙ
　ｗ０＝１，ｗ１＝２，ｗ２＝１
　Ｘ０（１） （４）＝（１），Ｘ１（２） （４）＝（０，３），Ｘ２（１） （４）＝（２）
　　（スペクトル分解のアルゴリズム）
　ここで、（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）を例にＡ写像をスペクトル分解するアルゴリズムの一例を示しておく。そのアルゴリズムは、以下の手順２－１～手順２－３からなる。
　手順２－１：（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）の各値にＡ写像内の位置を添えて、（（Ｂｏｂ，０），（Ａｌｉｃｅ，１），（Ｃａｔｈｙ，２），（Ｂｏｂ，３））を作成する。
　手順２－２：値と位置の組で大小関係を評価しながらソートして、（（Ａｌｉｃｅ，１），（Ｂｏｂ，０），（Ｂｏｂ，３），（Ｃａｔｈｙ，２））を得る。
　手順２－３：同じ値毎にＡ写像内の位置をまとめるとスペクトル分解Ａｌｉｃｅ：（１）＋Ｂｏｂ：（０，３）＋Ｃａｔｈｙ：（２）が完成する。
　　≪Ａ写像の分類≫
　Ａ写像は、結合性、検索性、集合を表しているかどうか、簡単に逆元が求まるか、という４つの指標で分類することができる。これらの分類を踏まえておくことは、これ以降の説明の理解に役立つため、ここで述べておく。
　・結合性
　自然数を要素とするＡ写像はインデックス演算子の両側におくことができる。そうでないＡ写像はインデックス演算子の左側にしかおくことができない。
　・検索性
　要素が昇順に並ぶＡ写像はバイセクションサーチを用いて特定の要素があるかどうか、ある場合はどこにあるかを効率的に検索することができる。このようなＡ写像を昇順配列と呼ぶ。要素がユニークかつ昇順であるＡ写像はある値で検索してマッチするものが存在する場合、それがただ一つになる。このようなＡ写像をユニーク昇順配列と呼ぶ。
　・集合を表しているかどうか
　Ａ写像の要素に重複がなければそれは集合を表していると見なすことができる。ただし、本明細書では要素が自然数であることも前提に加える。本明細書では、集合は結果列であり自然数（レコード番号）を要素とするＡ写像であるためである。
　・簡単に逆元が求まるか
　自然数を要素とするＡ写像でそのサイズをＮとするとき、そのＡ写像に０～Ｎ－１の値を持つ要素がすべて含まれる場合、インデックス演算子に関する逆元を簡単に求めることができる。これを対称配列と呼ぶ。対称配列Ｐの定義を以下に示す。
　ｉ，ｊ∈０，１，・・・，Ｎ－１；ｉ≠ｊ⇒Ｐ（Ｎ） （Ｎ）［ｉ］≠Ｐ（Ｎ） （Ｎ）［ｊ］
　対称配列はインデックス演算子に関して群を作る。したがって、単位元と逆元が存在する。Ｐの逆元は仮想表形式データのセルからソース表形式データのセルを特定する際に使用される。
　単位元：Ｅ＝（０，１，・・・，Ｎ－１）
　逆元：Ｐ［ｉ］＝ｊ⇒Ｐ－１［ｊ］＝ｉ
　＜Ｄ５Ａ＞
　Ｒは表形式データのレコード数、Ｋはカラムの中に含まれる値の種類を指すものとする。このとき、表形式データとは、上から順に０～Ｒ－１の番号で識別されるＲ個のレコードと、左から順に番号又は名前で識別される１～複数のカラムとを持ち、１つのレコードと１つのカラムとで１つの値が定まり、カラム毎にそのカラムで保持されるデータのデータ型（例えば、整数、浮動小数点、文字列等）が１つに定まっているものをいう。また、インデックスが成立しているとは、対象カラムのソート・検索・集計結果のサイズＷがわかり、ｉ∈０，１，・・・，Ｗ－１を指定するとおよそＯ（ｌｏｇ（Ｒ））以下の時間でソート・検索・集計結果のｉ行目を読み出せる状態になっていることをいう。
　以下では、まずＤ５Ａの内部構造について説明し、次に値を取り出す方法、次にＤ５Ａインデックスについて関連事項を交えながら説明する。
　　≪Ｄ５Ａの内部構造≫
　図４を参照しながらＤ５Ａの内部構造を説明する。図４は、カラムＣ（４）＝（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）が含まれるＣＳＶ（Comma Separated Values）形式の表形式データとそのＤ５Ａフォーマットを示している。
　Ｄ５Ａは、同じ構造をしたＤ５ＡのカラムであるＤ５Ａカラムが集まった構造をしている。各Ｄ５Ａカラムは、以下に述べる２つの構造を並置したものである。
　第１の構造はカラムの値の取得のための構造であり、図４中の破線で囲まれた部分である。この構造は、（ａ）Ａ写像であるカラムをそのまま格納するか、（ｂ）カラムをＳＮ分解して得たＳＶＬ、ＮＮＣを格納するか、（ｃ）その両方を格納するか、のいずれかで構成される。そのまま格納した（ａ）の場合は値の読み出しのパフォーマンスが向上するが、ＮＮＣを使うアルゴリズムが使えなくなる。ＳＶＬ、ＮＮＣを格納する（ｂ）の場合はＮＮＣを使うアルゴリズムが使えるが、値の読み出しのパフォーマンスが低下する。その両方を格納する（ｃ）の場合はＤ５Ａファイルのサイズが大きくなる。本実施形態では（ｂ）のケースで説明を行う。
　第２の構造はＤ５Ａインデックスのための構造であり、図４中の一点鎖線で囲まれた部分である。この構造はＳＶＬ、ＡＣＭ、ＩＮＶから成り、転置構造体と呼ばれる。転置構造体は、上述したＤ５Ａカラムのスペクトル分解をＡ写像の形に書き換えたものである。なお、転置構造体の詳細については後述する。
　転置構造体（つまり、第２の構造）が得られれば上記の第１の構造と合わせてＤ５Ａカラムとなり、Ｄ５Ａカラムを集めるとＤ５Ａとなる。
　　≪カラムの値を取得するための構造≫
　カラムの値を取得するための構造は、カラムＣ（Ｒ）をＳＮ分解して作成することができる。例えば、図４に示す例の場合、Ｃ（４）＝（Ｂｏｂ，Ａｌｉｃｅ，Ｃａｔｈｙ，Ｂｏｂ）＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）・（１，０，２，１）となる。したがって、ＳＶＬ（３）＝（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）、ＮＮＣ（４） （３）＝（１，０，２，１）となる。
　一方で、ＳＶＬとＮＮＣを使ってカラムは以下の式で得られる。
　Ｃ（Ｒ）＝ＳＶＬ（Ｋ）・ＮＮＣ（Ｒ） （Ｋ）　　　　式（４）
　したがって、カラムのｉ行目は以下の式で得られる。
　ｖａｌｕｅ＝Ｃ（Ｒ）［ｉ］＝ＳＶＬ（Ｋ）・ＮＮＣ（Ｒ） （Ｋ）［ｉ］　　　　式（５）
　例えば、図４に示す例の場合、カラムの１行目は（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）・（１，０，２，１）［１］＝Ａｌｉｃｅとなる。
　また、ＳＶＬからも以下の情報１～情報４が得られる。
　情報１：カラム内の値の種類数ＫがＳＶＬ（Ｋ）からわかる。例えば、図４に示す例の場合、Ｋは３となる。
　情報２：小さい方からｉ番目の値をＳＶＬ［ｉ］として読み出せる。
　情報３：ある値ｖがカラム内に存在するかどうかがＳＶＬのバイセクションサーチでわかる。また、その値ｖが存在するとき、ｖが何番目の値であるかもわかる。
　情報４：ＳＶＬが集計の次元となる。なお、集計の次元を作るためには従来はソートを行う必要があった。
　　≪転置構造体≫
　次に、Ｄ５Ａインデックスのための構造である転置構造体の作成方法について説明する。カラムをスペクトル分解するとソート・検索・集計を高速に行えることを述べたが、スペクトル分解には２つの扱いにくい点がある。１つ目は、Ａ写像でできていないため、インデックス演算子を用いてアクセスすることができない点（第１の問題点）である。２つ目は、ソート結果列のｉ番目を取得しようとすると、ｗ０，ｗ１，・・・を加算しながらｉ番目を探す必要がある点（第２の問題点）である。スペクトル分解を３つのＡ写像に変換したものが転置構造体であり、この２点を解決する。以下、その定義と作成方法を説明する。
　・転置構造体の定義とスペクトル分解からの作成方法
　転置構造体の定義を以下に示す。
Figure JPOXMLDOC01-appb-M000002
 　ここで、ＳＶＬ（Ｋ）、ＡＣＭ（Ｋ） （Ｒ＋１）、ＩＮＶ（Ｒ） （Ｒ）はそれぞれ以下の手順３－１～手順３－３で得られる
　手順３－１：ＳＶＬ（Ｋ）は、式（３）のスペクトル分解の値部分であるλ０，λ１，・・・，λＫ－１をそのまま並べてＡ写像にしたものである。また、式（４）で得られるＳＶＬ（Ｋ）と同じである。
　手順３－２：ＡＣＭ（Ｋ） （Ｒ＋１）は、
Figure JPOXMLDOC01-appb-M000003
 であり、式（３）の値λｉの出現回数ｗｉを累計数化してＡ写像にしたものである。このステップにはＯ（Ｋ）の時間が掛かる。
　手順３－３：ＩＮＶ（Ｒ） （Ｒ）は、
Figure JPOXMLDOC01-appb-M000004
 であり、式（３）の
Figure JPOXMLDOC01-appb-M000005
 を連結してＡ写像にしたものである。ここで、ｘｉ，ｊはλｉが出現するレコード番号のうち上からｊ番目のレコード番号である。
Figure JPOXMLDOC01-appb-M000006
 がλ０＜λ１＜・・・＜λＫ－１に対応するレコード番号であることからＩＮＶは転置レコード番号の配列になる。
　例えば、図４に示す例の場合、転置構造体は＜（Ａｌｉｃｅ，Ｂｏｂ，Ｃａｔｈｙ）：（１，３，４），（１，０，３，２）＞となる。
　スペクトル分解は、Ａ写像でなく、ソート結果列のｉ番目を取得しようとするとｗｉの加算操作が必要であった。スペクトル分解から導出された転置構造体は３つのＡ写像からなる構造体で第１の問題点を解決でき、ＩＮＶ［ｉ］でソート結果列のｉ番目を取得できるため第２の問題点も解決できる。
　・転置構造体からスペクトル分解を得る方法
　以下の方法でＤ５Ａ内の転置構造体からスペクトル分解を得ることができる。
　まず、式（３）のスペクトル分解のうち、λｉはλｉ＝ＳＶＬ（Ｋ）［ｉ］で得られる。また、予めＡＣＭ［－１］≡０と決めておくと、
Figure JPOXMLDOC01-appb-M000007
 は以下で得られる。
Figure JPOXMLDOC01-appb-M000008
 　上記の２つからスペクトル分解の第ｉ項は以下で求まることになる。
Figure JPOXMLDOC01-appb-M000009
 　例えば、図４に示す例の場合、スペクトル分解の第１項は以下で求まる。
Figure JPOXMLDOC01-appb-M000010
 　・転置構造体から得られる情報
　転置構造体を使うと、ＳＶＬから得られる情報（上記の情報１～情報４）に加えて、以下の情報５～情報８も得られる。
　情報５：小さい方からｉ番目の値の出現回数が以下でわかる。
　ｃｏｕｎｔ＝ＡＣＭ（Ｋ）［ｉ］－ＡＣＭ（Ｋ）［ｉ－１］　　　　式（８）
　例えば、図４に示す例の場合、小さい方から１番目の値の出現回数は、ＡＣＭ（Ｋ）［１］－ＡＣＭ（Ｋ）［０］＝３－１＝２となる。
　情報６：ソート結果のｉ番目のレコード番号は以下で読み出せる。
　ソート結果のｉ番目のレコード番号＝ＩＮＶ［ｉ］　　　　式（９）
　例えば、図４に示す例の場合、ソート結果の１番目のレコード番号は、ＩＮＶ［１］＝０（Ｂｏｂ）として読み出せる。
　情報７：小さい方からｉ番目の値を持つレコード番号を以下の配列として読み出すことができる。
　（ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ－１］］，・・・，ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ］－１］）
　例えば、図４に示す例の場合、小さい方から１番目の値（Ｂｏｂ）を持つレコード番号は、（ＩＮＶ［１］，・・・，ＩＮＶ［２］）＝（０，３）として読み出せる。
　情報８：値ｖ０～ｖ１を持つレコード番号は以下で読み出せる。
　ｉ０をｖ０≦ＳＶＬ［ｉ０］を満たす最小のｉ０、ｉ１をＳＶＬ［ｉ１］≦ｉ１を満たす最大のｉ１として、（ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ０－１］］，・・・，ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ１］－１］）　　　　式（１０）
　例えば、図４に示す例の場合、値Ｂｏｂ～Ｃａｔｈｙを持つレコード番号はｉ０＝１、ｉ１＝２であるため、（ＩＮＶ［ＡＣＭ［１－１］］，・・・，ＩＮＶ［ＡＣＭ［２］－１］）＝（ＩＮＶ［１］，・・・，ＩＮＶ［４－１］）＝（０，３，２）として読み出せる。
　・転置構造体でインデックスを作成できること
　上述したように、インデックスの成立要件は、ソート・検索・集計結果のサイズＷがわかり、ｉ∈０，１，・・・，Ｗ－１を指定するとおよそＯ（ｌｏｇ（Ｒ））以下でソート・検索・集計結果のｉ行目を読み出せることである。以下、転置構造体でインデックスを作成できることを確かめる。
　　（ソート）
　ソート結果のサイズはＲであることがわかる。ソート結果のｉ番目の要素は式（９）を使いＯ（１）で読み出せる。したがって、転置構造体はソートについてインデックスを作成するための要件を満たす。
　　（検索）
　式（１０）の場合について説明する。検索結果のサイズはＡＣＭ（Ｋ）［ｉ１］－ＡＣＭ（Ｋ）［ｉ０－１］であるとわかる。例えば、図４に示す例の場合、値Ｂｏｂ～Ｃａｔｈｙを持つレコード番号はｉ０＝１、ｉ１＝２であるため、ＡＣＭ（Ｋ）［２］－ＡＣＭ（Ｋ）［１－１］＝４－１＝３であるとわかる。
　検索結果のｉ番目の要素は、（ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ０－１］］，・・・，ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ１］－１］）［ｉ］によりＯ（１）で読み出せる。例えば、図４に示す例の場合、値Ｂｏｂ～Ｃａｔｈｙで検索するときｉ０＝１、ｉ１＝２であるため、（ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［１－１］］，・・・，ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［２］－１］）［ｉ］＝（０，３，２）［ｉ］で読み出せる。
　したがって、転置構造体は検索についてインデックスを作成するための要件を満たす。
　　（集計）
　集計結果のサイズは上記の情報１からＫであることがわかる。集計結果のｉ番目の値は上記の情報２で与えられ、Ｏ（１）で得られる。集計結果のｉ番目の値の出現回数は式（８）で与えられ、Ｏ（１）で得られる。したがって、転置構造体は集計についてインデックスを作成するための要件を満たす。
　例えば、図４に示す例の場合でｉ＝１のとき、集計結果のサイズは３、集計結果の１番目の値はＢｏｂ、集計結果の１番目の値の出現回数はＡＣＭ［１］－ＡＣＭ［１－１］＝３－１＝２であるとわかる。
　上記により、転置構造体を使ってソート・検索・集計を高速化するＤ５Ａインデックスが作成できるといえる。
　・Ｄ５Ａインデックスによるソート・検索・集計の結果の保持がわずかな記憶領域済むこと
　　（ソート結果）
　ソート結果は既にＩＮＶに保持されており、新たな記憶領域を必要としない。
　　（検索結果）
　式（１０）の場合について説明する。検索結果は配列（ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ０－１］］，・・・，ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ１］－１］）で与えられている。そのうち、ＩＮＶ、ＡＣＭは既に作成されており、検索結果を保持するために必要とする記憶領域はヒット件数とは無関係にｉ０，ｉ１の格納領域だけである。
　　（集計結果）
　集計結果のｉ番目の値は上記の情報２で与えられ、新たな記憶領域を必要としない。集計結果のｉ番目の値の出現回数は式（８）で与えられ、新たな記憶領域を必要としない。
　以上のように、Ｄ５Ａは仮想表形式データに値を、仮想インデックスにインデックスを供給する役目を持つ。カラムをＳＮ分解して得られるＳＶＬとＮＮＣを使うと、値を供給するだけでなく、上記の情報１～情報４の４種類の情報を得ることができる。また、転置構造体を使ってＤ５Ａインデックスができる（つまり、ソート・検索・集計で転置構造体をインデックスのためのデータ構造として利用することができる）ことを示した。Ｄ５Ａインデックスはソート・検索・集計を高速化するだけでなく、ソート・検索・集計の結果をわずかな記憶領域だけで保持することができる。
　＜仮想表形式データ＞
　例えば、ＲＤＢ（Relational Database）でＪＯＩＮやＵＮＩＯＮを行うとソース表形式データを読み出し、それらを比較し、書き出すデータを作り、その格納位置を決め、新たに確保した記憶領域上に書き出す。すると、時間と記憶領域とを必要とする。それがアーカイブの表形式データを活用しようとする際の第１ステップの問題である。この問題は、新たに生成される表形式データが巨大であればあるほど深刻になる。その生成に長い時間が掛かり、大きい記憶領域を必要とするためである。しかも、往々にして使用されるのは生成された表形式データのわずかな部分である。
　仮想表形式データは必要な部分を必要になったときに作り出す仕組みで、上記の問題を解決する。つまり、仮想表形式データではあるセルを表示する必要が生じた場合にその時点でそのセルに対応するソース表形式データのセルを参照してそれを表示する。しかし、そのためには仮想表形式データのセルと１つ以上のソース表形式データのセルとの間の対応を定める写像が予め定義されている必要がある。その写像は仮想表形式データから複数のソース表形式データへの写像とすることもできるし、その逆に複数のソース表形式データから仮想表形式データへの写像とすることもでき、どちらも本質的には同じである。しかし、前者は写像の宛先がどのソース表形式データのどのセルという２つの情報の組になるのに対して、後者は仮想表形式データのどのセルという１つの情報だけで済み定義しやすい。そこで、以下では、後者で説明を行う。なお、その両者とも逆写像を必要とする。前者は仮想インデックスが逆写像を必要とし、後者は仮想表形式データがソース表形式データを参照して値を取得する際に必要となる。
　後者の各ソース表形式データのどのセルを仮想表形式データ上のどのセルに対応させるか、という写像を割り付け写像と呼ぶ。ただし、実際の割り付け写像はソース表形式データ上のカラムである各ソースカラムから仮想表形式データ上のカラムである仮想カラムへの写像を定義するものとする。その各ソースカラムは１つ以上の区間に分割され、区間毎に対応表又はルールによりその区間上のセルが仮想カラム上のセルに対応付けられる。その区間毎の対応付けを区間写像と呼ぶ。割り付け写像はすべての区間写像を合わせたものである。
　　≪割り付け写像の作成手順≫
　図５を参照しながら割り付け写像の作成手順を説明する。なお、以下、ｒｓはソース表形式データ上のレコード番号、ｒｖは仮想表形式データ上のレコード番号を指すものとする。
　仮想表形式データ上のカラムである仮想カラムは１つ以上のソースカラムからの割り付け写像で構成される。図５に示す例では、仮想カラムはソースカラム０とソースカラム１から割り付けられている。
　図５の左下のソースカラム１を持つブランクＤ５Ａは、仮想カラム生成時にプログラム的に自動で生成されるＤ５Ａである。ブランクＤ５Ａは仮想カラム上の割り付けを受けていないセルにブランク値を供給し、仮想カラムが後述する全単射の条件を満たすようにするためのものである。全単射の条件を満たしていると、仮想表形式データには仮想インデックスが自動的に備わる。一方、仮想表形式データをソート・検索・集計する必要が無い場合もある。例えば、ＵＮＩＯＮやＪＯＩＮした結果全体をそのまま利用したい場合である。その場合はもちろん全単射の条件を考慮せず仮想表形式データを定義して使うことができる。
　各ソースカラムは１つ以上のソース区間に分割される。図５に示す例では、ソースカラム０は区間１及び区間２に分割されている。その各ソース区間から仮想カラムへの写像（つまり、区間写像）は２種類ある。１つ目は、要素が自然数でかつ重複がないＡ写像Ｍで定義される列挙型写像である。２つ目は、１次関数で定義される１次関数型写像である。前者の列挙型写像はあらゆる割り付け写像を定義できる一方で多くの記憶領域を消費する。後者の１次関数型写像は列挙型写像のＭを１次関数で置き換えた写像であり、記憶領域をわずかしか消費せず巨大な区間写像でも定義できるが規則性のある割り付けにしか対応できない。すべてのソース区間で区間写像が定義されると、割り付け写像が完成する。
　上記いずれの区間写像もそれが定義されると、その逆写像及び逆写像の存在条件も確定する。仮想表形式データを表示する際は、まず仮想カラムのレコード番号から上記の逆写像が存在するソース区間を特定し、次にその区間写像の逆写像を使ってソースカラム上のレコード番号を特定し、そしてそのレコード番号から値を取得して表示することになる。
　以下では、列挙型写像による区間写像と、１次関数型写像による区間写像とを説明した後、再び図５を参照して仮想表形式データの表示方法を説明する。
　　≪列挙型写像による区間写像及びその逆写像≫
　図６は列挙型写像による割り付けの例を示している。図６において、Ｒｓはソースカラムのサイズ、ｒｓはソースカラムのレコード番号、Ｒｖは仮想カラムのサイズ、ｒｖは仮想カラムのレコード番号、Ｑはソースカラム上の区間、ｑは区間Ｑの開始位置、ｕは区間Ｑの長さ、Ｖは区間Ｑに対応する仮想カラム上の区間、ｖは区間Ｖの開始位置、ｗは区間Ｖの長さを表す。
　このとき、列挙型写像による区間写像Ｆ：Ｑ→Ｖは以下で表される。
　ｒｖ＝Ｍ（ｕ） （Ｒｖ）［ｒｓ－ｑ］　　　　式（１１）
　また、その逆写像Ｆ－１：Ｖ→Ｑは以下で表される。
　Ｍ（ｕ） （Ｒｖ）＝Ｌ（ｕ） （Ｒｖ）・Ｐ（ｕ） （ｕ）；
　Ｌ（ｕ） （Ｒｖ）［ｊ］＝ｒｖ；
　ｒｓ＝Ｐ－１ （ｕ） （ｕ）［ｊ］＋ｑ　　　　式（１２）
　・列挙型写像
　まず、列挙型写像による区間写像を定義する式（１１）を説明する。図６において、ソースカラム及び仮想カラムの横に記載されている番号はレコード番号である。Ｍはソース区間の先頭から順に対応する仮想カラム上のレコード番号を書き出すことで定義することができる。図６に示す例では（７，５，９，１）となる。ここで、ソース区間Ｑの開始位置ｑは２である。
　ソース区間（区間Ｑ）はｒｓ＝２から始まりｒｓ＝５で終わる。式（１１）に各ｒｓを適用すると以下となる。
　ｒｓ＝２のとき、ｒｖ＝（７，５，９，１）［２－２］＝７
　ｒｓ＝３のとき、ｒｖ＝（７，５，９，１）［３－２］＝５
　ｒｓ＝４のとき、ｒｖ＝（７，５，９，１）［４－２］＝９
　ｒｓ＝５のとき、ｒｖ＝（７，５，９，１）［５－２］＝１
　・列挙型写像の逆写像
　次に、列挙型写像の逆写像を定義する式（１２）を説明する。
　Ｍは重複のない自然数を要素とするＡ写像であり、ＬＰ分解を行うことができる。式（１２）の最上段はそのＬＰ分解を示している。ＬＰ分解によってＬ＝（１，５，７，９）、Ｐ＝（２，１，３，０）を得る。Ｌはユニーク昇順配列であり、要素の有無、要素がある場合はその出現位置をバイセクションサーチで求めることができる。Ｐは対称配列であり、逆元Ｐ－１＝（３，１，０，２）を持つ。
　式（１２）の中段はｒｖがＬ中の何番目に出現するかを求める方法を示しており、ｊはその出現位置である。なお、ｊが求まらない場合、ｒｖはソース区間Ｑからの写像を受け入れていないことを意味し、逆写像は存在しない。
　式（１２）の下段はＰ－１＝（３，１，０，２）とｑ＝２と上記のｊを用いてｒｓが求まることを意味している。
　以上を踏まえ、ｒｖ＝１，５，７，９の場合について、ｒｓを計算してみる。
　ｒｖ＝１のとき、（１，５，７，９）［ｊ］＝１からｊ＝０；ｒｓ＝（３，１，０，２）［ｊ］＋２＝５
　ｒｖ＝５のとき、（１，５，７，９）［ｊ］＝５からｊ＝１；ｒｓ＝（３，１，０，２）［ｊ］＋２＝３
　ｒｖ＝７のとき、（１，５，７，９）［ｊ］＝７からｊ＝２；ｒｓ＝（３，１，０，２）［ｊ］＋２＝２
　ｒｖ＝９のとき、（１，５，７，９）［ｊ］＝９からｊ＝３；ｒｓ＝（３，１，０，２）［ｊ］＋２＝４
　　≪１次関数型写像による区間写像及びその逆写像≫
　図７は１次関数型写像による割り付けの例を示している。図７において、Ｒｓはソースカラムのサイズ、ｒｓはソースカラムのレコード番号、Ｒｖは仮想カラムのサイズ、ｒｖは仮想カラムのレコード番号、Ｑはソースカラム上の区間、ｑは区間Ｑの開始位置、ｕは区間Ｑの長さ、Ｖは区間Ｑに対応する仮想カラム上の区間、ｖは区間Ｖの開始位置、ｗは区間Ｖの長さを表す。
　このとき、１次関数型写像による区間写像Ｆ：Ｑ→Ｖは以下で表される。
　ｒｖ＝ａ×ｒｓ＋ｂ；ａ，ｂは整数、ａ≠０　　　　式（１３）
　また、その逆写像Ｆ－１：Ｖ→Ｑは以下で表される。
　ｒｓ＝（ｒｖ－ｂ）／ａ　　　　式（１４）
　ただし、ｖ≦ｒｖ＜ｖ＋ｗでないとき、ｒｓが整数にならないとき、ｒｖはＦの値域ではない。
　・１次関数型写像
　まず、１次関数型写像を定義する式（１３）を説明する．図７において、ソースカラム及び仮想カラムの横に記載されている番号はレコード番号である。ａは仮想カラム上のインターバルであり、図７に示す例ではａ＝３、ｂ＝－５となる。
　ソース区間（区間Ｑ）はｒｓ＝２から始まりｒｓ＝５で終わる。式（１３）に各ｒｓを適用すると以下となる。
　ｒｓ＝２のとき、ｒｖ＝３×ｒｓ－５＝１
　ｒｓ＝３のとき、ｒｖ＝３×ｒｓ－５＝４
　ｒｓ＝４のとき、ｒｖ＝３×ｒｓ－５＝７
　ｒｓ＝５のとき、ｒｖ＝３×ｒｓ－５＝１０
　・１次関数型写像の逆写像
　次に、１次関数型写像の逆写像を定義する式（１４）を説明する．上述したように、ａ＝３、ｂ＝－５である。
　まず、ｖ≦ｒｖ＜ｖ＋ｗであることを確かめる必要がある．ｖ＝１、ｗ＝１０であるため、１≦ｒｖ＜１＋１０でなければならない。その条件を満たす場合、式（１４）の上段を使ってｒｓを求める。このとき、式（１４）の下段にあるように、ｒｓが整数でない場合、ｒｖはソース区間Ｑからの写像を受け入れていないことを意味し、逆写像は存在しない。
　ｒｖ＝１のとき、ｒｓ＝（１－（－５））／３＝２
　ｒｖ＝４のとき、ｒｓ＝（４－（－５））／３＝３
　ｒｖ＝７のとき、ｒｓ＝（７－（－５））／３＝４
　ｒｖ＝１０のとき、ｒｓ＝（１０－（－５））／３＝５
　　≪仮想表形式データの表示≫
　再び図５を参照して仮想表形式データの表示方法を説明する。ソースカラム０のソース区間１は１次関数型写像による区間写像、ソースカラム０のソース区間２は列挙型写像による区間写像、ソースカラム１のソース区間１は１次関数型写像による区間写像としている。それぞれの区間写像の定義は以下になる。
　ソースカラム０のソース区間１における区間写像は、式（１３）により、Ｆ：ｒｖ＝ｒｓ×２＋１と定義される。
　ソースカラム０のソース区間２における区間写像は、式（１１）により、Ｆ：ｒｖ＝（２，７，０）［ｒｓ－３］と定義される。以下のようにｒｓ＝３，４，５を代入して正しいことが確認できる。
　ｒｓ＝３のときｒｖ＝（２，７，０）［３－３］＝２
　ｒｓ＝４のときｒｖ＝（２，７，０）［４－３］＝７
　ｒｓ＝５のときｒｖ＝（２，７，０）［５－３］＝０
　ブランクＤ５Ａのソースカラム１のソース区間１における区間写像は、式（１３）により、Ｆ：ｒｖ＝ｒｓ×２＋４と定義される。
　上記の各区間写像Ｆが定義されるとその逆写像Ｆ－１は以下のように自動的に定まる。
　ソースカラム０のソース区間１における逆写像は、式（１４）により、Ｆ－１：ｒｓ＝（ｒｖ－１）／２となる。
　ソースカラム０のソース区間２における逆写像は、式（１２）により、Ｆ－１：ｒｓ＝（２，０，１）［ｊ］＋３；ｒｖ＝（０，２，７）［ｊ］となる。まず、ｒｖ＝０のとき（０，２，７）をバイセクションサーチしてｒｖの格納位置ｊ＝０がわかり、ｒｓ＝（２，０，１）［０］＋３＝５となる。同様に、ｒｖ＝２のとき（０，２，７）をバイセクションサーチしてｒｖの格納位置ｊ＝１がわかり、ｒｓ＝（２，０，１）［１］＋３＝３となる。同様に、ｒｖ＝７のとき（０，２，７）をバイセクションサーチしてｒｖの格納位置ｊ＝２がわかり、ｒｓ＝（２，０，１）［２］＋３＝４となる。
　ブランクＤ５Ａのソースカラム１のソース区間１における逆写像は、式（１３）により、Ｆ－１：ｒｓ＝（ｒｖ－４）／２となる。
　上記をまとめると、ｒｖ＝０，１，２，３，５，７のときソースカラム０でｒｓ＝５，０，３，１，２，４、ｒｖ＝４，６のときソースカラム１でｒｓ＝０，１を得る。
　　≪仮想表形式データの構成法≫
　上記で説明した機能を実現するため、仮想表形式データは以下の情報で構成される。
　１．レコード数
　２．仮想カラムの名前及びデータ型
　３．１つ以上のソース表形式データのＵＲＬ又はパス
　４．上記のソース表形式データ中のソースカラムとソース区間の定義
　５．ソース区間毎の区間写像とその逆写像の定義
　上記のうち５以外は大きな記憶領域を必要としない。また、上記の５に大きな記憶領域を必要とするのは、ソース区間が大きくかつ列挙型写像のときに限られる。このため、仮想表形式データは多くの場合、コンパクトに構成できる。
　　≪異なる区間からの割り付けの衝突検出≫
　ここで、割り付け写像による割り付け先が衝突していないかを調べる方法について説明する。以下では、２つの割り付け写像をＦ０：Ｑ０→Ｖ０、Ｆ１：Ｑ１→Ｖ１とする。
　まず、自明なケースとして以下の（条件１－１）～（条件１－３）のいずれかを満たす場合、２つの割り付け写像Ｆ０、Ｆ１は衝突しない。
　（条件１－１）Ｖ０とＶ１が同一の仮想カラム上にない場合
　（条件１－２）ｖ０＋ｗ０－１＜ｖ１である場合
　（条件１－３）ｖ１＋ｗ１－１＜ｖ０である場合
　なお、ｖ０はＶ０の開始位置、ｗ０はＶ０の長さ、ｖ１はＶ１の開始位置、ｗ１はＶ１の長さである。
　上記の自明なケースに該当しない場合、以下の（ケース１）～（ケース３）により２つの割り付け写像Ｆ０、Ｆ１の衝突有無を調べることができる。
　（ケース１）Ｆ０、Ｆ１がいずれも列挙型写像である場合
　Ｌ０＝（ｖ０，・・・，ｖ０＋ｗ０－１）、Ｌ１＝（ｖ１，・・・，ｖ１＋ｗ１－１）として、Ｌ０とＬ１の共通範囲を新たにＬ０，Ｌ１とする。なお、ｗ０はＶ０の長さ、ｗ１はＶ１の長さである。
　そして、ｉ＝０，ｊ＝０に対して、以下の手順４－１～手順４－３を実行する。
　手順４－１：Ｌ０［ｉ］＝Ｌ１［ｊ］であれば「衝突あり」として終了する。
　手順４－２：Ｌ０［ｉ］＜Ｌ１［ｊ］であれば、ｉ←ｉ＋１として手順４－１に戻る。ただし、ｉ←ｉ＋１とした結果、ｉがＬ０の要素を表すインデックスの最大値を超える場合は「衝突なし」として終了する。
　手順４－３：Ｌ０［ｉ］＞Ｌ１［ｊ］であれば、ｊ←ｊ＋１として手順４－１に戻る。ただし、ｊ←ｊ＋１とした結果、ｊがＬ１の要素を表すインデックスの最大値を超える場合は「衝突なし」として終了する。
　（ケース２）Ｆ０、Ｆ１がいずれも１次関数型写像である場合
　Ｖ０とＶ１の共通部分を選び出し、Ｆ０、Ｆ１を、当該共通部分を値域とする以下の式でそれぞれ記述し直す。その際、ａ０、ａ１が正になるように調整する。
　ｙ０＝ａ０×ｘ０＋ｂ０；ｘ０＝０，１，２，・・・，Ｎ０－１
　ｙ１＝ａ１×ｘ１＋ｂ１；ｘ１＝０，１，２，・・・，Ｎ１－１
　ここで、ａ０，ａ１は１以上の整数、ｂ０，ｂ１は整数である。
　そして、ｘ０＝０、ｘ１＝０として、以下の手順５－１～手順５－３を実行する。
　手順５－１：ｙ０＝ｙ１であれば「衝突あり」として終了する。
　手順５－２：ｙ０＜ｙ１であれば、ｘ０←ｘ０＋ＭａｘＩｎｔ（１，（ｙ１－ｙ０）ｄｉｖ　ａ０）として手順５－１に戻る。ただし、ｘ０←ｘ０＋ＭａｘＩｎｔ（１，（ｙ１－ｙ０）ｄｉｖ　ａ０）とした結果、ｘ０＞ＭｉｎＩｎｔ（Ｎ０－１，ＬＣＭ（ａ０，ａ１）ｄｉｖ　ａ０）である場合は「衝突なし」として終了する。
　手順５－３：ｙ０＞ｙ１であれば、ｘ１←ｘ１＋ＭａｘＩｎｔ（１，（ｙ０－ｙ１）ｄｉｖ　ａ１）として手順５－１に戻る。ただし、ｘ１←ｘ１＋ＭａｘＩｎｔ（１，（ｙ０－ｙ１）ｄｉｖ　ａ１）とした結果、ｘ１＞ＭｉｎＩｎｔ（Ｎ１－１，ＬＣＭ（ａ０，ａ１）ｄｉｖ　ａ１）である場合は「衝突なし」として終了する。
　ここで、ＭａｘＩｎｔは最大の整数を選ぶ関数、ＭｉｎＩｎｔは最小の整数を選ぶ関数、ｄｉｖは整数の割り算（余りは切り捨て）、ＬＣＭは最小公倍数を返す関数を表す。
　（ケース３）Ｆ０、Ｆ１のいずれか一方が列挙型写像、他方が１次関数型写像である場合
　以下、Ｆ０を１次関数型写像、Ｆ１を列挙型写像であるものとする。Ｖ０とＶ１の共通部分を選び出し、Ｆ０、Ｆ１を、当該共通部分を値域とする以下の式でそれぞれ記述し直す。その際、ａ０が正になるように調整する。
　ｙ０（ｎ）＝ａ０×ｎ＋ｂ０；ｘ０＝０，１，２，・・・，Ｎ－１
　ｙ１（ｍ）＝（ｖ１，・・・，ｖ１＋ｗ１－１）［ｍ］
　ここで、ａ０＞０である。また、（ｖ１，・・・，ｖ１＋ｗ１－１）はサイズＭの昇順配列である。
　そして、ｎ＝０、ｍ＝０として、以下の手順６－１～手順６－３を実行する。
　手順６－１：ｙ０（ｎ）＝ｙ１（ｍ）であれば「衝突あり」として終了する。
　手順６－２：ｙ０（ｎ）＞ｙ１（ｍ）であれば、ｍ←ｍ＋１として手順６－１に戻る。ただし、ｍ←ｍ＋１とした結果、ｍ＝Ｍである場合は「衝突なし」として終了する。
　手順６－３：ｙ０（ｎ）＜ｙ１（ｍ）であれば、ｎ←（ｙ１（ｍ）－ｙ０（ｎ））ｄｉｖ　ａ０として手順６－１に戻る。ただし、ｎ←（ｙ１（ｍ）－ｙ０（ｎ））ｄｉｖ　ａ０とした結果、ｎ≧Ｎである場合は「衝突なし」として終了する。
　＜仮想インデックス＞
　これまでにＤ５Ａから直接又は間接的に値を継承した仮想表形式データを作成する方法を説明した。以下では、Ｄ５Ａ上の転置構造体を直接又は間接的に継承して仮想表形式データ上に仮想転置構造体が自動的に成立する理由を説明する。仮想転置構造体が成立すると、それをインデックスのためのデータ構造として使う仮想インデックスも自動的に成立する。仮想インデックスは、転置構造体の代わりに仮想転置構造体を使うだけで、アルゴリズムはＤ５Ａインデックスと同じものを使うのでＤ５Ａインデックスと同じ機能と特性を持つ。つまり、カラムのソート・検索・集計を高速化でき、かつ、巨大なソート結果・検索結果・集計結果でもわずかな記憶領域だけで保持できる。
　仮想転置構造体は転置構造体と同様に、仮想ＳＶＬ、仮想ＡＣＭ、仮想ＩＮＶを持つ構造体である。ここで、仮想ＳＶＬ、仮想ＡＣＭ、仮想ＩＮＶは仮想配列である。仮想配列とは、仮想表形式データがそうであるように値を保持せず、サイズＷが予めわかり、ｉ∈０，１，・・・，Ｗ－１を指定するとおよそＯ（ｌｏｇ（Ｒ））以下でｉ番目の要素が取り出せる、配列と同等の機能を持った仕組みのことである。仮想ＳＶＬ、仮想ＡＣＭ、仮想ＩＮＶは、仮想表形式データを定義した割り付け写像が以下の全単射の条件を満たしていれば自動的に成り立つ。
　・全単射の条件
　１．（写像が成り立つこと）ソースカラムのすべてのセルが仮想カラム上のセルに写されていること。
　２．（単射であること）どの仮想カラム上のセルも２つ以上のソースカラムのセルから写されていないこと。
　３．（全射であること）すべての仮想カラム上のセルがソースカラムのセルから写されていること。
　４．（ソースカラムが全単射で作られていること）ソースカラムがＤ５Ａの場合はソースカラムが全単射で作られているといえる。ソースカラムが仮想カラムの場合はソースカラムが上記の１～３を満たして作られていると全単射で作られているといえる。
　以下では、まず複数の転置構造体から仮想転置構造体が構成できることを説明し、その仮想転置構造体を使う仮想インデックスでソート・検索・集計が高速に実行でき、ソート結果・検索結果・集計結果が新たにわずかな記憶領域を確保するだけで保持できることを確かめる。次に仮想転置構造体と転置構造体でも更なる仮想転置構造体が階層的に作れ、それを使う仮想インデックスでもソート・検索・集計が高速に実行でき、ソート結果・検索結果・集計結果が新たにわずかな記憶領域を確保するだけで保持できることを確かめる。最後にスペクトル分解を用いると階層的に作られた仮想転置構造体の動作でも容易に理解できることを確認する。
　　≪仮想転置構造体の構成方法≫
　一例として、ソースカラム＃０：Ｃ０（４）とソースカラム＃１：Ｃ１（４）から定義された仮想カラムＣＶ（８）を図８に示す。Ｃ０（４）とＣ１（４）の要素は区別のため、Ａ０、Ｂ０、Ｃ０、Ｂ１、Ｃ１、Ｄ１とソースカラムの番号を添え字として表示しているが、値としてはＢ０＝Ｂ１、Ｃ０＝Ｃ１である。このとき、ソースカラム＃０からの割り付け先は仮想カラムの５、７、２、３行目であるため、割り付け写像Ｆ０＝（５，７，２，３）である。同様に、ソースカラム＃１からの割り付け先は仮想カラムの４、０、６、１行目であるため、割り付け写像Ｆ１＝（４，０，６，１）である。
　ソースカラム＃０の転置構造体とソースカラム＃１の転置構造体と仮想転置構造体とを図９に示す。ここで、ソースカラム＃０の転置構造体中のＳＶＬ、ＡＣＭ、ＩＮＶをそれぞれＳＶＬ０、ＡＣＭ０、ＩＮＶ０と表記し、ソースカラム＃１の転置構造体中のＳＶＬ、ＡＣＭ、ＩＮＶをそれぞれＳＶＬ１、ＡＣＭ１、ＩＮＶ１と表記する。また、仮想カラムの仮想転置構造体中のＳＶＬ、ＡＣＭ、ＩＮＶをそれぞれＳＶＬＶ、ＡＣＭＶ、ＩＮＶＶと表記する。
　ＩＮＶ０及びＩＮＶ１は共に転置レコード番号を格納した配列であり、ソースカラム上のレコード番号は割り付け写像で仮想カラム上のレコード番号に写されるため、ＩＮＶ０及びＩＮＶ１を読み出す際にはそれぞれＩＮＶ０'及びＩＮＶ１'に読み替える必要がある。ＩＮＶ０'、ＩＮＶ１'は以下の式（１５）で算出できる。
　ＩＮＶ０'＝Ｆ０・ＩＮＶ０＝（５，７，２，３）・（３，０，２，１）＝（３，５，２，７）　　　　式（１５）－１
　ＩＮＶ１'＝Ｆ１・ＩＮＶ１＝（４，０，６，１）・（１，２，０，３）＝（０，６，４，１）　　　　式（１５）－２
　以下、図９を例として、仮想転置構造体の構成方法を仮想配列ＳＶＬＶ、ＡＣＭＶ、ＩＮＶＶの順に説明する。
　・仮想配列ＳＶＬＶの構成方法
　まず、ＳＶＬＶのサイズを求める方法を説明する。予めＳＶＬ０及びＳＶＬ１に共通して出現する値Ｂ、Ｃはソースカラムの順位を加味して大小関係を決めるものと取り決める。つまり、ＳＶＬ０のＢ０はＳＶＬ１のＢ１よりも小さいものと取り決める。すると、各ＳＶＬ間で大小関係のつかない値は存在しなくなり、ＳＶＬＶのサイズは、ＳＶＬ０のサイズ＝３とＳＶＬ１のサイズ３の和である６となり、一意に確定する。
　次に、ＳＶＬＶのｉ番目の要素ＳＶＬＶ［ｉ］を求める方法を説明する。ＳＶＬ０又はＳＶＬ１の中から適当な値ｖを選択する。ただし、このｖはソースカラムの順位を加味して大小関係を決める上記の取り決めに従うものとする。次に、ＳＶＬ０及びＳＶＬ１の中でｖより小さい値の個数の和ｊを求める。もしｊ＜ｉならばｖよりも大きいｖ'を選択し、上記を再び行う。ｊ＞ｉのときも同様に行う（ただし、ｖよりも小さいｖ'を選択する。）。ｊ＝ｉとなったらそのときのｖがＳＶＬＶ［ｉ］である。
　上記のＳＶＬＶ［ｉ］を求める方法は、およそＯ（ｌｏｇ（Ｋ））程度で行える。すると、ＳＶＬＶはサイズがわかり、そのｉ番目の要素をＯ（ｌｏｇ（Ｒ））以下で取り出せるので、仮想配列ＳＶＬＶが存在すると考えてよいことになる。
　ｉ＝０のときの例を示す。最初にｖとしてＳＶＬ１のＢ１を選択してみる。ＳＶＬ０中にｖより小さい値は２個あり、ＳＶＬ１中には０個ある。したがって、ｊ＝２＋０＝２となり、ｉ＝０より大きい。そこで、次に、ｖとしてＳＶＬ０のＡ０を選択してみる。すると、ｊ＝０となり、ｊ＝ｉとなる。このため、ＳＶＬＶ［０］＝Ａ０となる。
　ｉ＝４のときの例を示す。最初にｖとしてＳＶＬ０のＢ０を選択してみる。ＳＶＬ０中にｖより小さい値は１個あり、ＳＶＬ１中には０個ある。したがって、ｊ＝１＋０＝１となり、ｉ＝４より小さい。そこで、次に、ｖとしてＳＶＬ１のＣ１を選択してみる。すると、ｊ＝３＋１＝４となり、ｊ＝ｉとなる。このため、ＳＶＬＶ［４］＝Ｃ１となる。
　上記により、仮想配列ＳＶＬＶ＝（Ａ０，Ｂ０，Ｂ１，Ｃ０，Ｃ１，Ｄ１）を作ることができる。
　・仮想配列ＡＣＭＶの構成方法
　まず、ＡＣＭＶのサイズはＳＶＬＶのサイズとして求まる。
　次に、ＡＣＭＶのｉ番目の要素ＡＣＭＶ［ｉ］を求める方法を説明する。まず、「仮想配列ＳＶＬＶの構成方法」で説明した方法によりｖ＝ＳＶＬＶ［ｉ］であるｖを求める。次に、ＳＶＬ０［ｉ０］≦ｖを満たす最大のｉ０を求める。ｉ０が見つからない場合、ｉ０＝－１とみなす。なお、ＡＣＭ［－１］≡０であることに留意されたい。
　同様に、ＳＶＬ１［ｉ１］≦ｖを満たす最大のｉ１を求める。そして、ＡＣＭＶ［ｉ］は、ＡＣＭＶ［ｉ］＝ＡＣＭ０［ｉ０］＋ＡＣＭ１［ｉ１］として求まる。
　上記のＡＣＭＶ［ｉ］を求める方法は、およそＯ（ｌｏｇ（Ｋ））程度で行える。すると、ＡＣＭＶはサイズがわかり、そのｉ番目の要素をＯ（ｌｏｇ（Ｒ））以下で取り出せるので、仮想配列ＡＣＭＶが存在すると考えてよいことになる。
　ｉ＝３のときの例を示す。最初にｖとしてＳＶＬ１のＢ１を選択してみる。ＳＶＬ０中にｖより小さい値は２個あり、ＳＶＬ１中には０個ある。したがって、ｊ＝２となり、ｉ＝３より小さい。そこで、次に、ｖとしてＳＶＬ０のＣ０を選択してみる。すると、ｊ＝２＋１＝３となり、ＳＶＬＶ［３］＝Ｃ０であることになる。
　次に、ＳＶＬ０［ｉ０］≦ｖを満たす最大のｉ０を求めると、ｉ０＝２が求まる。次に、ＳＶＬ１［ｉ１］≦ｖを満たす最大のｉ１を求めると、ｉ１＝０が求まる。したがって、ＡＣＭＶ［３］は、ＡＣＭＶ［３］＝ＡＣＭ０［２］＋ＡＣＭ１［０］＝４＋２＝６として求まる。
　上記により、仮想配列ＡＣＭＶ＝（１，３，５，６，７，８）を作ることができる。
　・仮想配列ＩＮＶＶの構成方法
　まず、ＩＮＶＶのサイズはＲとわかる。ここで、Ｒはソースカラムのサイズの総和である。
　次に、ＩＮＶＶ［ｉ］を求めるために、ＡＣＭＶ［ｊ－１］≦ｉ≦（ＡＣＭＶ［ｊ］－１）を満たすｊを求める方法を説明する。ｊはＡＣＭＶが定めるＩＮＶＶ上の区間の番号である。
　ＡＣＭＶのサイズをＫＶとする。ＫＶはＡＣＭ０及びＡＣＭ１のサイズの和である。まず、０，１，・・・，ＫＶ－１の中から適当なｊを選択し、「仮想配列ＡＣＭＶの構成方法」で説明した方法により区間ＡＣＭＶ［ｊ－１］～ＡＣＭＶ［ｊ］－１を求める。
　もしｉ＜ＡＣＭＶ［ｊ－１］であれば、ｊをもっと小さい値にして区間を選び直す。一方で、もしｉ＞ＡＣＭＶ［ｊ］－１であれば、ｊをもっと大きい値にして区間を選び直す。これを繰り返してｊを確定し、ｊが確定したらｏｆｆｓｅｔ＝ｉ－ＡＣＭＶ［ｊ－１］を求めておく。
　次に、ｖ＝ＳＶＬＶ［ｊ］を求める。すると、値ｖとそのソースカラムが求まる。そのｖを用いてそのソースカラム上のＳＶＬでＳＶＬ［ｋ］＝ｖとなるｋを求める。これにより、ＩＮＶＶ［ｉ］＝ＩＮＶ'［ＡＣＭ［ｋ－１］＋ｏｆｆｓｅｔ］としてＩＮＶＶ［ｉ］が求まる。ここで、ＩＮＶ'、ＡＣＭは当該ソースカラム上のＩＮＶ'、ＡＣＭである。
　上記のＩＮＶＶ［ｉ］を求める方法は、およそＯ（ｌｏｇ（Ｋ））程度で行える。すると、ＩＮＶＶはサイズがわかり、そのｉ番目の要素を効率良く取り出せるので、仮想配列ＩＮＶＶが存在すると考えてよいことになる。
　ｉ＝４のときの例を示す。最初にｊ＝３を選択してみる。区間の下限はＡＣＭＶ［ｊ－１］＝ＡＣＭＶ［２］＝５、区間の上限はＡＣＭＶ［ｊ］－１＝ＡＣＭＶ［３］－１＝５となり、選んだ区間が大きすぎることがわかる。そこで、ｊ＝２と選択し直してみる。区間の下限はＡＣＭＶ［ｊ－１］＝ＡＣＭＶ［１］＝３、区間の上限はＡＣＭＶ［ｊ］－１＝ＡＣＭＶ［２］－１＝４となる。このため、ｉ＝４はｊ＝２の区間に属することがわかる。ｏｆｆｓｅｔ＝ｉ－ＡＣＭＶ［ｊ－１］＝４－ＡＣＭＶ［１］＝１である。次に、ｖ＝ＳＶＬＶ［ｊ］＝ＳＶＬＶ［２］＝Ｂ１であることがわかる。次に、ソースカラム＃１上のＳＶＬ［ｋ］＝Ｂ１となるｋは０であることがわかる。これにより、ＩＮＶＶ［４］＝ＩＮＶ'［ＡＣＭ［ｋ－１］＋ｏｆｆｓｅｔ］＝ＩＮＶ'［１］＝６を得る。
　上記により、仮想配列ＩＮＶＶ＝（３，５，２，０，６，７，４，１）を作ることができる。
　・仮想インデックスでのソート
　仮想転置構造体を用いた仮想インデックスでソートを行ってみる。図８、図９にはＮＮＣが記載されていないためその代わりに図８のＣｖ（８）を用いる。ソート結果は以下となる。
　Ｃｖ（８）・ＩＮＶＶ＝（Ｂ１，Ｄ１，Ｂ０，Ａ０，Ｃ１，Ｂ０，Ｂ１，Ｃ０）・（３，５，２，０，６，７，４，１）＝（Ａ０，Ｂ０，Ｂ０，Ｂ１，Ｂ１，Ｃ０，Ｃ１，Ｄ１）
　上記の結果より確かにソートされていることが分かる。加えて、ソート結果には同じ「Ｂ」や「Ｃ」であってもＣ０（４）の「Ｂ」や「Ｃ」がＣ１（４）のそれらよりも先に来ることがわかる。これは同じ値のときはカラム番号が小さい方がその値が小さいとの取り決めが反映されたためである。また、ソート結果を保持するために新たな記憶領域を必要とすることがないのはＤ５Ａインデックスと同じである。
　・仮想インデックスでの検索
　仮想転置構造体を用いた仮想インデックスで検索を行ってみる。図８、図９にはＮＮＣが記載されていないためその代わりに図８のＣｖ（８）を用いる。また、検索は「Ｂ」～「Ｃ」の条件で行うものとする。
　式（１０）でｉ０＝１、ｉ１＝４となるため、（ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ０－１］］，・・・，ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ１］－１］）＝（５，２，０，６，７，４）となる。したがって、検索結果は以下となる。
　Ｃｖ（８）・（５，２，０，６，７，４）＝（Ｂ１，Ｄ１，Ｂ０，Ａ０，Ｃ１，Ｂ０，Ｂ１，Ｃ０）・（５，２，０，６，７，４）＝（Ｂ０，Ｂ０，Ｂ１，Ｂ１，Ｃ０，Ｃ１）
　また、検索結果を保持するためにはｉ０、ｉ１を保持するだけでよいためわずかな記憶域しか必要としないことはＤ５Ａインデックスと同じである。
　・仮想インデックスを用いた集計
　仮想転置構造体を用いた仮想インデックスで集計を行ってみる。集計結果のｉ番目の値ｖａｌｕｅは上記の情報２で与えられ、集計結果のｉ番目の値の出現回数ｃｏｕｎｔは式（８）で与えられる。それに従って集計を行うと、以下の表１のようになる。
Figure JPOXMLDOC01-appb-T000011
 　ここで、同じ値でもその値を提供したＤ５Ａが異なると分かれて集計結果が得られる。このため、その方が望ましいユーザはそれをそのまま、そうでないユーザは同じ値に対する出現回数を合算する必要がある。合算は最大でＤ５Ａの数を超えないのでそのために要する処理時間は大きくない。また、集計結果を保持するために新たな記憶域を必要とすることがないのはＤ５Ａインデックスと同じである。
　以上、仮想ＳＶＬ、仮想ＡＣＭ、仮想ＩＮＶが存在することがわかった。したがって、仮想転置構造体が存在するといえる。転置構造体はＤ５Ａインデックスのためのデータ構造であり、同様の理由により仮想転置構造体は仮想インデックスのためのデータ構造であると言うことができる。
　また、仮想転置構造体はソースカラムの転置構造体への参照で構成されているが、ソースカラムが仮想カラムである場合にはその転置構造体は仮想転置構造体であるので、その場合、仮想転置構造体が階層的に構築されていることになる。
　　≪階層的に作成された仮想表形式データの仮想インデックス≫
　仮想転置構造体が階層的に作れることを述べたが、以下、実例を用いてそれを確かめる。図１０は、Ｄ５ＡファイルであるＣ０（３）とＣ１（２）で仮想表形式データＣＶ０（５）を作成し、その仮想表形式データＣＶ０（５）とＤ５ＡファイルであるＣ２（３）で更なる仮想表形式データＣＶ１（８）を作成する例を示している。以下に割り付け写像の定義を示す。
　Ｆ（Ｃ０（３）→ＣＶ０（５））＝（２，３，０）
　Ｆ（Ｃ１（２）→ＣＶ０（５））＝（４，１）
　Ｆ（ＣＶ０（５）→ＣＶ１（８））＝（２，３，７，１，５）
　Ｆ（Ｃ２（３）→ＣＶ１（８））＝（０，６，４）
　このとき、図１０の転置構造体がどうなるのかを示したが図１１である。Ｃ０（３）、Ｃ１（２）、ＣＶ０（５）、Ｃ２（３）の転置構造体又は仮想転置構造体は同図に示したとおりになる。それぞれのＩＮＶは式（１５）と同様に、以下のようにしてＩＮＶ'に読み替えられる。
　ＩＮＶ０'＝Ｆ（Ｃ０（３）→ＣＶ０（５））・ＩＮＶ０＝（２，３，０）・（１，０，２）＝（３，２，０）
　ＩＮＶ１'＝Ｆ（Ｃ１（２）→ＣＶ０（５））・ＩＮＶ１＝（４，１）・（０，１）＝（４，１）
　ＩＮＶＶ０'＝Ｆ（ＣＶ０（５）→ＣＶ１（８））・ＩＮＶＶ０＝（２，３，７，１，５）・（３，４，２，０，１）＝（１，５，７，２，３）
　ＩＮＶ２'＝Ｆ（Ｃ２（３）→ＣＶ１（８））・ＩＮＶ２＝（０，６，４）・（２，１，０）＝（４，６，０）
　こうしてできたＳＶＬ、ＡＣＭ、ＩＮＶ'を使って既に説明した手順によりＣＶ０（５）、ＣＶ１（８）の仮想転置構造体が構成できる。
　ここで、階層的に作成された仮想表形式データを、仮想インデックスを使ってソート・検索・集計を行ってみる。
　・階層的にできた仮想表形式データの仮想インデックスを使ったソート
　階層的にできた仮想転置構造体を用いた仮想インデックスでソートを行ってみる。図１０、図１１にはＮＮＣが記載されていないためその代わりに図１０のＣＶ１（８）を用いる。ソート結果は以下となる。
　ＣＶ１（８）・ＩＮＶＶ１＝（Ｄ２，Ａ０，Ｂ０，Ｃ１，Ａ２，Ａ１，Ｂ２，Ｂ０）・（１，５，４，７，２，６，３，０）＝（Ａ０，Ａ１，Ａ２，Ｂ０，Ｂ０，Ｂ２，Ｃ１，Ｄ２）
　上記の結果より確かにソートされていることが分かる。加えて、ソート結果には同じ「Ａ」や「Ｂ」や「Ｃ」であってもＣ０（３）の「Ａ」や「Ｂ」がＣ１（２）、Ｃ２（３）のそれらよりも先に来ることがわかる。これは同じ値のときはカラム番号が小さい方がその値が小さいとの取り決めが反映されたためである。また、ソート結果を保持するために新たな記憶領域を必要とすることがないのはＤ５Ａインデックスと同じである。
　・階層的にできた仮想表形式データの仮想インデックスを使った検索
　階層的にできた仮想転置構造体を用いた仮想インデックスで検索を行ってみる。図１０、図１１にはＮＮＣが記載されていないためその代わりに図１０のＣＶ１（８）を用いる。また、検索は「Ｂ」～「Ｃ」の条件で行うものとする。
　式（８）でｉ０＝３、ｉ１＝５となるため、（ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ０－１］］，・・・，ＩＮＶ（Ｒ） （Ｒ）［ＡＣＭ（Ｋ）［ｉ１］－１］）＝（７，２，６，３）となる。したがって、検索結果は以下となる。
　ＣＶ１（８）・（７，２，６，３）＝（Ｄ２，Ａ０，Ｂ０，Ｃ１，Ａ２，Ａ１，Ｂ２，Ｂ０）・（７，２，６，３）＝（Ｂ０，Ｂ０，Ｂ２，Ｃ１）
　また、検索結果を保持するためにはｉ０、ｉ１を保持するだけでよいためわずかな記憶域しか必要としないことはＤ５Ａインデックスと同じである。
　・階層的にできた仮想表形式データの仮想インデックスを用いた集計
　階層的にできた仮想転置構造体を用いた仮想インデックスで集計を行ってみる。計結果のｉ番目の値ｖａｌｕｅは上記の情報２で与えられ、集計結果のｉ番目の値の出現回数ｃｏｕｎｔは式（８）で与えられる。それに従って集計を行うと、以下の表２のようになる。
Figure JPOXMLDOC01-appb-T000012
 　ここで、同じ値でもその値を提供したＤ５Ａが異なると分かれて集計結果が得られる。このため、その方が望ましいユーザはそれをそのまま、そうでないユーザは同じ値に対する出現回数を合算する必要がある。その場合でも最大でＤ５Ａの数を超えないのでそのために要する処理時間は大きくない。また、集計結果を保持するために新たな記憶域を必要とすることがないのはＤ５Ａインデックスと同じである。
　　≪スペクトル分解を通じた仮想インデックスの理解≫
　図１１のＣ０（３），Ｃ１（２）→ＣＶ０（５）とＣＶ０（５），Ｃ２（３）→ＣＶ１（８）をスペクトル分解の立場から解釈すると分かりやすい。分かりやすさのために、以下の式はすべて割り付け写像を使ってＩＮＶをＩＮＶ'に読み替えた後の形で記載する。
　Ｃ０（３）とＣ１（２）をスペクトル分解で表すと以下となる。
　Ｃ０（３）＝Ａ０：（３）＋Ｂ０：（２，０）
　Ｃ１（２）＝Ａ１：（４）＋Ｃ１（１）
　このため、ＣＶ０（５）は、以下で表すことができる。
　ＣＶ０（５）＝Ｃ０（３）＋Ｃ１（２）＝Ａ０：（３）＋Ａ１：（４）＋Ｂ０：（２，０）＋Ｃ１（１）
　また、ＣＶ０（５）とＣ２（３）をスペクトル分解で表すと以下となる。
　ＣＶ０（５）＝Ａ０：（１）＋Ａ１：（５）＋Ｂ０：（７，２）＋Ｃ１（３）
　Ｃ２（３）＝Ａ２：（４）＋Ｂ２：（６）＋Ｄ２：（０）
　このため、ＣＶ１（８）は、以下で表すことができる。
　ＣＶ１（８）＝ＣＶ０（５）＋Ｃ２（３）＝Ａ０：（１）＋Ａ１：（５）＋Ａ２：（４）＋Ｂ０：（７，２）＋Ｂ２：（６）＋Ｃ１（３）＋Ｄ２：（０）
　したがって、ソート結果列は（１，５，４，７，２，６，３，０）となる。また、「Ｂ」
～「Ｃ」での検索結果列は（７，２，６，３）となる。集計も上記の表３と同様にできる。このため、手計算の場合はスペクトル分解による計算は分かりやすくて優れていることが分かる。
　＜データ処理装置１０を含むシステムの全体構成例＞
　本実施形態に係るデータ処理装置１０を含むシステムの全体構成例を図１２に示す。図１２に示すように、本実施形態に係るデータ処理装置１０は、インターネット等のネットワーク２０上に分散して配置されているデータベースサーバと通信可能に接続される。これらのデータベースサーバには、Ｄ５Ａ又は仮想表形式データの少なくとも一方が１つ以上格納されている。
　ここで、本実施形態に係るデータ処理装置１０は、仮想表形式データ作成部１０１と、ソート部１０２と、検索部１０３と、集計部１０４と、記憶部１０５とを有する。なお、仮想表形式データ作成部１０１、ソート部１０２、検索部１０３及び集計部１０４は、例えば、データ処理装置１０にインストールされた１以上のプログラムが、ＣＰＵ（Central Processing Unit）等のプロセッサに実行させる処理により実現される。また、記憶部１０５は、例えば、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）、フラッシュメモリ等により実現される。
　仮想表形式データ作成部１０１は、上記の「仮想表形式データの構成法」で説明した１～５の情報を持つ仮想表形式データを作成する。また、仮想表形式データ作成部１０１は、上記の「仮想表形式データの構成法」で説明した５の区間写像を定義する際に、「異なる区間からの割り付けの衝突検出」で説明した方法により、区間写像（割り付け写像）による割り付け先が衝突しているか否かを判定する。
　ソート部１０２は、上述した仮想表形式データの仮想転置構造体を用いた仮想インデックスでのソートを実行する。例えば、ソート部１０２は、仮想表形式データのソート対象の仮想カラムと、その仮想カラムの仮想転置構造体に含まれる仮想ＩＮＶとを用いて、それらのインデックス演算によりソート結果を計算する。
　検索部１０３は、検索条件を受け付けると、上述した仮想表形式データの仮想転置構造体を用いた仮想インデックスで検索を実行する。例えば、検索部１０３は、仮想表形式データの検索対象の仮想カラムと、その仮想カラムに対する検索条件と、その仮想カラムの仮想転置構造体に含まれる仮想ＩＮＶ及び仮想ＡＣＭとを用いて、式（８）及び式（１０）を計算した後、当該仮想カラムと式（８）及び式（１０）の計算結果とのインデックス演算により検索結果を計算する。
　集計部１０４は、上述した仮想表形式データの仮想転置構造体を用いた仮想インデックスで集計を行う。例えば、集計部１０４は、仮想表形式データの集計対象の仮想カラムの仮想転置構造体を用いて、上記の情報２と式（８）により集計を行う。
　記憶部１０５は、各種データ（例えば、仮想表形式データ、Ｄ５Ａ、ソート結果、検索結果、集計結果等）を記憶する。
　＜データ処理装置１０のハードウェア構成例＞
　本実施形態に係るデータ処理装置１０のハードウェア構成例を図１３に示す。図１３に示すように、本実施形態に係るデータ処理装置１０は、入力装置２０１と、表示装置２０２と、外部Ｉ／Ｆ２０３と、通信Ｉ／Ｆ２０４と、ＲＡＭ（Random Access Memory）２０５と、ＲＯＭ（Read Only Memory）２０６と、補助記憶装置２０７と、プロセッサ２０８とを有する。これらの各ハードウェアは、それぞれがバス２０９を介して通信可能に接続される。
　入力装置２０１は、例えば、キーボード、マウス、タッチパネル、物理ボタン等である。表示装置２０２は、例えば、ディスプレイ、表示パネル等である。なお、データ処理装置１０は、例えば、入力装置２０１及び表示装置２０２の少なくとも一方を有していなくてもよい。
　外部Ｉ／Ｆ２０３は、記録媒体２０３ａ等の外部装置とのインタフェースである。記録媒体２０３ａとしては、例えば、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等が挙げられる。
　通信Ｉ／Ｆ２０４は、データ処理装置１０をネットワーク２０に接続するためのインタフェースである。ＲＡＭ２０５は、プログラムやデータを一時保持する揮発性の半導体メモリ（記憶装置）である。ＲＯＭ２０６は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリ（記憶装置）である。補助記憶装置２０７は、例えば、ＨＤＤ、ＳＳＤ、フラッシュメモリ等の不揮発性の記憶装置である。プロセッサ２０８は、例えば、ＣＰＵ等の各種演算装置である。
　なお、図１３に示すハードウェア構成は一例であって、データ処理装置１０は、他のハードウェア構成を有していてもよい。例えば、データ処理装置１０は、複数の補助記憶装置２０７や複数のプロセッサ２０８を有していてもよいし、図示したハードウェアの一部を有していなくてもよいし、図示したハードウェア以外の種々のハードウェアを有していてもよい。
　＜仮想表形式データの作成処理の流れ＞
　以下では、仮想表形式データの作成処理の流れについて、図１４を参照しながら説明する。
　ステップＳ１０１：まず、仮想表形式データ作成部１０１は、仮想表形式データのレコード数と仮想カラムの名前及びデータ型の指定を受け付ける（上記の「仮想表形式データの構成法」で説明した１～２の情報）。なお、仮想表形式データのレコード数と仮想カラムの名前及びデータ型は、例えば、ユーザによって指定される。
　ステップＳ１０２：次に、仮想表形式データ作成部１０１は、１つ以上のソース表形式データのＵＲＬ又はパスの指定を受け付ける（上記の「仮想表形式データの構成法」で説明した３の情報）。なお、１つ以上のソース表形式データのＵＲＬ又はパスは、例えば、ユーザによって指定される。また、１つ以上のソース表形式データに含まれる１以上のカラムのＵＲＬ又はパスが指定されてもよい。
　ステップＳ１０３：次に、仮想表形式データ作成部１０１は、各ソース表形式データ中のソースカラムとソース区間の定義を受け付ける（上記の「仮想表形式データの構成法」で説明した４の情報）。なお、各ソース表形式データ中のソースカラムとソース区間の定義は、例えば、ユーザによって指定される。
　ステップＳ１０４：次に、仮想表形式データ作成部１０１は、ソース区間毎の区間写像の定義を受け付け（上記の「仮想表形式データの構成法」で説明した５の情報）、逆写像の定義を算出する。なお、ソース区間毎の区間写像とその逆写像の定義は、例えば、ユーザによって指定される。また、区間写像が定義されるとその逆写像は式（１２）及び式（１４）で自動的に定まり、記憶部１０５に格納される。
　ステップＳ１０５：最後に、仮想表形式データ作成部１０１は、上記のステップＳ１０１～ステップＳ１０４で受け付けた情報を仮想表形式データとして記憶部１０５に保存する。
　＜仮想表形式データにおけるソート処理の流れ＞
　以下では、仮想表形式データにおけるソート処理の流れについて、図１５を参照しながら説明する。
　ステップＳ２０１：ソート部１０２は、仮想表形式データの仮想カラムのうち、ソート対象の仮想カラムの仮想転置構造体を用いた仮想インデックスでのソートを実行する。
　ステップＳ２０２：そして、ソート部１０２は、上記のステップＳ２０１におけるソート結果を記憶部１０５に保存する。ただし、ソート部１０２は、ソート結果を保存しなくてもよい。
　＜仮想表形式データにおける検索処理の流れ＞
　以下では、仮想表形式データにおける検索処理の流れについて、図１６を参照しながら説明する。
　ステップＳ３０１：まず、検索部１０３は、検索条件を受け付ける。
　ステップＳ３０２：次に、検索部１０３は、仮想表形式データの仮想カラムのうち、検索対象の仮想カラムの仮想転置構造体を用いた仮想インデックスでの検索を実行する。
　ステップＳ３０３：そして、検索部１０３は、上記のステップＳ３０２における検索結果を記憶部１０５に保存する。
　＜仮想表形式データにおける集計処理の流れ＞
　以下では、仮想表形式データにおける集計処理の流れについて、図１７を参照しながら説明する。
　ステップＳ４０１：集計部１０４は、仮想表形式データの仮想カラムのうち、集計対象の仮想カラムの仮想転置構造体を用いた仮想インデックスで集計を実行する。
　ステップＳ４０２：そして、集計部１０４は、上記のステップＳ３０３における集計結果を記憶部１０５に保存する。ただし、集計部１０４は、集計結果を保存しなくてもよい。
　＜まとめ＞
　以上のように、本実施形態に係るデータ処理装置１０では、Ｄ５Ａ又は既に定義済の仮想表形式データをソース表形式データとして、割り付け写像により新たな仮想表形式データを定義することができる。しかも、これらの仮想表形式データは仮想インデックスによりソート、検索、集計を高速に実現することが可能となる。
　このため、例えば、元となる表形式データのＤ５Ａを起点として様々な仮想表形式データを階層的に作成することが可能となり、これらの仮想表形式データのソート、検索、集計も高速に実行することが可能となる。また、利用者は、自身の利用目的に応じて、既に公開されているＤ５Ａや仮想表形式データから新たな仮想表形式データを作成し、公開することも可能となる。
　＜補足＞
　以下、補足として、既存技術ではインデックスの継承ができない一方で、本実施形態ではインデックスの継承が可能な理由について説明する。
　インデックスはインデックスのためのデータ構造とそのデータ構造を使って処理を高速化するアルゴリズムのセットで実現される。転置構造体はソート、検索、集計を高速化するインデックスのためのデータ構造と見做すことができる。転置構造体からカラムの要素を並べ替えたカラムに対する仮想転置構造体を作成することができる。また、複数の転置構造体から仮想転置構造体を作成することができる。更に、複数の仮想転置構造体を階層化して更なる仮想転置構造体を作成することもできる。このように、仮想転置構造体は、階層的にも或いはカラムの要素が並べ替えられても作成することができる。転置構造体を使うインデックスのアルゴリズムは仮想転置構造体にも適用でき、それが仮想インデックスとなる。既存のインデックスは転置構造体のように複数を組み合わせても階層的に組み合わせても成り立つインデックスのためのデータ構造を持たないため、組み合わせたり階層化したりしたときに継承ができないのである。
　本発明は、具体的に開示された上記の実施形態に限定されるものではなく、請求の範囲の記載から逸脱することなく、種々の変形や変更、既知の技術との組み合わせ等が可能である。
　本願は、日本国に２０２３年１月２７日に出願された基礎出願２０２３－０１０７１６号及び基礎出願２０２３－０１０７１７号に基づくものであり、その全内容はここに参照をもって援用される。
　１０　　　　データ処理装置
　２０　　　　ネットワーク
　１０１　　　仮想表形式データ作成部
　１０２　　　ソート部
　１０３　　　検索部
　１０４　　　集計部
　１０５　　　記憶部
　２０１　　　入力装置
　２０２　　　表示装置
　２０３　　　外部Ｉ／Ｆ
　２０３ａ　　記録媒体
　２０４　　　通信Ｉ／Ｆ
　２０５　　　ＲＡＭ
　２０６　　　ＲＯＭ
　２０７　　　補助記憶装置
　２０８　　　プロセッサ
　２０９　　　バス

Claims (19)

  1. 　１以上の表形式データに含まれる１以上のカラムが持つ第１のデータ構造を所定の写像により変換した第２のデータ構造を持つ仮想カラムで構成される仮想表形式データに対して、前記第２のデータ構造をインデックスとして利用したソート操作、検索操作又は集計操作を行うデータ操作部、
    　を有するデータ処理装置。
  2. 　前記１以上の表形式データには、前記第２のデータ構造を持つ仮想カラムで構成される仮想表形式データが含まれる、請求項１に記載のデータ処理装置。
  3. 　前記１以上の表形式データには、前記カラムの値を昇順に保持する配列であるＳＶＬと、前記カラムの値の転置レコード番号を保持する配列であるＩＮＶと、前記ＳＶＬと前記ＩＮＶとの対応関係を保持する配列であるＡＣＭとで構成されるＤ５Ａ、及び、前記仮想表形式データ、が含まれる、請求項１に記載のデータ処理装置。
  4. 　前記１以上の表形式データには、前記カラムが更に含まれる、請求項３に記載のデータ処理装置。
  5. 　前記１以上の表形式データには、前記カラムの値を前記ＳＶＬ上の位置に置き換えた自然数を保持する配列であるＮＮＣが更に含まれる、請求項３に記載のデータ処理装置。
  6. 　前記データ操作部は、
    　前記仮想表形式データのソート対象のカラムに関する前記第２のデータ構造に含まれるＩＮＶにより、前記ソート対象のカラムの値を順に取得することで、前記ソート操作を行う、請求項３乃至５の何れか一項に記載のデータ処理装置。
  7. 　前記データ操作部は、
    　前記仮想表形式データの検索対象のカラムに関する前記第２のデータ構造に含まれるＩＮＶ及びＡＣＭと、検索条件として与えられた値ｖ０及びｖ１とを用いて、ｖ０≦ＳＶＬ［ｉ０］を満たす最小のｉ０とＳＶＬ［ｉ１］≦ｉ１を満たす最大のｉ１から（ＩＮＶ［ＡＣＭ［ｉ０－１］］，・・・，ＩＮＶ［ＡＣＭ［ｉ１］－１］）を検索結果として求めることで、前記検索操作を行う、請求項３乃至５の何れか一項に記載のデータ処理装置。
  8. 　前記データ操作部は、
    　前記仮想表形式データの集計対象のカラムに関する前記第２のデータ構造に含まれるＳＶＬ及びＡＣＭを用いて、ＡＣＭ［ｉ］－ＡＣＭ［ｉ－１］により、前記仮想表形式データのＳＶＬのｉ番目の要素の集計結果を算出することで、前記集計操作を行う、請求項３乃至５の何れか一項に記載のデータ処理装置。
  9. 　１以上の表形式データに含まれる１以上のカラムが持つ第１のデータ構造を所定の写像により変換した第２のデータ構造を持つ仮想カラムで構成される仮想表形式データに対して、前記第２のデータ構造をインデックスとして利用したソート操作、検索操作又は集計操作を行うデータ操作手順、
    　をコンピュータが実行するデータ処理方法。
  10. 　１以上の表形式データに含まれる１以上のカラムが持つ第１のデータ構造を所定の写像により変換した第２のデータ構造を持つ仮想カラムで構成される仮想表形式データに対して、前記第２のデータ構造をインデックスとして利用したソート操作、検索操作又は集計操作を行うデータ操作手順、
    　をコンピュータに実行させるプログラム。
  11. 　作成対象の仮想表形式データのレコード数と、前記仮想表形式データのカラムを表す仮想カラムと、１以上の表形式データと、前記１以上の表形式データに含まれる１以上のカラムとの指定を受け付ける受付部と、
    　前記１以上の表形式データに含まれる前記１以上のカラムが持つ第１のデータ構造を所定の写像により変換した第２のデータ構造を前記仮想カラムに割り付けることで、前記仮想表形式データを作成する割り付け写像定義部と、
    　を有するデータ処理装置。
  12. 　前記１以上のカラムの値を、前記仮想表形式データの前記仮想カラム上に表示する表示部、を有する請求項１１に記載のデータ処理装置。
  13. 　前記写像には、前記第１のデータ構造と前記第２のデータ構造との対応関係が１次関数で表現される１次関数型写像と、前記第１のデータ構造と前記第２のデータ構造との対応関係が前記対応関係の列挙で表現される列挙型写像とが含まれる、請求項１１又は１２に記載のデータ処理装置。
  14. 　異なる第１のデータ構造に関して、異なる写像によりそれぞれ変換した第２のデータ構造が衝突するか否かを判定する衝突判定部、を有する請求項１３に記載のデータ処理装置。
  15. 　前記衝突判定部は、
    　前記異なる写像のうちの任意の２つの写像をＦ０，Ｆ１として、
    　前記写像Ｆ０の値域と前記写像Ｆ１の値域とが同一の仮想カラム上にない場合、前記写像Ｆ０の変換先の第２のデータ構造と前記写像Ｆ１の変換先の第２のデータ構造とは衝突しないと判定し、
    　前記写像Ｆ０の値域を表す区間の開始位置を表すインデックスをｖ０、前記写像Ｆ０の定義域を表す区間の長さをｗ０、前記写像Ｆ１の値域を表す区間の開始位置を表すインデックスをｖ１としたとき、ｖ０＋ｗ０－１＜ｖ１である場合、前記写像Ｆ０の変換先の第２のデータ構造と前記写像Ｆ１の変換先の第２のデータ構造とは衝突しないと判定し、
    　前記写像Ｆ１の定義域を表す区間の長さをｗ１としたとき、ｖ１＋ｗ１－１＜ｖ０である場合、前記写像Ｆ０の変換先の第２のデータ構造と前記写像Ｆ１の変換先の第２のデータ構造とは衝突しないと判定する、請求項１４に記載のデータ処理装置。
  16. 　前記衝突判定部は、
    　前記写像Ｆ０と前記写像Ｆ１とがいずれも列挙型写像である場合、前記写像Ｆ０の値域を表す区間の長さをｗ０、前記写像Ｆ１の値域を表す区間の長さをｗ１、Ｌ０＝（ｖ０，・・・，ｖ０＋ｗ０－１）、Ｌ１＝（ｖ１，・・・，ｖ１＋ｗ１－１）として、Ｌ０とＬ１の共通範囲Ｌ０'，Ｌ１'を求め、各ｉ，ｊに対してＬ０'［ｉ］＝Ｌ１'［ｊ］とならないとき、前記写像Ｆ０の変換先の第２のデータ構造と前記写像Ｆ１の変換先の第２のデータ構造とは衝突しないと判定し、
    　前記写像Ｆ０と前記写像Ｆ１とがいずれも１次関数型写像である場合、前記写像Ｆ０の値域と前記写像Ｆ１の値域との共通部分を値域とするｙ０＝ａ０×ｘ０＋ｂ０；ｘ０＝０，１，２，・・・，Ｎ０－１で前記写像Ｆ０を記述し直すと共に、前記共通部分を値域とするｙ１＝ａ１×ｘ１＋ｂ１；ｘ１＝０，１，２，・・・，Ｎ１－１で前記写像Ｆ１を記述し直し、ｘ０≦ＭｉｎＩｎｔ（Ｎ０－１，ＬＣＭ（ａ０，ａ１）ｄｉｖ　ａ０）とｘ１≦ＭｉｎＩｎｔ（Ｎ１－１，ＬＣＭ（ａ０，ａ１）ｄｉｖ　ａ１）のｘ０，ｘ１に対してｙ０＝ｙ１とならないとき、前記写像Ｆ０の変換先の第２のデータ構造と前記写像Ｆ１の変換先の第２のデータ構造とは衝突しないと判定し、
    　前記写像Ｆ０が１次関数型写像、前記写像Ｆ１が列挙型写像である場合、前記写像Ｆ０の値域と前記写像Ｆ１の値域との共通部分を値域とするｙ０（ｎ）＝ａ０×ｎ＋ｂ０；ｘ０＝０，１，２，・・・，Ｎ－１で前記写像Ｆ０を記述し直すと共に、前記共通部分を値域とするｙ１（ｍ）＝（ｖ１，・・・，ｖ１＋ｗ１－１）［ｍ］で前記写像Ｆ１を記述し直し、各ｎ，ｍに対してｙ０（ｎ）＝ｙ１（ｍ）とならないとき、前記写像Ｆ０の変換先の第２のデータ構造と前記写像Ｆ１の変換先の第２のデータ構造とは衝突しないと判定する、請求項１５に記載のデータ処理装置。
  17. 　前記第１のデータ構造及び前記第２のデータ構造は、転置レコード番号を要素とする配列を表すＩＮＶが少なくとも含まれるデータ構造である、請求項１６に記載のデータ処理装置。
  18. 　作成対象の仮想表形式データのレコード数と、前記仮想表形式データのカラムを表す仮想カラムと、１以上の表形式データと、前記１以上の表形式データに含まれる１以上のカラムとの指定を受け付ける受付手順と、
    　前記１以上の表形式データに含まれる前記１以上のカラムが持つ第１のデータ構造を所定の写像により変換した第２のデータ構造を前記仮想カラムに割り付けることで、前記仮想表形式データを作成する割り付け写像定義手順と、
    　をコンピュータが実行するデータ処理方法。
  19. 　作成対象の仮想表形式データのレコード数と、前記仮想表形式データのカラムを表す仮想カラムと、１以上の表形式データと、前記１以上の表形式データに含まれる１以上のカラムとの指定を受け付ける受付手順と、
    　前記１以上の表形式データに含まれる前記１以上のカラムが持つ第１のデータ構造を所定の写像により変換した第２のデータ構造を前記仮想カラムに割り付けることで、前記仮想表形式データを作成する割り付け写像定義手順と、
    　をコンピュータに実行させるプログラム。
PCT/JP2024/000399 2023-01-27 2024-01-11 データ処理装置、データ処理方法、及びプログラム Ceased WO2024157776A1 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
JP2024572949A JPWO2024157776A1 (ja) 2023-01-27 2024-01-11
CN202480009105.5A CN120584343A (zh) 2023-01-27 2024-01-11 数据处理装置、数据处理方法及程序产品
KR1020257027169A KR20250133955A (ko) 2023-01-27 2024-01-11 데이터 처리 장치, 데이터 처리 방법, 및 프로그램
EP24747107.1A EP4657274A4 (en) 2023-01-27 2024-01-11 DATA PROCESSING DEVICE, DATA PROCESS AND PROGRAM
US19/280,646 US20250355848A1 (en) 2023-01-27 2025-07-25 Data processing device, data processing method, and program

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP2023010717 2023-01-27
JP2023-010717 2023-01-27
JP2023-010716 2023-01-27
JP2023010716 2023-01-27

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US19/280,646 Continuation US20250355848A1 (en) 2023-01-27 2025-07-25 Data processing device, data processing method, and program

Publications (1)

Publication Number Publication Date
WO2024157776A1 true WO2024157776A1 (ja) 2024-08-02

Family

ID=91970355

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2024/000399 Ceased WO2024157776A1 (ja) 2023-01-27 2024-01-11 データ処理装置、データ処理方法、及びプログラム

Country Status (6)

Country Link
US (1) US20250355848A1 (ja)
EP (1) EP4657274A4 (ja)
JP (1) JPWO2024157776A1 (ja)
KR (1) KR20250133955A (ja)
CN (1) CN120584343A (ja)
WO (1) WO2024157776A1 (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12536206B2 (en) * 2024-05-08 2026-01-27 Microsoft Technology Licensing, Llc Inferring graph model from data in lake
US12547597B2 (en) 2024-05-08 2026-02-10 Microsoft Technology Licensing, Llc Inferring graph model from semantic model

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2013117873A (ja) * 2011-12-02 2013-06-13 Hitachi Systems Ltd データベース処理方法
JP2015207026A (ja) * 2012-08-29 2015-11-19 株式会社ターボデータラボラトリー 情報処理装置、レコード位置情報特定方法および情報処理プログラム
WO2023276162A1 (ja) * 2021-07-02 2023-01-05 晋二 古庄 データ作成装置、データ作成方法、及びプログラム

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH1091644A (ja) * 1996-09-10 1998-04-10 Oki Electric Ind Co Ltd データベース問い合わせ処理方法及び装置
JP3860992B2 (ja) * 2001-11-09 2006-12-20 株式会社ターボデータラボラトリー データの結合・提示方法、および、データ結合・提示プログラム
JP4881435B2 (ja) * 2007-06-21 2012-02-22 株式会社ターボデータラボラトリー メモリ共有型並列処理システムにおいて表形式データを集計する方法及び装置
US10237916B2 (en) 2015-09-30 2019-03-19 Tokyo Electron Limited Systems and methods for ESC temperature control
CA3038475A1 (en) 2016-09-28 2018-04-05 Immpact-Bio Ltd. A universal platform for car therapy targeting a novel antigenic signature of cancer
JP2021067962A (ja) * 2018-02-21 2021-04-30 株式会社ターボデータラボラトリー 情報処理システム及び情報処理方法
CN116648697A (zh) * 2021-01-13 2023-08-25 Ess控股株式会社 信息处理方法、信息处理装置和程序

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2013117873A (ja) * 2011-12-02 2013-06-13 Hitachi Systems Ltd データベース処理方法
JP2015207026A (ja) * 2012-08-29 2015-11-19 株式会社ターボデータラボラトリー 情報処理装置、レコード位置情報特定方法および情報処理プログラム
WO2023276162A1 (ja) * 2021-07-02 2023-01-05 晋二 古庄 データ作成装置、データ作成方法、及びプログラム

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP4657274A1 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12536206B2 (en) * 2024-05-08 2026-01-27 Microsoft Technology Licensing, Llc Inferring graph model from data in lake
US12547597B2 (en) 2024-05-08 2026-02-10 Microsoft Technology Licensing, Llc Inferring graph model from semantic model

Also Published As

Publication number Publication date
EP4657274A1 (en) 2025-12-03
EP4657274A4 (en) 2026-04-15
US20250355848A1 (en) 2025-11-20
CN120584343A (zh) 2025-09-02
JPWO2024157776A1 (ja) 2024-08-02
KR20250133955A (ko) 2025-09-09

Similar Documents

Publication Publication Date Title
Anand et al. Mining of massive datasets
JP5342958B2 (ja) 圧縮データの構造を問い合わせる方法
US8533203B2 (en) Identifying synonyms of entities using a document collection
Amato et al. MI-File: using inverted files for scalable approximate similarity search
US7761407B1 (en) Use of primary and secondary indexes to facilitate aggregation of records of an OLAP data cube
US8219564B1 (en) Two-dimensional indexes for quick multiple attribute search in a catalog system
Genuzio et al. Fast scalable construction of (minimal perfect hash) functions
US20250355848A1 (en) Data processing device, data processing method, and program
CN113536040B (zh) 信息查询方法、装置以及存储介质
Deepak et al. EvoMiner: frequent subtree mining in phylogenetic databases
Khan et al. Set-based unified approach for summarization of a multi-attributed graph
Baswana et al. Mincut sensitivity data structures for the insertion of an edge
US11106703B1 (en) Clustering of structured and semi-structured data
Brisaboa et al. Aggregated 2d range queries on clustered points
Chen et al. On the signature tree construction and analysis
Karaoglu et al. The number of cubic surfaces with 27 lines over a finite field
Aggarwal et al. Gconnect: A connectivity index for massive disk-resident graphs
Patil et al. Succinct representations of weighted trees supporting path queries
JP2004534981A (ja) データベース・システムでデータを編成し、問合せを処理する方法、およびそのような方法を実施するためのデータベース・システムおよびソフトウェア製品
McKay et al. Enumeration of Latin squares with conjugate symmetry
Yang et al. Querying a collection of continuous functions
Harvey et al. Resolving unresolved resolved and unresolved triplets consistency problems
Chen et al. On the Designing of Popular Packages
Paul et al. Optimized entity attribute value model: a search efficient representation of high dimensional and sparse data
JP2021114037A (ja) インデックス管理装置

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 24747107

Country of ref document: EP

Kind code of ref document: A1

DPE1 Request for preliminary examination filed after expiration of 19th month from priority date (pct application filed from 20040101)
ENP Entry into the national phase

Ref document number: 2024572949

Country of ref document: JP

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 2024572949

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 202480009105.5

Country of ref document: CN

ENP Entry into the national phase

Ref document number: 1020257027169

Country of ref document: KR

Free format text: ST27 STATUS EVENT CODE: A-0-1-A10-A15-NAP-PA0105 (AS PROVIDED BY THE NATIONAL OFFICE)

WWE Wipo information: entry into national phase

Ref document number: 1020257027169

Country of ref document: KR

NENP Non-entry into the national phase

Ref country code: DE

WWP Wipo information: published in national office

Ref document number: 202480009105.5

Country of ref document: CN

WWP Wipo information: published in national office

Ref document number: 2024747107

Country of ref document: EP