JP3549608B2 - Method and apparatus for determining structure of hierarchical data based on identifier - Google Patents

Description

[0001]
[Industrial applications]
The present invention relates to a determination method and apparatus for determining the structure of hierarchical structure data when inserting data into hierarchical structure data managed by a chain.
[0002]
[Prior art]
In an information processing apparatus, there is a method using a hierarchical structure as one of methods for managing a plurality of different data in association with each other. Hierarchical structure data composed of several data having an upper and lower relationship with each other is managed by a chain in which data is linked by, for example, a pointer.
[0003]
FIG. 11 shows an example of such hierarchical structure data. The hierarchical structure data in FIG. 11 is composed of five data: data α, β, γ having a data structure of a lower layer, and data A, B having no data structure of a lower layer. Among them, the data A exists in each lower layer of α and β, but the actual data (substance data) is one because the hierarchical structure data is managed by the chain. As described above, when the hierarchy is managed by the chain, there is an advantage that the same data can be referred to from a plurality of locations in the hierarchical structure. When data is inserted by adding a new hierarchical relationship between data in the hierarchical structure data, the data may or may not have an infinite hierarchy.
[0004]
FIG. 12 shows an example of data insertion that does not result in an infinite hierarchy in the hierarchical structure data of FIG. In FIG. 12, data β is inserted in a lower layer of data γ, and data γ has a relationship including not only data β but also data under the data β, that is, data A and B.
[0005]
On the other hand, FIG. 13 shows an example of data insertion in which the hierarchical structure data of FIG. 11 has an infinite hierarchy. In FIG. 13, as a result of inserting the same data α in a lower layer of the data α, the chains in the vertical direction are connected in a loop. Therefore, an infinite hierarchy in which the data α is repeated endlessly is formed in a lower layer of the data α.
[0006]
[Problems to be solved by the invention]
The conventional data manipulation method as described above has the following problems. If an attempt is made to retrieve all data in hierarchical structure data having an infinite hierarchy as shown in FIG. 13, the same data structure composed of data α, β, γ, A, and B appears many times in the lower layer. , The same entity data must be fetched each time. Therefore, the processing becomes complicated and the processing speed is reduced.
[0007]
Even if it is prohibited to connect data having the same name up and down, there is a possibility that an infinite hierarchy may occur. For example, in FIG. 11, when data α is inserted below data γ, an infinite hierarchy occurs. In addition, when certain data is copied and another name is added, the data having another name may be inserted below the original data to generate an infinite hierarchy. In such a case, the data operation becomes complicated as in the case of FIG.
[0008]
The present invention provides a data structure judging method and an apparatus therefor for examining a data structure to judge whether an infinite hierarchy occurs, in order to prevent data processing of hierarchical structure data managed by a chain from becoming complicated. The purpose is to:
[0009]
[Means for Solving the Problems]
FIG. 1 is a principle diagram of the data structure determination method of the present invention.
In FIG. 1, first, an identifier is added to data that is each element of hierarchical structure data composed of two or more data having a vertical relationship (step S1), and second data is inserted below the first data. It is checked whether or not there are two or more data having the same identifier in the vertical data string generated by the process (step S2).
[0010]
If there are two or more pieces of data having the same identifier, it is determined that inserting the second data below the first data results in an infinite hierarchical structure (Step S3), and two pieces of data having the same identifier are determined. If not, it is determined that the infinite hierarchical structure is not obtained even if the second data is inserted below the first data (step S4).
The data structure determination device of the present invention includes a data storage unit and a processing unit, and operates on hierarchical structure data composed of two or more data having a vertical relationship. The data storage means stores the data to which each element of the hierarchical structure data is added with the identifier. The processing means checks whether or not the second data can own the lower third data in the vertical data string formed by inserting the second data below the first data. If the third data can own the third data, it is determined whether the identifier of the first data matches the identifier of one of the second data and the data lower than the second data. If the data identifier matches the data identifier, it is determined that an infinite hierarchical structure occurs when the second data is inserted below the first data, and the first data identifier is determined to be the second data and the second data. If the data does not match the identifier of any of the data lower than the second data, it is determined that the infinite hierarchical structure does not occur even if the second data is inserted below the first data. Data cannot own third data Lever, infinite hierarchy be inserted second data under the first data is determined to not occur.
[0011]
[Action]
The data that constitutes each element of the hierarchical structure data has information indicating a vertical relationship with other data, and by operating this information, a vertical relationship between the data and other data is defined. The data can be inserted into the hierarchical structure.
[0012]
Here, an identifier for uniquely identifying each data is further added (step S1). By comparing the identifiers, it is possible to easily determine whether the two data are substantially the same.
[0013]
When inserting the second data below the first data to generate new hierarchical structure data, or when adding the second data to the existing hierarchical structure data including the first data, the first The identifiers of a plurality of data (data strings) positioned in the up-down direction connecting the data and the second data are checked (step S2). If there are two or more pieces of data having the same identifier among them, a loop occurs in the data chain, so that it is determined that the insertion of the data results in an infinite hierarchical structure (step S3). If there is no two or more data having the same identifier, it is determined that the data insertion does not result in an infinite hierarchical structure (step S4).
[0014]
Using this determination result, when inserting the second data below the first data results in an infinite hierarchical structure, the insertion of the data can be prohibited. Therefore, the efficiency of processing the hierarchical structure data is improved.
[0015]
【Example】
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
FIG. 2 is a system configuration diagram of the information processing apparatus according to the embodiment. The information processing apparatus shown in FIG. 2 includes a CPU (central processing unit) 1, a data storage unit 2, an input / output device 3, and a bus 4 connecting these devices. The data storage unit 2 is a disk device including, for example, a magnetic disk, an optical disk, and the like, and stores individual data as each element of the hierarchical structure data. Each of these data is provided with a unique identifier for identifying the data. The input / output device 3 is, for example, a display device provided with an input device such as a keyboard, and receives a data operation instruction from a user and displays a processing result. The CPU 1 retrieves data from the data storage unit 2 and executes a process in accordance with a data operation instruction command passed from the input / output device 3.
[0016]
For example, when a user gives an instruction to define a hierarchical relationship between some individual data, the CPU 1 stores a pointer indicating the hierarchical relationship in management information of each data, and generates hierarchical structure data. Then, the hierarchical structure data is stored in the data storage unit 2.
[0017]
When a new hierarchical relationship is set between data and data is inserted into the hierarchical structure data, the CPU 1 checks whether an infinite hierarchy is caused by the new hierarchical relationship. Then, in some cases, the result of the check is presented to the user via the input / output device 3, and data is inserted according to the user's instruction.
[0018]
FIG. 3 is a flowchart of a process in which the CPU 1 searches the hierarchical structure data downward, determines its structure, and inserts data. When the process is started in FIG. 3, first, the CPU 1 receives an instruction from the user to insert the second data below the first data constituting the hierarchical structure data (step S11). Next, it is checked whether or not the identifier of the first data matches any of the identifiers of the second data and lower data (step S12). If the identifier does not match any data identifier, the second data is inserted below the first data (step S13), and the process ends.
[0019]
If any of the identifiers of the second data and lower-order data match the identifier of the first data, the user is informed to that effect via the input / output device 3 to determine whether or not to insert the data. (Step S14). Then, if the user permits the data insertion, the second data is inserted below the first data (step S13), and if not, the process is terminated.
[0020]
When there is data having the same identifier as the identifier of the first data in the hierarchy below the second data, the same data structure is repeated up and down by performing the data insertion, and an infinite hierarchy is generated. In the data insertion processing of FIG. 3, in such a case, the user can prohibit data insertion.
[0021]
Next, a specific example of the data insertion processing will be described with reference to FIGS.
FIG. 4 shows a specific example of hierarchical structure data before data insertion. In FIG. 4, groups α and β are data having a lower layer, and members a, b and c are data having no lower layer. The members b and c and the group α exist below the group β, and the member a exists below the group α.
[0022]
FIG. 5 shows the format of the management information set for each data of FIG. 4, and FIG. 6 shows the contents of the management information of each data of FIG. The management information of these data is stored in the data storage unit 2.
[0023]
In FIG. 5, the name indicates the name of the data, and the identifier indicates a number for uniquely identifying the data. The child pointer is a pointer indicating management information of data in a lower layer of the data, and is set so as not to point to anything in the case of data having no lower layer. The previous pointer is a pointer indicating management information of data before the data in the data in the same hierarchy as the data, and is set so as not to point to anything in the case of data located at the head in the same hierarchy. . The rear pointer is a pointer indicating management information of data next to the data in the same layer, and is set so as not to point to anything in the case of data located at the end in the same layer. The real pointer is a pointer that points to the substance of the data (substance data).
[0024]
In the case of each data shown in FIG. 4, as shown in FIG. 6, the identifier of the group α is 1, the child pointer indicates the management information of the member a, the front pointer indicates the management information of the member c, and the rear pointer indicates the management information of the member c. Not even point. Further, the identifier of the group β is 2, the child pointer thereof points to the management information of the member b, and the front pointer and the rear pointer do not indicate anything. The identifier of member a is 3, and its child pointer, front pointer, and rear pointer do not point to anything. The identifier of the member b is 4, the child pointer and the front pointer do not point to anything, and the rear pointer points to the management information of the member c. The identifier of the member c is 5, the child pointer of the member c indicates nothing, the front pointer indicates the management information of the member b, and the rear pointer indicates the management information of the group α.
[0025]
FIG. 7 is a detailed flowchart of the data insertion process by the CPU 1, and FIG. 8 is a flowchart of a subroutine process called in step S22 of FIG. The CPU 1 performs processing in the following order.
[0026]
First, it is determined whether or not the data to be inserted (inserted data) can own the lower layer, that is, whether or not the child pointer of the management information of the data points to any data (step S21). If the insertion data can own the lower layer, the subroutine FindGroup is called with the management information of the data to be inserted (insertion destination data) already existing in the hierarchical structure data and the management information of the insertion data as arguments (step). S22).
[0027]
For example, if there is an instruction to insert the group β under the group α in FIG. 4, it is checked whether the group β can own a lower layer (step S21). Looking at the management information of the group β shown in FIG. 6, the child pointer points to the member b, indicating that the group β is data that can be owned by the lower layer. Then, the subroutine FindGroup is called using the management information of the group α and the management information of the group β as arguments (step S22).
[0028]
The subroutine FindGroup searches in the hierarchy below the insertion data based on the insertion destination data passed as an argument and the management information of the insertion data, and detects the presence or absence of data having the same identifier as the insertion destination data. If data with the same identifier is detected, its return value is 1.
[0029]
Next, the return value of the subroutine FindGroup is checked (step S23). If the return value is not 1, the inserted data is inserted below the insertion destination data (step S24), and the processing is terminated. finish. Here, when the return value is 1, it indicates that an infinite hierarchical structure is formed, and when it is not 1, it indicates that the infinite hierarchical structure is not formed.
[0030]
If the insertion data does not possess the lower layer in step S22, the data structure is not repeated below the insertion data, so the insertion data is inserted directly below the insertion destination data (step S24), and the process ends. For example, if the inserted data is any of the members a, b, and c, these are data that cannot own the lower layer, and are immediately inserted below the insertion destination data.
[0031]
Next, the processing of the subroutine FindGroup in FIG. 7 will be described.
First, each identifier is extracted from each piece of management information passed as an argument, and the two are compared (step S31). If they are equal, the return value is set to 1 (step S39), and the process ends.
[0032]
If the two identifiers are different, the management information of the first data in the lower layer of the inserted data is extracted (step S32), and it is checked whether the data can own the lower layer (step S33). If the data cannot own the lower layer, it is determined whether all the data in the lower layer of the insertion data have been checked. If there is the next data which has not been checked yet in the same hierarchy, the management information is taken out (step S35), and the processing after step S33 is repeated. If it is determined that all data in the lower layer of the insertion data cannot possess the lower layer, the return value is set to 0 (step S36), and the process ends.
[0033]
If the data can own the lower layer in step S33, FindGroup is recursively called using the management information of the insertion destination data passed as an argument and the management information of the extracted data as arguments (step S37). Next, the return value of the recursively called FindGroup is checked (step S38). If it is 1, the return value of the caller's FindGroup is set to 1 (step S39), and the process ends. If the return value of the recursively called FindGroup is not 1, the processing after step S34 is performed.
[0034]
In step S22 of FIG. 7, when the subroutine FindGroup is called with the management information of the group α and the management information of the group β as arguments, first, the identifier of the group α is compared with the identifier of the group β (step S31). As shown in FIG. 6, the identifiers of the groups α and β are 1 and 2, respectively, and they are different values. Therefore, the management information of the member b at the head of the lower layer of the group β which is the insertion data is extracted next (step S32).
[0035]
Next, it is checked whether or not the member b can own the lower layer (step S33). Since the child pointer is not stored in the management information of the member b and it is known that the member b cannot own the lower layer, it is determined whether or not all the data in the lower layer of the group β has been checked (step S34). ). This determination is made by checking whether the pointer after the member b points to the data. Since the pointer after the member b points to the member c, it is known that there is a member c which has not been checked yet in the lower layer of the group β, and its management information is extracted (step S35).
[0036]
Next, it is checked whether or not the member c can own the lower layer (step S33). However, since the member c cannot own the lower layer, it is checked whether or not the pointer after the member c points to the data (step S34). Since the pointer after the member c points to the group α which is the next data, the management information is taken out (step S35).
[0037]
Next, it is checked whether the group α can own a lower layer (step S33). The child pointer of the group α points to the member a, and it is known that the group α can own the lower layer. Therefore, the management information of the group α passed as an argument and the management information of the extracted group α are used as arguments. Call FindGroup recursively (step S37). The FindGroup called recursively extracts the respective identifiers from the two pieces of management information and compares them (step S31). In this case, since the two pieces of management information are both management information of the group α, their identifiers are both 1. Therefore, since the two identifiers have the same value, the return value 1 is returned to the call source FindGroup (step S39).
[0038]
On the other hand, the call source FindGroup sets the return value to 1 (step S39) because the recursively called FindGroup returned a return value of 1 (step S38), and returns the control to the caller's data insertion process. return.
[0039]
Here, since the return value of the first called FindGroup is 1 (step S23), the process ends without performing the process of inserting the group β below the group α. Thus, the insertion of the group β having the group α in the lower layer below the group α is prohibited, and the formation of an infinite hierarchy can be prevented.
[0040]
In FIG. 7, when the return value of FindGroup is 1 in step S23, the flow is such that the data insertion is always prohibited. However, a step similar to step S14 in FIG. 3 is provided to determine whether to insert data. May be inquired of the user. This allows the user to indicate whether to allow an infinite hierarchy data structure.
[0041]
In the above embodiment, a method is used in which the management information of the data in the lower layer is extracted using the child pointer of the management information, the value of the identifier is checked, and the data structure is determined. However, if the management information has information indicating the parent in the upper layer of the data, the management information of the parent can be sequentially extracted to determine the data structure.
[0042]
FIG. 9 is a flowchart of a process in which the CPU 1 searches the hierarchical structure data upward, determines its structure, and inserts data. When the process is started in FIG. 9, first, the CPU 1 receives an instruction from the user to insert the second data below the first data constituting the hierarchical structure data (step S41). Next, it is checked whether or not the identifier of the second data matches any of the identifiers of the first data and higher-order data (step S42). If the identifier does not match any data identifier, the second data is inserted below the first data (step S43), and the process ends.
[0043]
If any of the identifiers of the first data and higher data match the identifiers of the second data, the user is notified through the input / output device 3 to that effect and whether or not to insert the data. (Step S44). Then, if the user permits the data insertion, the second data is inserted below the first data (step S43), and if not, the process is terminated as it is.
[0044]
When there is data having the same identifier as the identifier of the second data as the insertion data in the hierarchy above the first data as the insertion destination data, the same data structure is repeated in the vertical direction by performing the data insertion. , Resulting in an infinite hierarchy. In the data insertion process of FIG. 9, the user can prohibit data insertion in such a case.
[0045]
FIG. 10 shows a format of data management information when performing the data insertion processing as shown in FIG. In FIG. 10, a name, an identifier, a child pointer, a front pointer, a rear pointer, and a real pointer are the same as those in FIG. The parent pointer is a pointer indicating management information of the parent data of the data, and is set so as not to point to anything at the highest data (root) of the hierarchical structure. By repeating this parent pointer in order, it is possible to extract the management information of the data in the hierarchy higher than the insertion destination data.
[0046]
【The invention's effect】
According to the present invention, it is possible to automatically determine the structure of data managed by a chain. As a result, it is possible to prevent the formation of an infinite hierarchy that can occur when data having a hierarchical structure is manipulated, thereby simplifying the hierarchical structure and greatly contributing to speeding up data processing.
[Brief description of the drawings]
FIG. 1 is a diagram illustrating the principle of the present invention.
FIG. 2 is a system configuration diagram of an embodiment.
FIG. 3 is a flowchart of a data insertion process by a downward search.
FIG. 4 is a diagram showing hierarchical structure data according to the embodiment.
FIG. 5 is a diagram showing a format of data management information.
FIG. 6 illustrates an example of data management information.
FIG. 7 is a detailed flowchart of a data insertion process.
FIG. 8 is a flowchart of a subroutine.
FIG. 9 is a flowchart of a data insertion process by an upward search.
FIG. 10 is a diagram showing a format of management information of data having a parent pointer.
FIG. 11 is a diagram showing an example of hierarchical structure data.
FIG. 12 is a diagram illustrating an example of data insertion that does not result in an infinite hierarchy.
FIG. 13 is a diagram illustrating an example of data insertion at an infinite hierarchy.
[Explanation of symbols]
1 CPU
2 Data storage unit 3 I / O device 4 Bus

Claims (6)

A data structure determination device for operating a hierarchical structure data composed of two or more data having a vertical relationship,
Data storage means for storing data to be each element of the hierarchical structure data to which an identifier has been added ,
In the vertical data string formed by inserting the second data below the first data, it is checked whether the second data can possess lower third data, and the second data is checked. If the third data can own the third data, it is checked whether the identifier of the first data matches the identifier of one of the second data and data lower than the second data. If the identifier of the data of the first agrees with the identifier of the one data, determines that the insertion of the corresponding second data under the first data infinite hierarchy occurs, the first data If the identifier does not match the identifier of any of the second data and data lower than the second data, the second data may be inserted below the first data indefinitely. It is determined that no hierarchical structure occurs, and the second data is If you can not own a third data, and the process of determining means said first endless hierarchy be inserted the second data under the data does not occur
Data structure determination apparatus comprising: a. The data storage unit stores management information including a child pointer in association with data serving as each element of the hierarchical structure data,
  The processing unit refers to the management information and determines whether the second data can own the third data, and determines whether the identifier of the first data is the second data and the second data. 2. The data structure judging device according to claim 1, wherein it is checked whether or not the data matches the identifier of one of the data lower than the data. The processing means does not insert the second data below the first data when determining that an infinite hierarchical structure occurs, and determines that the infinite hierarchical structure does not occur when determining that the infinite hierarchical structure does not occur . The data structure determination device according to claim 1, wherein the data structure determination device is configured to insert the second data below. When the identifier of the first data does not match the identifier of the second data , the processing means checks whether or not the third data can possess lower fourth data. There if own data of said 4, the identifier of the first data, to see if it matches one of the data identifiers of the data and the third lower data than the third, the first data identifier, if they match one of the data identifiers of the lower data from the data of the third data and the third, and judging infinite hierarchical structure results The data structure determination device according to claim 1 . When the third data cannot own the fourth data , the processing unit checks whether there is data that can own lower data in the same hierarchy as the third data, and 5. The data structure determination device according to claim 4 , wherein if there is no data that can be generated, it is determined that an infinite hierarchical structure does not occur . When the processing unit determines that an infinite hierarchical structure occurs , the processing unit further includes an input / output unit that inquires of a user whether to insert the second data below the first data, and receives an answer to the inquiry,
The processing means does not insert the second data below the first data when the input / output means receives a response indicating that the input / output means does not insert data, and the input / output means performs data insertion. 2. The data structure determination device according to claim 1, wherein when receiving a response to the effect, the second data is inserted below the first data .

Images