Method and apparatus for virtual memory mapping and transaction management in an object-oriented database system

• US 5,649,139 A
• Filed: 05/31/1995
• Issued: 07/15/1997
• Est. Priority Date: 03/22/1991
• Status: Expired due to Term

• Current Assignee: Progress Software Corporation
• Original Assignee: eXcelon Corp. (Progress Software Corporation)
• Inventors: Weinreb, Daniel L., Haradhvala, Sam J.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Tran, Denise
• Application Number:
  US08/456,237
• Time in Patent Office: 776 Days
• Field of Search: 395/403, 395/481, 395/490, 395/412-416, 395/183.01, 395/600, 364/246.03, 364/285.3
• US Class Current: 711/202
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 9/4493 Object persistence
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

An apparatus and method are provided for virtual memory mapping and transaction management in an object-oriented database system having permanent storage for storing data in at least one database, at least one cache memory for temporarily storing data, and a processing unit which runs application programs which request data using virtual addresses. The system performs data transfers in response to memory faults resulting from requested data not being available at specified virtual addressed and performs mapping of data in cache memory. The data in the database may include pointers containing persistent addresses, which pointers are relocated between persistent addresses and virtual addresses. When a data request is made, either for read or write, from a given client computer in a system, other client computers in the system are queried to determine if the requested data is cached and/or locked in a manner inconsistent with the requested use, and the inconsistent caching is downgraded or the transfer delayed until such downgrading can be performed.

Claims

1. An apparatus for virtual memory mapping for a computer system having at least one permanent storage device for storing data, a virtual memory system defining a virtual address space and including at least one cache memory for temporarily storing data addressed by physical addresses, and a processing unit, the processing unit including means for requesting data utilizing a virtual address to access said data in the at least one cache memory, the virtual memory system including means for mapping virtual addresses to physical addresses, and means for detecting when access to data requested by the means for requesting is not permitted at the virtual address utilized by the means for requesting, said apparatus comprising:

means, operative in response to a detection by said means for detecting that access to the requested data is not permitted, for determining if the requested data is in the at least one cache memory,

means for transferring the requested data from the at least one permanent storage device to the at least one cache memory, operative in response to a determination by said means for determining that the requested data is not in the at least one cache memory, and

means, operative in response to a determination that the requested data is in the at least one cache memory, for instructing the means for mapping to map the virtual address of the requested data to the physical address of the requested data in the at least one cache memory and for permitting access to the requested data.

2. An apparatus as set forth in claim 1, wherein the means for detecting detects when a virtual address utilized to access data requested by the means for requesting is not mapped to a physical address.

3. An apparatus as set forth in claim 2, wherein said requested data includes a pointer containing a persistent address, the apparatus further comprising means for relocating inbound the persistent address to a virtual address.

4. An apparatus as set forth in claim 3, further comprising:

means for determining whether the virtual address utilized by the means for requesting is assigned to data, and

means for signalling an error to the means for requesting, in response to a determination that the virtual address utilized is not assigned to data.

5. An apparatus as set forth in claim 4, wherein the data resides in a database, the apparatus further comprising:

means for determining if virtual addresses have been assigned to a selected portion of the database, which selected portion contains the requested data, and

means for assigning virtual addresses for said selected portion of the database if such virtual addresses are not assigned.

6. An apparatus as set forth in claim 5 wherein the processing unit runs application programs requiring data from the database, and wherein an application program may involve a transaction, and including means, operative when the transaction commits, for relocating outbound all data which was relocated inbound during the transaction, and for unmapping all mapped virtual address which were mapped to physical addresses during the transaction, and for cancelling all virtual address assignments made during the transaction.

7. An apparatus as set forth in claim 6 including means for locking a portion of the database at a client computer when data from the portion is utilized in a transaction at the client computer.

8. An apparatus as set forth in claim 7 wherein said means for relocating, unmapping and cancelling, operative when a transaction commits, further includes means for unlocking the locked portion of the database.

9. An apparatus as set forth in claim 1 wherein a request for data may be one of a read request and a write request, wherein the database is divided into segments, each segment containing at least one page and wherein said means for transferring transfers a page containing the requested data wherein the apparatus further comprises:

means, operative in response to a transfer of a page in response to a read request for the page, for encaching the page for read and for locking the page for read at a client computer, and means, operative in response to a transfer of a page in response to a write request for the page, for encaching the page for write and for locking the page for write at the client computer.

10. An apparatus as set forth in claim 9 wherein the database system has a plurality of client computers and a server computer for each of the at least one permanent storage means, wherein the apparatus further comprises:

second means, operative in response to a request for data from the at least one database for read access from the means for requesting of a first client computer, for detecting if the requested data is in the cache memory of a second client computer for write access,

means, responsive to a detection by the means for detecting that the requested data is in the cache memory of the second client computer, for instructing the second client computer to downgrade a cached state of the data to read access, and

means for permitting the means for transferring to transfer the requested data to the first client computer.

11. An apparatus as set forth in claim 10 wherein each server computer has an ownership table having an entry for each page of the at least one permanent storage device of the server computer which is encached at a client computer, said entry for a page indicating which client computers have the page encached and whether the page is encached for one of read and write access, and wherein the second means for detecting utilizes the ownership table to determine if the page is encached at a client computer for write.

12. An apparatus as set forth in claim 11 further comprising:

means for querying the client computer having a page encached for write to determine if the page is locked for write, and

means, responsive to a response from the queried client computer that the page is not locked for write, for downgrading the entry for the page in the ownership table from indicating encached for write to indicate encached for read and for permitting the means for transferring to transfer the page to the cache memory of the first client computer.

13. An apparatus as set forth in claim 12, wherein the database system has an application program involving at least one transaction, wherein the apparatus further comprises:

means, responsive to a response from the queried client computer that the page is locked for write, for deferring further action until the transaction being run at the queried client computer commits, said means for downgrading and for permitting being operative when the transaction performed by the queried client computer commits.

14. An apparatus as set forth in claim 13 wherein each client computer has a cache directory having an entry for each page in the corresponding cache memory, which entry indicates a cached state and a locked state of the page wherein the apparatus further comprises:

means, responsive to a query whether the cached state of a page is locked write, for looking up the page in the cache directory of the queried client computer to determine if the page is locked for write.

15. An apparatus as set forth in claim 14 wherein the queried client computer includes means, responsive to a determination that the page is not locked for write for downgrading the cached state of the entry for the page in the cache directory from indicating encached for write to indicate encached for read, and for replying to the querying server computer that the page is not locked for write.

16. An apparatus as set forth in claim 15, wherein the queried client computer includes means, responsive to a determination that the page is locked for write, for marking the entry for the page in the cache directory to be downgraded when the transaction commits, said means for downgrading and replying being operative when the transaction being run on the queried client computer commits.

17. An apparatus as set forth in claim 9 wherein the computer system has a plurality of client computers and a server computer for each permanent storage means, wherein the apparatus further comprises:

means, responsive to a request for data from a database for write access from the means for requesting of a first client computer, for detecting if the requested data is in the cache memory of a second client computer,

means, responsive to a detection by the means for detecting that the requested data is in the cache memory of the second client computer, for instructing the second client computer to remove the data from its cache memory, and

means, for transferring the requested data to the first client computer.

18. An apparatus as set forth in claim 17, wherein each server computer has an ownership table having an entry for each page of the permanent storage means of the server computer which is encached at a client computer, said entry for a page indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the means for detecting utilizes the ownership table to determine if the page is encached.

19. An apparatus as set forth in claim 18, further comprising:

means for querying each client computer having the page encached to determine if the page is also locked,

means, responsive to a reply from all queried client computers that the page is not locked, for removing entries for the page from the ownership table, for making an entry for the requesting client computer in the ownership table, and for permitting the means for transferring to transfer the page to the cache memory of the requesting client computer.

20. An apparatus as set forth in claim 19 wherein the database system has an application program involving at least one transaction wherein the apparatus further comprises:

means, responsive to a response from at least one queried client computer that the page is locked, for deferring further action until the at least one transaction being run on the at least one queried client computer commits, said means for removing all entries, and for making an entry and for permitting being operative when the at least one transaction being run on the at least one queried client computer commit.

21. An apparatus as set forth in claim 20 wherein each client computer has a cache directory having an entry for each page in the corresponding cache memory, which entry indicates a cached state and a locked state of the page wherein the apparatus further comprises:

means, operative in response to a query as to whether a page is locked, for looking up the page in the cache directory of the queried client computer to determine if the page is locked.

22. An apparatus as set forth in claim 21 wherein the queried client computer includes means, responsive to a determination that the page is unlocked, for removing the page from the cache memory of the client computer, for removing the entry for the page from the cache directory, and for replying to the querying server computer that the page is not locked.

23. An apparatus as set forth in claim 22 wherein the queried client computer includes means, responsive to a determination that the page is locked, for marking the entry for the page in the cache directory to be evicted when the transaction commits, and for replying to the querying server computer that the page is locked, said means for removing the page, and for removing the entry, and for replying, being operative when the transaction being run on the queried client computer commits.

24. An apparatus as set forth in claim 3 wherein the database system has a computer for each of the at least one permanent storage means, wherein each database is divided into segments, each containing at least one page, and wherein each segment of a database is divided into a data segment and an information segment.

25. An apparatus as set forth in claim 24 wherein a plurality of different types of objects may be stored in a data segment, and wherein the information segment for each data segment contains a tag table having a tag entry for each object in the data segment, each tag entry identifying at least the object type for the corresponding object.

26. An apparatus as set forth in claim 25 wherein a data segment may contain at least one of a single object, a vector of multiple objects and free space, wherein the tag entry for a single object contains a type code for the object, the tag entry for a vector of objects contains a type code for one of the multiple objects and a length field indicating a number of objects in the vector, and the tag entry for free space has a type code and a length field.

27. An apparatus as set forth in claim 26 wherein the database system has an application program involving at least one transaction, and wherein objects may be created during a transaction, an object having an object type indication and an indication of a database and a segment for the object wherein the apparatus further comprises:

means for determining the size of the object from the object type indication,

means for searching the tag table to find free space of suitable size for the object,

means for inserting a tag entry for the object in place of any tag entry for free space if suitable free space is found,

means for inserting a tag entry for free space of shorter size if free space remains after insertion of the object,

means for creating a tag entry at the end of the tag table if suitable free space is not found, and

means for generating a virtual address for the object.

28. An apparatus as set forth in claim 27, wherein objects may be deleted during a transaction, and further comprising:

means for finding a tag entry in the tag table for a deleted object,

means for determining the size of the deleted object, and

means for converting the tag entry for the deleted object to a tag entry for free space of size equal to the determined size of the deleted object.

29. An apparatus as set forth in claim 28 further comprising:

means for determining if a tag entry preceding or following the tag entry for free space for the deleted object in the tag table is a tag entry for free space, and

means for merging adjacent tag entries for free space into a single tag entry for free space of size equal to the sum of the sizes of the merged tag entries.

30. An apparatus as set forth in claim 25 wherein each object in the at least one database may contain at least one pointer at a selected offset location in the object which points to a persistent address in the at least one database, and wherein each database has a schema associated therewith, the schema containing an entry for each object type present in the database, each schema entry containing a field indicating a size of the object type, and an instruction indicating an offset location in the object for each pointer for the object type.

31. An apparatus as set forth in claim 30 further comprising:

means for transferring the schema for a database to a client computer before the means for mapping at the client computer performs any mapping for data from the database, and wherein the means for transferring includes means for transferring page data from both a data segment and an information segment corresponding to the data segment.

32. An apparatus as set forth in claim 31 wherein the database system has an application program involving at least one transaction, and wherein the apparatus further comprises:

means, operative when a transaction commits, for relocating outbound data which was relocated inbound during the transaction;

wherein means for relocating inbound and the means for relocating outbound each include means for determining an object type for a selected object from the tag table transferred with a page, means for obtaining a description of the selected object from the schema using the object type from the tag table, and means for retrieving a corresponding pointer, utilizing each schema instruction for the object type,

wherein the means for relocating inbound includes means for converting the persistent address of each pointer to a corresponding virtual address, and

wherein the means for relocating outbound includes means for converting the virtual address of each pointer to the corresponding persistent address.

33. An apparatus as set forth in claim 24 further comprising:

a persistent relocation map (PRM) in an information segment of a database, which PRM indicates a beginning persistent address for a selected database portion and having a given segment and offset,

said means for transferring including means for transferring the PRM, and

means for determining a persistent address corresponding to a given database, segment and offset from the PRM.

34. An apparatus as set forth in claim 33 further comprising:

a virtual address map at least one client computer for indicating a beginning virtual address for a selected database portion and having a given offset, and

means for determining a virtual address corresponding to a given database, segment and offset from the virtual address map.

35. An apparatus as set forth in claim 34 wherein the database system has an application program involving at least one transaction, and wherein the apparatus further comprises:

means, operative when a transaction commits, for relocating outbound data which was relocated inbound during the transaction, and

means for relocating inbound including means for determining a database, segment and offset for a given persistent page address from the persistent relocation map, and means for determining the corresponding virtual page address for the determined database, segment and offset from the virtual address map, and

wherein the means for relocating outbound includes means for determining a database, segment and offset for a given virtual page address from the virtual address map, and means for determining a corresponding persistent address from the determined database, segment and offset from the virtual address map.

36. An apparatus as set forth in claim 35 further including:

means for verifying that the persistent relocation map for the segment containing requested data has been transferred to the client computer,

means for examining each PRM entry in turn to determine if there is a corresponding virtual address map entry, and

means for creating a new virtual address map entry for each selected database portion for which a VAM entry does not exist.

37. An apparatus as set forth in claim 1 wherein the means for detecting that access to the requested data is not permitted is operative in response to one of an instruction indicating access to data is not permitted and a program fault resulting from an unsuccessful attempt to one of read and write data.

71. The apparatus as set forth in claim 1, wherein the database defines an address space which is larger than the virtual address space.

38. A method for virtual memory mapping and transaction management for a database system having at least one permanent storage means for storing data in at least one database, a virtual memory system defining a virtual address space and including at least one cache memory for temporarily storing data addressed by physical addresses and means for mapping virtual addresses to physical addresses, and a processing unit, the processing unit including means for requesting data utilizing a virtual address to access said data in the at least one cache memory, said method comprising the steps of:

detecting, using the virtual memory system, when access to data requested by the means for requesting is not permitted at the virtual address utilized by the means for requesting,

determining if the requested data is in the at least one cache memory in response to a detection that access to the requested data is not permitted,

transferring the requested data from the at least one permanent storage means to the at least one cache memory, when the requested data is not in the at least one cache memory,

instructing the means for mapping to map the virtual address of the requested data to the physical address of the requested data in the at least one cache memory, and

permitting access to the requested data.

39. A method as set forth in claim 38, wherein the step of detecting comprises detecting whether the virtual address utilized to access the data requested by the means for requesting is mapped to a physical address.

40. A method as set forth in claim 39, wherein the requested data includes pointers containing persistent addresses, and the method further comprises the step of relocating inbound the pointers in the requested data from persistent addresses to virtual addresses.

41. A method as set forth in claim 40, further comprising the steps of:

determining whether the virtual address utilized by the means for requesting is assigned to a portion of the at least one database, and

signalling an error to the means for requesting in response to a determination that the virtual address utilized is not assigned to a portion of the at least one database.

42. A method as set forth in claim 41, further comprising the steps of:

determining if virtual addresses have been assigned to a selected portion of a database, which selected portion contains the requested data, and

assigning virtual addresses for said selected portion if such virtual addresses are not assigned.

43. A method as set forth in claim 42 wherein the processing unit runs application programs requiring data from said at least one database, and wherein an application program may involve one or more transactions, said method further comprising the steps, performed when a transaction of the one or more transactions commits, of:

relocating outbound all data which was relocated inbound during the transaction,

unmapping all physical addresses which were mapped during said transaction, and

cancelling all virtual address assignments made during the transaction.

44. A method as set forth in claim 43 including the step of locking a portion of the at least one database at a client computer when data from the portion is utilized in a transaction at the client computer.

45. A method as set forth in claim 44 further including the step of unlocking all portions of the at least one database which were locked during the transaction when the transaction commits.

46. A method as set forth in claim 38 wherein a request for data may be one of a read request and a write request, wherein a database is divided into segments, each segment containing one or more pages, and wherein the step of transferring transfers the page containing requested data, said method further comprising the steps of:

encaching a transferred page for read in response to a transfer for a read request and locking the page for read at a client computer, and

encaching a transferred page for write in response to a transfer for a write request and locking the page for write at the client computer.

47. A method as set forth in claim 46 wherein the database system has a plurality of client computers and a server computer for each of the at least one permanent storage means, said method further comprising the steps of:

detecting, in response to a request for data from a database for read access from the means for requesting of a first client computer, if the requested data is in the cache memory of a second client computer, and

instructing the second client computer, in response to a detection that the requested data is in the cache memory of the second client computer, to downgrade the encached state of the data to read access.

48. A method as set forth in claim 47 wherein each server computer has an ownership table having an entry for each page of the at least one permanent storage means of the server computer which is encached at the client computer, each entry for a page indicating which client computers have the page encached and whether the page is encached for one of read and write access, and wherein the step of detecting includes the step of utilizing the ownership table to determine if the page is encached for write access.

49. A method as set forth in claim 48 further comprising the steps of:

querying the client computer having the page encached for write to determine if the page is locked for write, and

downgrading the entry for the page in the ownership table from indicating encached for write to indicate encached for read in response to a response from the queried client computer that the page is not locked for write.

50. A method as set forth in claim 49, wherein an application program involves at least one transaction, said method further comprising the step of:

deferring further steps, in response to a response from the queried client computer that the page is locked for write, until the transaction being run at the queried client computer commits, the steps of downgrading and transferring being performed when the transaction performed by the queried client computer commits.

51. A method as set forth in claim 50 wherein each client computer has a cache directory having an entry for each page in the corresponding cache memory, which entry indicates a cached state and a locked state of the page, said method further comprising the step of:

looking up the page in the cache directory of the queried client computer to determine if the page is locked for write in response to a query of the locked state of the page.

52. A method as set forth in claim 51 further comprising the steps of:

downgrading the cached state of the entry for the page in the cache directory of the queried client computer from indicating encached for write to indicate encached for read in response to a determination that the page is not locked for write, and

replying to the querying server computer that the page is not locked for write.

53. A method as set forth in claim 52, including the steps of:

marking the entry for the page in the cache directory of the queried client computer to be downgraded when the transaction commits in response to a determination that the page is locked for write,

the steps of downgrading and replying being performed when the transaction being run on the queried client computer commits.

54. A method as set forth in claim 46 wherein the database system has a plurality of client computers and a server computer for each of the at least one permanent storage means, said method further comprising the steps of:

detecting if the requested data is in the cache memory of a second client computer in response to a request for data from a database for write access from the means for requesting of a first client computer; and

instructing the second client computer, in response to a detection that the requested data is in the cache memory of the second client computer, to remove the data from the cache memory of the second client computer.

55. A method as set forth in claim 54, wherein each server computer has an ownership table having an entry for each page of the permanent storage means of the server computer which is encached at a client computer, each entry for a page indicating which client computers have the page encached and whether the page is encached for one of read and write access, and wherein the step of detecting includes a step of determining if the page is encached utilizing the ownership table.

56. A method as set forth in claim 55 further comprising the steps of:

querying each client computer having the page encached to determine if the page is also locked,

removing all entries for the page from the ownership table in response to a reply from all queried client computers that the page is not locked, and

making an entry for the requesting client computer in the ownership table.

57. A method as set forth in claim 56 wherein the database system has an application program involving at least one transaction, said method further comprising the steps of:

deferring further action, in response to a response from at least one queried client computer that the page is locked, until the transactions being run on all said at least one queried client computers commit,

the steps of removing all entries, making an entry and for transferring the page being performed when the transactions being run on all queried client computers commit.

58. A method as set forth in claim 57 wherein each computer has a cache directory having an entry for each page in the corresponding cache memory, which entry indicates a cached state and a locked state of the page, the method further comprising the step of:

looking up the page in the cache directory of the queried client computer to determine if the page is locked in response to a query of the locked state of the page.

59. A method as set forth in claim 58 further comprising the steps of:

removing the page from the cache memory of the queried client computer in response to a determination that the page is in the cache memory,

removing the entry for the page from the cache directory, and

replying to the server computer that the page is not locked.

60. A method as set forth in claim 59 further comprising the steps of:

marking the entry for the page in the cache directory of the queried client computer to be evicted when the transaction commits in response to a determination that the page is locked, and

replying to the querying server computer that the page is locked, said steps of removing the page, removing the entry, and replying being performed when the transaction being run on the queried client computer commits.

61. A method as set forth in claim 38 wherein the database system includes an application program involving at least one transaction, and wherein objects may be created during a transaction, an object having an object type indication and an indication of a database and a segment of a database for the object, said method further comprising the steps of:

utilizing the object type indication of an object to determine the size of the object,

searching a tag table for free space tags to find free space of suitable size for the object,

inserting an object tag for the object in place of the free space tag if suitable free space is found,

inserting a free space tag of shorter size if free space remains after insertion of the object,

creating an object tag at the end of the tag table if suitable free space is not found, and

generating a virtual address for the object.

62. A method as set forth in claim 61 wherein objects may be deleted during a transaction, said method further comprising the steps of:

finding a tag in a tag table for a deleted object, determining a size of the deleted object, and

converting the tag for the deleted object to a free space tag of a size equal to the determined size of the deleted object.

63. An method as set forth in claim 62 further comprising the steps of:

determining if a tag preceding or following the free space tag is a free space tag, and

merging adjacent free space tags into a single free space tag of a size equal to the sum of sizes of the merged tags.

64. A method as forth in claim 40 including the steps of:

transferring a schema for a database to a client computer before relocating data from the database at the client computer, and

wherein the step of transferring includes the step of transferring page data from both a data segment and a corresponding information segment.

65. A method as set forth in claim 64 wherein the database system includes an application program involving at least one transaction, said method further comprising the steps of:

relocating outbound, when a transaction commits, all data which was relocated inbound during the transaction,

wherein the step of relocating inbound and the step of relocating outbound each include the step of determining an object type for a selected object utilizing a page table transferred with a page,

obtaining a description of the selected object from the schema, utilizing the object type from a tag table, and

wherein the step of relocating inbound includes a step of converting a persistent address of each pointer to a corresponding virtual address, and

wherein the step of relocating outbound includes a step of converting a virtual address of each pointer to a corresponding persistent address.

66. A method as set forth in claim 40 wherein the database system includes a persistent relocation map (PRM) in an information segment of a database, which PRM indicates a persistent address of a beginning of a selected database portion and has a given segment and offset, wherein the step of transferring includes a step of transferring the PRM, said method further including a step of determining a persistent address corresponding to a given database, segment and offset utilizing the PRM.

67. A method as set forth in claim 66 wherein the database system includes a virtual address map (VAM) at at least one client computer, which virtual address map indicates a beginning virtual address for a selected database portion and having a given segment and offset, said method further including a step of determining a virtual address corresponding to a given database, segment and offset utilizing the VAM.

68. A method as set forth in claim 67 wherein the database system includes an application program involving at least one transaction, said method further comprising the steps of:

relocating outbound, when a transaction commits, all data which was relocated inbound during the transaction,

wherein the step of relocating inbound comprises the steps of determining a database, segment and offset for a given persistent page address utilizing the PRM, and determining a corresponding virtual page address from the determined database, segment and offset, utilizing the VAM; and

wherein the step of relocating outbound includes the steps of determining a database, segment and offset for a given virtual page address utilizing the VAM, and determining a corresponding persistent page address from the determined database, segment and offset utilizing the PRM.

69. A method as forth in claim 68 wherein said step of assigning includes the steps of:

verifying that the PRM for the segment containing requested data has been transferred to the client computer,

determining if there is a corresponding VAM entry for each PRM entry, and

creating a new VAM entry, for each selected database portion for which it is determined that a VAM entry does not exist.

70. A method as set forth in claim 38 wherein a step of detecting that data is not available includes detecting one of whether data is not available and whether a program fault resulted from an unsuccessful attempt to access data.

72. An apparatus for virtual memory mapping for a computer system having a permanent storage device for storing data, a virtual memory system defining a virtual address space and including a cache memory for temporarily storing data addressed by physical addresses, and a processing unit, the processing unit including a data requesting mechanism that requests data utilizing a virtual address to access said data in the cache memory, the virtual memory system including a virtual memory map that maps virtual addresses to physical addresses, and a virtual memory fault detector that detects when access to data requested by the data requesting mechanism is not permitted at the virtual address utilized by the data requesting mechanism, said apparatus comprising:

a status detection mechanism having an input coupled to the virtual memory fault detector for receiving an indication therefrom that access to the requested data is not permitted, and an output for outputting a determination indicating whether the requested data is in the cache memory,

a data transfer controller coupled between the permanent storage device and the cache memory, and having an input coupled to the status detection mechanism, which transfers the requested data from the permanent storage device to the cache memory when the input receives a determination by said status detection mechanism that the requested data is not in the cache memory, and

a mapping instruction device having an input coupled to the data transfer controller, and an output coupled to the virtual memory system, the mapping instruction device instructing the virtual memory system, to map the virtual address of the requested data to the physical address of the requested data in the cache memory and permitting access to the requested data when a determination that the requested data is in the cache memory is received.

73. An apparatus as set forth in claim 72, wherein the virtual memory fault detector detects when a virtual address utilized to access data requested by the data requesting mechanism is not mapped to a physical address.

74. An apparatus as set forth in claim 73, wherein said requested data includes a pointer containing a persistent address, and further comprising an inbound address relocation mechanism that relocates the persistent address into a virtual address.

75. An apparatus as set forth in claim 74, further comprising:

an address assignment determination mechanism that determines whether the virtual address utilized by the data requesting mechanism is assigned to a portion of the data stored on the permanent storage device, and

an error signalling device that signals an error to the data requesting mechanism, in response to a determination that the virtual address utilized is not assigned to a portion of the data stored on the permanent storage device.

76. An apparatus as set forth in claim 75, further comprising:

an assignment status detection device that determines if virtual addresses have been assigned to a selected portion of the data on the permanent storage device, which selected portion contains the requested data, and

an address assignment device that assigns virtual addresses for said selected portion of the data if such virtual addresses are not assigned.

77. An apparatus as set forth in claim 76, wherein the processing unit runs application programs requiring data from the permanent storage device, and wherein an application program may involve one or more transactions, and including an outbound relocation mechanism that relocates outbound all data which was relocated inbound during said transaction when a transaction of the one or more transactions commits, and that unmaps all the mapped physical addresses which were mapped during said transaction, and that cancels all virtual address assignments made during the transaction.

78. An apparatus as set forth in claim 77, including a locking mechanism that locks a portion of the data at a client computer when data from the portion is utilized in a transaction at the client computer.

79. An apparatus as set forth in claim 78, wherein said outbound relocation mechanism further includes an unlocking mechanism that unlocks the locked portion of the data.

80. An apparatus as set forth in claim 72, wherein a request for data may be one of a read request and a write request, wherein the data is organized into a database which is divided into segments, each segment containing at least one page and wherein the data transfer controller transfers a page containing the requested data wherein the apparatus further comprises:

a read request device having an input for receiving a transfer of a page in response to a read request for the page, that encaches the page for read and that locks the page for read at a client computer, and a write request device having an input for receiving a transfer of a page in response to a write request for the page, that encaches the page for write and locks the page for write at the client computer.

81. An apparatus as set forth in claim 80, wherein the computer system has a plurality of client computers and a server computer for the permanent storage device, wherein the apparatus further comprises:

cache status detection mechanism having an input for receiving a request for data from the at least one database for read access from the requesting mechanism of a first client computer, for detecting if the requested data is in the cache memory of a second client computer for write access,

an instructing device having an input for receiving a detection by the detecting device that the requested data is in the cache memory of the second client computer, and an output for instructing the second client computer to downgrade a cached state of the data to read access, and

wherein the data transfer controller transfers the requested data to the first client computer.

82. An apparatus as set forth in claim 81, wherein each server computer has an ownership table having an entry for each page of the permanent storage device of the server computer which is encached at a client computer, said entry for a page indicating which client computers have the page encached and whether the page is encached for one of read and write access, and wherein the cache status detection mechanism utilizes the ownership table to determine if the page is encached for write.

83. An apparatus as set forth in claim 82, further comprising:

a querying device that queries the queried client computer having a page encached for write to determine if the page is locked for write, and

a status downgrading mechanism having an input for receiving a response from the queried computer that the page is not locked for write, that downgrades the entry for the page in the ownership table from indicating encached for write to indicate encached for read and that permits the data transfer controller device to transfer the page to the cache memory of the first client computer.

84. An apparatus as set forth in claim 83, wherein the computer system has an application program involving at least one transaction, wherein the apparatus further comprises:

a delay mechanism having an input for receiving a response from the queried client computer that the page is locked for write, that defers further action until the transaction being run at the queried client computer commits, said status downgrading mechanism being operative when the transaction performed by the queried client computer commits.

85. An apparatus as set forth in claim 84, wherein each client computer has a cache directory having an entry for each page in the corresponding cache memory, which entry indicates a cached state and a locked state of the page wherein the apparatus further comprises:

a look-up device having an input that receives a query whether the cached state of a page is locked write, that looks up the page in the cache directory of the queried client computer to determine if the page is locked for write.

86. An apparatus as set forth in claim 85, wherein the queried client computer includes a downgrading and replying mechanism having an input for receiving a determination that the page is not locked for write, that downgrades the cached state of the entry for the page in the cache directory from indicating encached for write to indicate encached for read, and replies the querying server computer that the page is not locked for write.

87. An apparatus as set forth in claim 86, wherein the queried client computer includes a marking device having an input for receiving a determination that the page is locked for write, that marks the entry for the page in the cache directory to be downgraded when the transaction commits, the downgrading and replying device being operative when the transaction being run on the queried client computer commits.

88. An apparatus as set forth in claim 80, wherein the database system has a plurality of client computers and a server computer for each permanent storage device, wherein the apparatus further comprises:

a detection device having an input for receiving a request for data for write access from the data requesting device of a first client computer, that detects if the requested data is in the cache memory of a second client computer,

an instruction device having an input for receiving a detection by the detection device that the requested data is in the cache memory of the second client computer, and an output for instructing the second client computer to remove the data from its cache memory, and

wherein the data transfer controller transfers the requested data to the first client computer.

89. An apparatus as set forth in claim 88, wherein each server computer has an ownership table having an entry for each page of the permanent storage device of the server computer which is encached at a client computer, said entry for a page indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the detection device utilizes the ownership table to determine if the page is encached.

90. An apparatus as set forth in claim 89, further comprising:

a querying device that queries each client computer having the page encached to determine if the page is also locked,

a downgrade mechanism controller, having an input for receiving a reply from all queried client computers that the page is not locked, that removes all entries for the page from the ownership table, that makes an entry for the requesting client computer in the ownership table, and that permits the transferring device to transfer the page to the cache memory of the requesting client computer.

91. An apparatus as set forth in claim 90, wherein the computer system has an application program involving at least one transaction, wherein the apparatus further comprises:

a delay mechanism having an input for receiving a response from at least one queried client computer that the page is locked, that defers further action until the at least one transaction being run on said at least one queried client computer commits, said downgrade mechanism being operative when the at least one transaction being run on the at least one queried client computer commits.

92. An apparatus as set forth in claim 91, wherein each client computer has a cache directory having an entry for each page in the corresponding cache memory, which entry indicates a cached state and a locked state of the page wherein the apparatus further comprises:

a look-up device having an input for receiving a query as to whether a page is locked, that looks up the page in the cache directory of the queried client computer to determine if the page is locked.

93. An apparatus as set forth in claim 92, wherein the queried client computer includes a cache entry removal mechanism having an input for receiving a determination that the page is unlocked, that removes the page from the cache memory of the client computer, that removes the entry for the page from the cache directory, and has an output for outputting a reply to the querying server computer that the page is not locked.

94. An apparatus as set forth in claim 93, wherein the queried client computer includes a reply device having an input for receiving a determination that the page is locked, that marks the entry for the page in the cache directory to be evicted when the transaction commits, and that replies to the querying server computer that the page is locked, said cache entry removal mechanism being operative when the transaction being run on the queried client computer commits.

95. An apparatus as set forth in claim 72, wherein the computer system has a server computer for each of the at least one permanent storage device, wherein data is organized into a database divided into segments, each segment containing at least one page, and wherein each segment of the database is divided into a data segment and an information segment.

96. An apparatus as set forth in claim 95, wherein a plurality of different types of objects may be stored in a data segment, and wherein the information segment for each data segment contains a tag table having a tag entry for each object in the data segment, each tag entry identifying at least the object type for the corresponding object.

97. An apparatus as set forth in claim 96, wherein a data segment may contain at least one of a single object, a vector of multiple objects and free space, wherein the tag entry for a single object contains a type code for the object, the tag entry for a vector of objects contains a type code for one of the multiple objects and a length field indicating a number of objects in the vector, and the tag entry for free space has a type code and a length field.

98. An apparatus as set forth in claim 97, wherein the computer system has an application program involving at least one transaction, and wherein objects may be created during a transaction, an object having an object type indication and an indication of a database and a segment for the object wherein the apparatus further comprises:

a size determination device that determines the size of the object from the object type indication,

a tag table search device that searches the tag table to find free space of suitable size for the object,

a first tag entry insertion device that inserts a tag entry for the object in place of any tag entry for free space if suitable free space is found,

a second tag entry insertion device that inserts a tag entry for free space of shorter size if free space remains after insertion of the object,

a tag entry generator that creates a tag entry at the end of the tag table if suitable free space is not found, and

a virtual address generator that generates a virtual address for the object.

99. An apparatus as set forth in claim 98, wherein objects may be deleted during a transaction, and further comprising:

a tag entry identification device that finds a tag entry in the tag table for a deleted object,

a size determination device that determines the size of the deleted object, and

a tag entry converter that converts the tag entry for the deleted object to a tag entry for free space of size equal to the determined size of the deleted object.

100. An apparatus as set forth in claim 99, further comprising:

a free space identification device that determines if a tag entry preceding or following the tag entry for free space for the deleted object in the tag table is a tag entry for free space, and

a merge device that merges adjacent tag entries for free space into a single tag entry for free space of size equal to the sum of the sizes of the merged tag entries.

101. An apparatus as set forth in claim 96, wherein each object in the data may contain at least one pointer at a selected offset location in the object which points to a persistent address in the data, and wherein the data a schema associated therewith, the schema containing an entry for each object type present in the data, each schema entry containing a field indicating a size of the object type, and an instruction indicating an offset location in the object for each pointer for the object type.

102. An apparatus as set forth in claim 101, further comprising:

a schema transfer device that transfers the schema for the data to a client computer before the virtual memory system at the client computer performs any mapping for the data, and wherein the schema transfer device includes a page data transfer device that transfers page data from both a data segment and an information segment corresponding to the data segment.

103. An apparatus as set forth in claim 102, wherein the computer system has an application program involving at least one transaction, and wherein the apparatus further comprises:

an outbound address relocation device, operative when a transaction commits, that relocates outbound data which was relocated inbound during the transaction;

wherein the inbound address relocation device and the outbound relocating device each include an object type identification device that determines an object type for a selected object from the tag table transferred with a page, a description obtaining device that obtains a description of the selected object from the schema using the object type from the tag table, and a retrieval mechanism that retrieves a corresponding pointer, utilizing each schema instruction for the object type, and

wherein the inbound address relocation device includes a first converter that converts the persistent address of each pointer to a corresponding virtual address, and wherein the outbound address relocation device includes a second converter that converts the virtual address of each pointer to the corresponding persistent address.

104. An apparatus as set forth in claim 95, further comprising:

an information segment of the database, a persistent relocation map, which indicates a beginning persistent address for a selected database portion and having a given segment and offset,

said data transfer controller including a mechanism for transferring the persistent relocation map, and

a mechanism for determining a persistent address corresponding to a given database, segment and offset from the persistent relocation map.

105. An apparatus as set forth in claim 104, further comprising:

a virtual address map at least one client computer for indicating a beginning virtual address for a selected database portion and having a given offset, and

a mechanism for determining a virtual address corresponding to a given database, segment and offset from the virtual address map.

106. An apparatus as set forth in claim 105, wherein the computer system has an application program involving at least one transaction, and wherein the apparatus further comprises:

an outbound address relocation device, operative when a transaction commits, that relocates outbound data which was relocated inbound during the transaction, and an inbound address relocation device including a first mechanism for determining a database, segment and offset for a given persistent page address from the persistent relocation map, and a second mechanism for determining a corresponding virtual page address for the determined database, segment and offset from the virtual address memory, and

wherein the outbound relocation device includes a mechanism for determining a database, segment and offset for a given virtual page address from the virtual address map, and a mechanism for determining a corresponding persistent address from the determined database, segment and offset from the persistent relocation map.

107. An apparatus as set forth in claim 106, further including:

a verification device, that verifies that the persistent relocation map for the segment containing requested data has been transferred to at least one client computer,

a mechanism for examining each persistent relocation map entry in turn to determine if there is a corresponding virtual address map entry, and

a mechanism for creating a new virtual address map entry for each selected database portion for which a virtual address map entry does not exist.

108. An apparatus as set forth in claim 72 wherein the virtual memory fault detector detects one of whether access to data is not permitted and whether a program fault resulted from an unsuccessful attempt to access data.