Data storage system with set lists which contain elements associated with parents for defining a logical hierarchy and general record pointers identifying specific data sets

• US 5,454,101 A
• Filed: 09/15/1992
• Issued: 09/26/1995
• Est. Priority Date: 09/15/1992
• Status: Expired due to Term

• Current Assignee: Universal Firmware Industries Limited
• Original Assignee: Universal Firmware Industries Limited
• Inventors: Ahmadi, Babak, Mackay, Duncan C.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US07/945,266
• Time in Patent Office: 1,106 Days
• Field of Search: 395/600, 364/282.3, 364/282.4, 364/282.1, 364/283.1, 364/962, 364/962.1, 364/963, 364/963.4, 364/963.5, 364/974, 364/974.3, 364/974.7, 364/283.2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

In a computer having one or more secondary storage devices attached thereto, a Finite Data Environment Processor (FDEP) manages Data Sets residing on the secondary storage devices and in memory using Set Lists (SLs) and General Record Pointers (GRPs). The Data Sets contain either data or logical organizational information. The Set Lists comprise Data Sets organized into a hierarchy by listing a identifier for each of the data sets with a corresponding identifier for the logical parent of that data set. These set lists are also data sets and can be identified as child or parent in a set list. The General Record Pointers identify information in terms of Data Sets and records within them. Using the principal idea that a Data Set is uniquely identifiable, the present invention eliminates problems normally associated with referencing the location of data after the data has been moved.

Claims

1. An apparatus for managing data in a computer having one or more memory devices characterized by:

(a) one or more Data Sets stored in one or more of the memory devices, wherein both data and logical organization are recorded in the Data Sets;

(b) one or more Set Lists stored in one or more Data Sets, wherein a Set List comprises a list of Set List Elements, and the Set List Elements are stored in an arbitrary order in any of the Set Lists;

(c) each Set List Element comprising;

(1) a Self Identification used to identify the Set List Element and an associated Data Set;

(2) an identification of a parent Set List Element in any of the Set Lists for defining a logical hierarchy of the Set List Elements, wherein a predefined value for the identification of the parent Set List Element indicates that the Set List Element is a root Set List Element in the logical hierarchy, and a value other than the predefined value for the identification of the parent Set List Element indicates the Set List Element is logically subordinate to the parent Set List Element in the logical hierarchy;

(d) means for manipulating the logical hierarchy by modifying the identifications of the parent Set List Elements;

(e) one or more General Record Pointers stored in one or more of the memory devices, wherein each General Record Pointer identifies a specific one of the Data Sets; and

(f) means for accessing the Data Sets, further comprising means for searching the Set Lists to locate a desired Set List Element therein having a Self Identification matching a specified General Record Pointer.

2. The apparatus as defined in claim 1, wherein each General Record Pointer comprises an identification of a site and a value unique for the site.

3. The apparatus as defined in claim 1, further characterized by means for creating a new Data Set within the logical hierarchy, comprising means for generating and assigning a unique General Record Pointer to the new Data Set, means for allocating a storage location for physical data associated with the new Data Set, means for creating a new Set List Element containing the General Record Pointer as its Self Identification, and means for recording the storage location in the newly created Set List Element.

4. The apparatus as defined in claim 1, further characterized by means for deleting an existing Data Set from the logical hierarchy by setting an indicator in the Set List Element associated therewith to a deleted state.

5. The apparatus as defined in claim 1, wherein the means for manipulating is characterized by means for moving a Data Set in the logical hierarchy by altering the identification of the parent Set List Element stored in the Set List Element associated with the Data Set.

6. The apparatus as defined in claim 1, wherein the mean for manipulating is characterized by means for promoting a Data Set within the logical hierarchy by replacing the identification of the parent Set List Element in the Set List Element associated with the Data Set with an identification of a parent Set List Element stored in the parent Set List Element.

7. The apparatus as defined in claim 1, wherein the means for manipulating is characterized by means for inserting a Data Set within the logical hierarchy to a position between a subordinate Set List Element and a superior Set List Element, further comprising means for creating a new Set List Element, means for recording a General Record Pointer associated with the Data Set as the Self Identification in the new Set List Element, means for recording the Self Identification of the superior Set List Element as the identification of the parent Set List Element in the new Set List Element, and means for recording the Self Identification of the new Set List Element as the identification of the parent Set List Element in the subordinate Set List Element.

8. The apparatus as defined in claim 1, further characterized by means for storing a Set List Element in an arbitrary one of the Set Lists, wherein the Set List Element contains an identification of a parent Set List Element residing in another Set List.

9. The apparatus as defined in claim 1, further characterized by means for locating a specific Set List Element by searching all Set Lists, regardless of the logical hierarchies defined by the Set List Elements.

10. The apparatus as defined in claim 1, wherein a Data Set is identified solely by a General Record Pointer, the apparatus further characterized by means for locating a desired Data Set by arbitrarily selecting Set Lists, means for arbitrarily searching Set List Elements within the selected Set Lists to identify a Set List Element with a Self Identification matching the General Record Pointer for the desired Data Set, wherein the identified Set List Element contains a storage location for the desired Data Set.

11. The apparatus as defined in claim 1, further characterized by means for associating a plurality of Set List Elements with a given Data Set, wherein each of the Set List Elements are in a different logical hierarchy.

12. The apparatus as defined in claim 1, further characterized by descendant view means for identifying a starting Set List Element and for locating one or more subordinate Set List Elements having an identification of a parent Set List Element matching the Self Identification of the starting Set List Element, further comprising means for repeating the means for identifying and means for locating using the matching Set List Elements for all subordinate Set List Elements.

13. The apparatus as defined in claim 1, further characterized by ancestor view means for identifying a starting Set List Element and for locating one or more Set List Elements having a Self Identification matching an identification of a parent Set List Element of the starting Set List Element, further comprising means for repeating the means for identifying and means for locating using the matching Set List Elements until a root Set List Element is encountered.

14. The apparatus as defined in claim 1, wherein the means for manipulating is characterized by means for copying a Data Set and all immediate subordinate Data Sets by copying the Set List Elements associated therewith.

15. The apparatus as defined in claim 14, wherein the means for copying is further characterized by:

(i) means for creating a new Set List Element associated with the copied Data Set;

(ii) means for generating a new General Record Pointer and recording it as a Self Identification in the copied Set List Element;

(iii) means for duplicating the contents of the copied Data Set to a new Data Set and identifying the Data Set with the new General Record Pointer;

(iv) means for replacing the storage location in the new Set List Element with a storage location for the new Data Set; and

(v) means for repeating the means for creating (i) through the means for replacing (iv) for subordinate Set List Elements.

16. The apparatus as defined in claim 1, further characterized by means for associating a plurality of Set List Elements with a given Data Set, wherein each of the Set List Elements are in a different position in the logical hierarchy.

17. The apparatus as defined in claim 16, wherein each Set List Element associated with the Data Set has an identical Self Identification.

18. The apparatus as defined in claim 16, wherein each Set List Element associated with the Data Set has a different identification of a parent Set List Element thereby resulting in the different position in the logical hierarchy.

19. The apparatus as defined in claim 1, further characterized by means for detecting erroneous control data.

20. The apparatus as defined in claim 19, wherein the means for detecting is characterized by means for detecting corruption in the Set Lists and Set List Elements.

21. The apparatus as defined in claim 20, wherein the means for detecting is characterized by means for searching a Set List for a desired Set List Element and means for performing a checksum test on the desired Set List Element to establish a test result, wherein a match between the test result and a checksum value stored in the desired Set List Element indicates a lack of corruption.

22. The apparatus as defined in claim 20, wherein the means for detecting is characterized by means for searching a Set List for a desired Set List Element and means for searching for a Set List Element corresponding to the identification of the parent Set List Element stored in the desired Set List Element, wherein a failure to find the parent Set List Element indicates corruption.

23. The apparatus as defined in claim 20, wherein the means for detecting is characterized by means for searching a Set List for a desired Set List Element and means for performing a content validity test on the associated Data Set to establish a test result, wherein a match between the test result and a checksum value stored in the Set List Element indicates a lack of corruption.

24. The apparatus as defined in claim 20, wherein the means for detecting corruption is characterized by means for correcting Set List Element corruption, comprising:

(i) means for creating a new Set List Element;

(ii) means for generating a new General Record Pointer and recording it as the Self Identification of the new Set List Element;

(iii) means for recording the storage location of the associated Data Set in the new Set List Element; and

(iv) means for identifying the new Set List Element as a recovered Set List Element.

25. The apparatus as defined in claim 1, further comprising a plurality of sites, each site having one or more computers and memory devices situated thereat, wherein each site is identified by a unique site identification.

26. The apparatus as defined in claim 25, further characterized by means for uniquely identifying any given Data Set across any number of sites.

27. The apparatus as defined in claim 25, further characterized by means for locating a Data Set beyond the confines of a single site, further comprising means for searching for the Data Set beginning at a starting site and proceeding to other sites.

28. The apparatus as defined in claim 25, further characterized by means for moving a Data Set within the logical hierarchy by altering the identification of the parent Set List Element associated therewith, wherein the parent Set List Element exists in a Set List at a different site.

29. The apparatus as defined in claim 25, further characterized by means of copying a Data Set within the logical hierarchy from a first site to a different site.

30. The apparatus as defined in claim 25, further comprising means for storing the Data Sets identified within a given Set List in differing ones of the memory devices.

31. The apparatus as defined in claim 1, further comprising means for storing associated Data Sets and Set List Elements in differing ones of the memory devices.

32. The apparatus as defined in claim 31, wherein the means for storing comprises:

(i) means for selecting a first memory device for storing a Data Set;

(ii) means for determining that the first memory device does not contain sufficient storage for the Data Set;

(iii) means for selecting a second memory device for storing the Data Set;

(iv) means for repeating the means for selecting (i) through the means for selecting (iii) until a memory device with sufficient memory is found; and

(v) means for updating the storage location contained in the Set List Element associated with the Data Set to reflect the selected memory device.

33. The apparatus as defined in claim 1, further comprising a Finite Data Environment Processor performed by the computer, the Finite Data Environment Processor comprising means for maintaining a Finite Data List containing one or more Finite Data List Elements, wherein each Finite Data List Element identifies a storage location of one of the Set Lists, and the Finite Data List Elements are stored in an arbitrary order in the Finite Data List.

34. The apparatus as defined in claim 33, further comprising means for locating a desired Data Set by arbitrarily selecting Set Lists identified by the Finite Data List Elements.

35. The apparatus as defined in claim 33, further comprising means for detecting erroneous control data.

36. The apparatus as defined in claim 35, wherein the means for detecting comprises means for detecting corruption in the Finite Data List and Finite Data List Elements.

37. The apparatus as defined in claim 36, wherein the means for detecting corruption comprises means for searching the Finite Data List for a Finite Data List Element and means for performing a checksum test on each Finite Data List Element to establish a test result, wherein a match between the test result and a checksum value stored in the Finite Data List Element indicates a lack of corruption.

38. The apparatus as defined in claim 36, wherein the means for detecting corruption comprises means for searching the Finite Data List for a Finite Data List Element and means for performing a Set List content validity test, wherein the Set List is loaded and a checksum test performed on the contents thereof to establish a test result, wherein a match between the test result and a checksum value found in the Finite Data List Element indicates a lack of corruption.

39. The apparatus as defined in claim 36, wherein the means for detecting corruption comprises means for correcting Finite Data List Element corruption, comprising:

(i) means for creating a new Finite Data List Element;

(ii) means for generating a new General Record Pointer and recording it in a Self Identification for the Finite Data List Element;

(iii) means for recording the storage location for the Data Set in the Finite Data List Element; and

(iv) means for identifying the Finite Data List Element as a recovered Finite Data List Element.