# US 2001/0034822 A1 · Method and apparatus for virtual memory mapping and transaction management in an object-oriented database system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2001/0034822 A1
- Document ID: US20010034822A1
- Status: Published application
- Kind: A1
- Application number: 09/800,257
- Filed: 2001-03-06
- Published: 2001-10-25
- Earliest claimed: 1991-03-22
- Assignees: Progress Software Corporation
- Inventors: Daniel L. Weinreb; Sam J. Haradhvala
- Web page: https://patentgrep.com/patent/US20010034822A1

## CPC

- G06F 12/1072: Decentralised address translation, e.g. in distributed shared memory systems
- G06F 9/4493: {Object persistence}
- G06F 12/0813: with a network or matrix configuration
- G06F 12/0815: Cache consistency protocols
- G06F 12/10: Address translation
- Y10S 707/99938: Concurrency, e.g. lock management in shared database
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## 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 on 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

### Claim 1

An apparatus for virtual memory mapping and transaction management for an object-oriented database system having at least one permanent storage means for storing data in at least one database, 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 virtual addresses to access said data in the cache memory, means for mapping virtual addresses to physical addresses, and means for detecting when data requested by therequesting means is not available at the virtual address utilized by the requesting means, said apparatus comprising:
means operative in response to a detection by said detecting means for determining if the requested data is in the cache memory,
means for transferring the requested data from the permanent storage means to the cache memory responsive to a determination by said determining means that the requested data is not in the cache memory, and
means operative when requested data is in the cache memory for instructing the means for mapping to map the virtual addresses of the requested data to the physical addresses of the data in the cache memory.

### Claim 2 (depends on 1)

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 requesting means is not mapped to a physical address.

### Claim 3 (depends on 2)

An apparatus as set forth in claim 2, wherein said data includes pointers containing persistent addresses, and further comprising means for relocating inbound the pointers in said requested data from persistent addresses to virtual addresses.

### Claim 4 (depends on 3)

An apparatus as set forth in claim 3, further comprising:
means for determining whether the virtual address utilized by the requesting means 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.

### Claim 5 (depends on 4)

An apparatus as set forth in claim 4, further comprising:
means for determining if virtual addresses have been assigned to a selected portion of a database, which portion contains the data requested, and
means for assigning virtual addresses for said selected database portion if such virtual addresses are not assigned.

### Claim 6 (depends on 5)

An apparatus as set forth in claim 5 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, and including means operative when a transaction commits, said means including means for relocating outbound all data which was relocated inbound during said transaction, means for unmapping all data which was mapped during said transaction, and means for cancelling all virtual address assignments made during the transaction.

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 7)

An apparatus as set forth in claim 7 wherein said means operative when a transaction commits includes means for unlocking all data portions locked during the transaction.

### Claim 9 (depends on 1)

An apparatus as set forth in claim 1 wherein a request for data may be a read request or a write request, wherein a database is divided into segments, each containing one or more pages and wherein said means for transferring transfer the page containing requested data; and
including means responsive 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 the client computer, and means responsive 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.

### Claim 10 (depends on 9)

An apparatus as set forth in claim 9 wherein the system has a plurality of client computers and a server computer for each permanent storage means; and
including means responsive to a request for data from a database for read access from the requesting means 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 detecting means for instructing the second client computer to downgrade to read access, and means for transferring the requested data to the first client computer.

### Claim 11 (depends on 10)

An apparatus as set forth in claim 10 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 indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the detecting means utilizes the ownership table to determine if the page is encached for write.

### Claim 12 (depends on 11)

An apparatus as set forth in claim 11 including means for querying the client computer having the page encached for write to determine if the page is locked for write, and means responsive to a response from the queried computer that the page is not locked for write for downgrading the ownership table entry for the page 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 requesting client computer.

### Claim 13 (depends on 12)

An apparatus as set forth in claim 12, wherein the system has an application program involving at least one transaction, and including 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 queried client computer transaction commits.

### Claim 14 (depends on 13)

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; and
including means responsive to a locked-for-write query for looking up the page in the cache directory of the queried client computer to determine if the page is locked for write.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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 “downgrade when done”, said means for downgrading and replying being operative when the transaction being run on the queried client computer commits.

### Claim 17 (depends on 9)

An apparatus as set forth in claim 9 wherein the system has a plurality of client computers and a server computer for each permanent storage means; and
including means responsive to a request for data from a database for write access from the requesting means 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 detecting means 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.

### Claim 18 (depends on 17)

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 indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the encached determining means utilizes the ownership table to determine if the page is encached.

### Claim 19 (depends on 18)

An apparatus as set forth in claim 18 including 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 all 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.

### Claim 20 (depends on 19)

An apparatus as set forth in claim 19 wherein the system has an application program involving at least one transaction, and including means responsive to a response from at least one queried client computer that the page is locked for deferring further action until the transactions being run on all said at least one queried client computers commit, said means for removing all entries, for making an entry and for permitting being operative when all queried client computer transactions commit.

### Claim 21 (depends on 20)

An apparatus as set forth in claim 20 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; and
including means responsive to a locked query for looking up the page in the cache directory of the queried client computer to determine if the page is locked.

### Claim 22 (depends on 21)

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.

### Claim 23 (depends on 22)

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 “evict when done” and for replying to the querying server computer that the page is locked, said means for removing the page, removing the entry, and for replying being operative when the transaction being run on the queried client computer commits.

### Claim 24 (depends on 1)

An apparatus as set forth in claim 1 wherein the system has a computer for each 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.

### Claim 25 (depends on 24)

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 segment, each tag entry identifying at least the object type for the corresponding object.

### Claim 26 (depends on 25)

An apparatus as set forth in claim 25 wherein a segment may contain single objects, vectors of multiple objects and free space, the tag for a single object containing a type code for the object, the tag for a vector of objects containing a type code for the object and a length field indicating the number of objects in the vector, and the tag for free space also having a type code and a length field.

### Claim 27 (depends on 26)

An apparatus as set forth in claim 26 wherein the system has an application program involving at least one transaction, and wherein objects may be created during a transaction, a created object having an object type indication and an indication of database and segment for the object; and
including means for determining the size of the created object from the created object type means for searching the tag table to find free space of suitable size for the createdobject, means for inserting a new object tag in place of the free space tag if suitable free space is found, means for inserting a new free space tag of shorter size if free space remains after insertion of the created object, means for creating a new tag at the end of the tag table if suitable free space is not found, and means for generating a virtual address for the created object.

### Claim 28 (depends on 27)

An apparatus as set forth in claim 27 wherein objects may be deleted during a transaction and including means for finding the tag in the tag table for a deleted object, means for determining the size of the deleted object, and means for converting the tag for the deleted object to a free space tag of size equal to the determined size of the deleted object.

### Claim 29 (depends on 28)

An apparatus as set forth in claim 28 including means for determining if the tag preceding or the tag following the new free space tag is a free space tag, and means for merging adjacent free space tags into a single free space tag of size equal to the sum of the sizes of the merged tags.

### Claim 30 (depends on 25)

An apparatus as set forth in claim 25 wherein each object type in a database may contain one or more pointers at selected offset locations in the object which point to persistent addresses in the 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 the size of the object type, and an instruction indicating the offset location in the object for each pointer for the object type.

### Claim 31 (depends on 30)

An apparatus as set forth in claim 30 including 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 the corresponding information segment.

### Claim 32 (depends on 31)

An apparatus as set forth in claim 31 wherein the system has an application program involving at least one transaction, and including means operative when a transaction commits for relocating outbound all data which was relocated inbound during the transaction; wherein the means for relocating inbound and the means for relocating outbound each include means for determining the object type for a selected object from the tag table transferred with a page, means for obtaining a description of the object from the schema using the object type from the tag table, and means for retrieving the corresponding pointer, utilizing each schema instruction for the object type, and 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.

### Claim 33 (depends on 24)

An apparatus as set forth in claim 24 including a persistent relocation map (PRM) in an information segment of a database, which PRM indicates the beginning persistent address for a selected database portion and having a given segment offset, said means for transferring including means for transferring the PRM, and including means for determining the persistent address corresponding to a given database, segment and offset from the PRM.

### Claim 34 (depends on 33)

An apparatus as set forth in claim 33 including a virtual address map (VAM) at each client computer for indicating the beginning virtual address for a selected database portion and having a given offset, and means for determining the virtual address corresponding to a given database, segment and offset from the VAM.

### Claim 35 (depends on 34)

An apparatus as set forth in claim 34 wherein the system has an application program involving at least one transaction, and including means operative when a transaction commits for relocating outbound all data which was relocated inbound during the transaction, the means for relocating inbound including means for determining the database, segment and offset for a given persistent page address from the PRM, and means for determining the corresponding the virtual page address for the determined database, segment and offset from the VAM, and
wherein the step of relocating outbound includes means for determining the database, segment and offset for a given virtual page address from the VAM, and means for determining the corresponding persistent address from the determined database, segment and offset from the VAM.

### Claim 36 (depends on 35)

An apparatus as set forth in claim 35 wherein said means for assigning includes means for verifying that the PRM 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 VAM entry, and means for creating a new VAM entry for each selected database portion for which it is determined that a VAM entry does not exist.

### Claim 37 (depends on 1)

An apparatus as set forth in claim 1 wherein the means for detecting that data is not available is operative in response to either an instruction indicating data is not available or in response to a program fault resulting from an unsuccessful attempt to read or write data.

### Claim 38

An apparatus for virtual memory mapping and transaction management for an object-oriented database system having at least one permanent storage means for storing data, said data including pointers containing persistent addresses, at least one cache memory addressed by physical addresses, and a processing unit including means for requesting data in the cache utilizing virtual addresses, said apparatus comprising:
means for transferring data between the cache memory and the permanent storage means,
means for relocating inbound data requested by the means for requesting, and
means for mapping the virtual addresses of the requested data to physical addresses of the data in the cache memory.

### Claim 39 (depends on 38)

An apparatus as set forth in claim 38 wherein the system has a server computer for each 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.

### Claim 40 (depends on 39)

An apparatus as set forth in claim 39 including a persistent relocation map (PRM) in an information segment of a database, which PRM indicates the beginning persistent address for a selected database portion and having a given segment offset, said means for transferring including means for transferring the PRM, and including means for utilizing the PRM to determine the persistent address corresponding to a given database, segment and offset.

### Claim 41 (depends on 40)

An apparatus as set forth in claim 40 including a virtual address map (VAM) at each client computer, which map indicates the beginning virtual address for a selected database portion and having a given offset, and means for utilizing the VAM to determine the virtual address corresponding to a given database, segment and offset.

### Claim 42 (depends on 41)

An apparatus as set forth in claim 41 wherein an applications program may involve one or more transactions, and including means operative when a transaction commits for relocating outbound all data which was relocated inbound during the transaction, the means for relocating inbound including means for utilizing the PRM to determine the database, segment and offset for a given persistent page address, and means for utilizing the VAM to determine the corresponding virtual page address from the determined database, segment and offset; and
wherein the means for relocating outbound includes means for utilizing the VAM to determine the database, segment and offset for a given virtual page address, and means for utilizing the PRM to determine the corresponding persistent page address from the determined database segment and offset.

### Claim 43 (depends on 42)

An apparatus as set forth in claim 42 wherein said means for assigning includes means for verifying that the PRM for the segment containing requested data has been transferred to the client computer, means for looking at each PRM entry in turn to determine if there is a corresponding VAM entry, and means for creating a new VAM entry, and thus assigning virtual address space, for each selected database portion for which it is determined that a VAM entry does not exist.

### Claim 44

An apparatus for virtual memory mapping and transaction management for an object-oriented database system, comprising:
at least one permanent storage means for storing data in at least one database,
a plurality of client computers each having a cache memory for storing data and a processing unit, the processing unit including means for requesting data from said at least one database and means for transferring data between the permanent storage means and the cache memory,
means responsive to a request for data from a database from the requesting means of a first client computer for detecting if the requested data is in the cache memory of a second client computer, and is encached in a manner incompatible with consistent use of the data by the first client computer,
means responsive to a detection by said detecting means for instructing said second client computer to change the manner in which the data is encached, and
means for transferring said requested data to the first client computer responsive to said means for instructing.

### Claim 45 (depends on 44)

An apparatus as set forth in claim 44, wherein said request for data is a request for write access, and said means for detecting the text of the requested data in the cached memory of a second client computer, and said means for instructing instruct said second client computer to remove said requested data from its cached.

### Claim 46 (depends on 44)

An apparatus as set forth in claim 44, wherein said request for data is a request for read access, and said means for detecting the text if the requested data is encached for write at a second client computer, and said means for instructing instruct said second client computer to downgrade said data from encached for write to encached for read.

### Claim 47 (depends on 44)

An apparatus as set forth in claim 44, wherein a request for data may be a read request or a write request, wherein a database is divided into segments, each containing one or more pages and wherein said means for transferring transfer the page containing requested data; and
including means responsive 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 the client computer, and means responsive 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.

### Claim 48 (depends on 47)

An apparatus as set forth in claim 47 wherein the system has a plurality of client computers and a server computer for each permanent storage means; and
including means responsive to a request for data from a database for read access from the requesting means 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 detecting means for instructing the second client computer to downgrade to read access, and means for transferring the requested data to the first client computer.

### Claim 49 (depends on 48)

An apparatus as set forth in claim 48 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 indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the detecting means utilizes the ownership table to determine if the page is encached for write.

### Claim 50 (depends on 49)

An apparatus as set forth in claim 49 including means for querying the client computer having the page encached for write to determine if the page is locked for write, and means responsive to a response from the queried computer that the page is not locked for write for downgrading the ownership table entry for the page 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 requesting client computer.

### Claim 51 (depends on 50)

An apparatus as set forth in claim 50, wherein the system has an application program involving at least one transaction, and including 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 queried client computer transaction commits.

### Claim 52 (depends on 51)

An apparatus as set forth in claim 51 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; and
including means responsive to a locked-for-write query for looking up the page in the cache directory of the queried client computer to determine if the page is locked for write.

### Claim 53 (depends on 52)

An apparatus as set forth in claim 52 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.

### Claim 54 (depends on 53)

An apparatus as set forth in claim 53, 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 “downgrade when done”, said means for downgrading and replying being operative when the transaction being run on the queried client computer commits.

### Claim 55 (depends on 47)

An apparatus as set forth in claim 47 wherein the system has a plurality of client computers and a server computer for each permanent storage means; and
including means responsive to a request for data from a database for write access from the requesting means 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 detecting means 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.

### Claim 56 (depends on 55)

An apparatus as set forth in claim 55, 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 indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the encached determining means utilizes the ownership table to determine if the page is encached.

### Claim 57 (depends on 56)

An apparatus as set forth in claim 56 including 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 all 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.

### Claim 58 (depends on 57)

An apparatus as set forth in claim 57 wherein the system has an application program involving at least one transaction, and including means responsive to a response from at least one queried client computer that the page is locked for deferring further action until the transactions being run on all said at least one queried client computers commit, said means for removing all entries, for making an entry and for permitting being operative when all queried client computer transactions commit.

### Claim 59 (depends on 58)

An apparatus as set forth in claim 58 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; and
including means responsive to a locked query for looking up the page in the cache directory of the queried client computer to determine if the page is locked.

### Claim 60 (depends on 60)

An apparatus as set forth in claim 60 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's removing the entry for the page from the cache directory, and for replying to the querying server computer that the page is unlocked.

### Claim 61 (depends on 60)

An apparatus as claimed in claim 60 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 “evict when done” and for replying to the querying server computer that the page is locked, said means for removing the page, removing the entry, and for replying being operative when the transaction being run on the queried client computer commits.

### Claim 62

A method for virtual memory mapping and transaction management for an object-oriented database system having at least one permanent storage means for storing data in at least one database, 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 virtual addresses to access said data in the cache memory and means for mapping virtual addresses to physical addresses, said method comprising the steps of:
detecting when data requested by the requesting means is not available at the virtual address utilized by the requesting means,
determining if the data requested is in the cache memory in response to a detection,
transferring the requested data from the permanent storage means to the cache memory responsive to a determination that the requested data is not in the cache memory, and
instructing the means for mapping to map the virtual addresses of the requested data to the physical addresses of the data in the cache memory.

### Claim 63 (depends on 62)

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

### Claim 64 (depends on 63)

A method as set forth in claim 63, wherein said 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.

### Claim 65 (depends on 64)

A method as set forth in claim 64, further comprising the steps of:
determining whether the virtual address utilized by the requesting means is assigned to data, and
signalling an error to the means for requesting in response to a determination that the virtual address utilized is not assigned to data.

### Claim 66 (depends on 65)

A method as set forth in claim 65, further comprising the steps of:
determining if virtual addresses have been assigned to a selected portion of a database, which portion contains the data requested, and
assigning virtual addresses for said selected database portion if such virtual addresses are not assigned.

### Claim 67 (depends on 66)

A method as set forth in claim 66 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 commits of:
relocating outbound all data which was relocated inbound during said transaction,
unmapping all data which was mapped during said transaction, and
cancelling all virtual address assignments made during the transaction.

### Claim 68 (depends on 67)

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

### Claim 69 (depends on 68)

A method as set forth in claim 68 further including the step of unlocking all data portions locked during the transaction when a transaction commits.

### Claim 70 (depends on 62)

A method as set forth in claim 62 wherein a request for data may be a read request or a write request, wherein a database is divided into segments, each containing one or more pages, and wherein said 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 the 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.

### Claim 71 (depends on 70)

A method as set forth in claim 70 wherein said system has a plurality of client computers and a server computer for each 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 requesting means 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, to downgrade to read access.

### Claim 72 (depends on 71)

A method as set forth in claim 71 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 indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the step of detecting includes the step of utilizing the ownership table to determine if the page is encached for write.

### Claim 73 (depends on 72)

A method as set forth in claim 72 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 ownership table entry for the page from indicating encached for write to indicate encached for read in response to a response from the queried computer that the page is not locked for write.

### Claim 74 (depends on 73)

A method as set forth in claim 73, 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, said steps of downgrading and transferring being performed when the queried client computer transaction commits.

### Claim 75 (depends on 74)

A method as set forth in claim 74 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 locked-for-write query

### Claim 76 (depends on 75)

A method as set forth in claim 75 further comprising the steps of:
downgrading the cached state of the entry for the page in the cache directory of a 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.

### Claim 77 (depends on 76)

A method as set forth in claim 76, including the steps of:
marking the entry for the page in the cache directory of the queried client computer “downgrade when done” in response to a determination that the page is locked for write,
said steps of downgrading and replying being performed when the transaction being run on the queried client computer commits.

### Claim 78 (depends on 70)

A method as set forth in claim 70 wherein said system has a plurality of client computers and a server computer for each 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 requesting means of a first client computer, and
instructing the second client computer in response to a detection by the detecting means to remove the data from its cache memory.

### Claim 79 (depends on 78)

A method as set forth in claim 78, 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 indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the step of determining encached status includes the step of determining if the page is encached utilizing the ownership table.

### Claim 80 (depends on 79)

A method as set forth in claim 79 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.

### Claim 81 (depends on 80)

A method as set forth in claim 80 wherein the 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,
said steps of removing all entries, making an entry and for transferring the page being performed when all queried client computer transactions commit.

### Claim 82 (depends on 81)

A method as set forth in claim 81 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 is response to a locked query.

### Claim 83 (depends on 82)

A method as set forth in claim 82 further comprising the steps of:
removing the page from the cache memory of the queried client computer in response to a determination,
removing the entry for the page from the cache directory, and
replying to the querying server computer that the page is not locked.

### Claim 84 (depends on 83)

A method as set forth in claim 83 further comprising the steps of:
marking of the entry for the page in the cache directory of the queried client computer “evict when done” 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.

### Claim 85 (depends on 62)

A method as set forth in claim 62 wherein said system includes an application program involving at least one transaction, and wherein objects may be created during a transaction, a created 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 of a created object to determine the size of the created object,
searching a tag table for free-space tags to find free space of suitable size for the created object,
inserting an object tag for the created object in place of the free space tag if suitable free space is found,
inserting a new free space tag of shorter size if free space remains after insertion of the new object,
creating a new tag at the end of the tag table if suitable free space is not found, and
generating a virtual address for the created object.

### Claim 86 (depends on 85)

A method as set forth in claim 85 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 the size of the deleted object, and
converting the tag for the deleted object to a free space tag of size equal to the determined size of the deleted object.

### Claim 87 (depends on 86)

An apparatus as set forth in claim 86 further comprising the steps of:
determining if the tag preceding or the tag following the new free space tag is a free space tag, and
merging adjacent free space tags into a single free space tag of size equal to the sum of the sizes of the merged tags.

### Claim 88 (depends on 64)

A method as forth in claim 64 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 its corresponding information segment.

### Claim 89 (depends on 88)

A method as set forth in claim 88 wherein the 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 steps of relocating outbound each include the step of determining the object type for a selected object utilizing a tag table transferred with a page,
obtaining a description of the object from the schema, utilizing the object type from the tag table, and
wherein the step of relocating inbound includes the step of converting the persistent address of each pointer to a corresponding virtual address, and
wherein the step of relocating outbound includes the step of converting the virtual address of each pointer to the corresponding persistent address.

### Claim 90 (depends on 64)

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

### Claim 91 (depends on 90)

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

### Claim 92 (depends on 91)

A method as set forth in claim 91 wherein said system includes an application program involving at least one transaction, said method further including the steps of relocating outbound, when a transaction commits, all data which was relocated inbound during the transaction,
wherein the step of relocating inbound including the steps of determining the database, segment and offset for a given persistent page address utilizing the PRM, and determining the 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 the database, segment and offset for a given virtual page address utilizing the VAM, and determining the corresponding persistent page address from the determined database, segment and offset utilizing the PRM.

### Claim 93 (depends on 92)

A method as forth in claim 92 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.

### Claim 94 (depends on 62)

A method as set forth in claim 62 wherein the step of detecting that data is not available is performed in response to either an instruction indicating data is not available or in response to a program fault resulting from an unsuccessful attempt to read or write data.

### Claim 95

A method for virtual memory mapping and transaction management for an object-oriented database system having at least one permanent storage means for storing data, said data including pointers containing persistent addresses, at least one cache memory addressed by physical addresses, and a processing unit including means for requesting data in the cache utilizing virtual addresses, said method comprising the steps of:
transferring data between the cache memory and the permanent storage means,
relocating inbound data requested by the means for requesting, and
mapping the virtual addresses of the requested data to physical addresses of the data in the cache memory.

### Claim 96 (depends on 95)

A method as set forth in claim 95 wherein the system includes a server computer for each permanent storage means, and a persistent relocation map (PRM) in an information segment of a database, which PRM indicates the beginning persistent address for a selected database portion and having a given segment and offset, wherein said step of transferring includes transferring the PRM, and said method further includes the step of determining the persistent address corresponding to a given database, segment and offset utilizing the PRM.

### Claim 97 (depends on 96)

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

### Claim 98 (depends on 97)

A method as set forth in claim 97 wherein the system includes an application program having 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 includes the steps of utilizing the PRM to determine the database, segment and offset for a given persistent page address and utilizing the VAM to determine the corresponding virtual page address from the determined database, segment and offset, and
wherein the step of relocating outbound includes the steps of utilizing the VAM to determine the database, segment and offset for a given virtual page address, and utilizing the PRM to determine the corresponding persistent page address from the determined database, segment and offset.

### Claim 99 (depends on 98)

A method as set forth in claim 98 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.

### Claim 100

A method for virtual memory mapping and transaction management for an object-oriented database system, the system having at least one permanent storage means for storing data in at least one database, a plurality of client computers each having a cache memory for storing data and a processing unit, the processing unit including means for requesting data from said at least one database and means for transferring data between the permanent storage means and the cache memory, said method comprising the steps of:
detecting, in response to a request for data from a database from the requesting means of a first client computer, if the requested data is in the cache memory of a second client computer, and is encached in a manner incompatible with consistent use of the data by the first client computer,
instructing said second client computer to change the manner in which the data is encached in response to a detection, and
transferring said requested data to the first client computer after the second client computer changes the manner in which the data is encached.

### Claim 101 (depends on 100)

A method as set forth in claim 100, wherein said step of detecting if requested data is in the cache memory of a second client computer in response to a request for write access, and said step of instructing includes instructing said second client computer to remove the requested data from its cache.

### Claim 102 (depends on 100)

A method as set forth in claim 100, wherein said step of detecting if the requested data is encached for write at a second client computer in response to a request for read access, and said step of instructing includes instructing said second client computer to downgrade said data from encached for write to encached for read.

### Claim 103 (depends on 100)

A method as set forth in claim 100, wherein a request for data may be a read request or a write request, wherein a database is divided into segments, each containing one or more pages and wherein said step of transferring includes transferring the page containing requested data, said method further including the steps of:
encaching the page for read, in response to a transfer of a page in response to a read request for the page, and locking the page for read at the client computer and,
encaching the page for write, in response to a transfer of a page in response to a write request for the page, and locking the page for write at the client computer.

### Claim 104 (depends on 103)

A method as set forth in claim 103 wherein the system includes plurality of client computers and a server computer for each 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 requesting means of a first client computer, if the requested data is in the cache memory of a second client computer for write access, and
instructing the second client computer in response to a detection to downgrade to read access.

### Claim 105 (depends on 104)

A method as set forth in claim 104 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 indicating which client computers have the page encached and whether the page is encached for read or write, and wherein said step of detecting includes the step of determining if the page is encached for write utilizing the ownership table.

### Claim 106 (depends on 105)

A method as set forth in claim 105 including the steps of:
querying the client computer having the page encached for write to determine if the page is locked for write,
downgrading the ownership table entry for the page, in response to a response from the queried computer that the page is not locked for write, from indicating encached for write to indicate encached for read.

### Claim 107 (depends on 106)

A method as set forth in claim 106, wherein the system includes an application program involving at least one transaction, said method including the steps of:
deferring further action 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,
said steps of downgrading and transferring being performed when the queried client computer transaction commits.

### Claim 108 (depends on 107)

A method as set forth in claim 107 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 including the step of looking up the page in the cache directory of the queried client computer in response to a locked-for-write query to determine if the page is locked for write.

### Claim 109 (depends on 108)

A method as set forth in claim 108 further including 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, and
replying to the querying server computer in response to a determination that the page is not locked for write.

### Claim 110 (depends on 109)

A method as set forth in claim 109, further comprisikng the steps of:
marking the entry for the page in the cache directory “downgrade when done” in response to a determination that the page is locked for write, said steps of downgrading and replying being performed when the transaction being run on the queried client computer commits.

### Claim 111 (depends on 103)

A method as set forth in claim 103 wherein the system includes a plurality of client computers and a server computer for each permanent storage means, said method including the steps of:
detecting, in response to a request for data from a database for write access from the requesting means 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 to remove the data from its cache memory.

### Claim 112 (depends on 111)

A method as set forth in claim 111, 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 indicating which client computers have the page encached and whether the page is encached for read or write, and wherein the step of determining encached status includes determining if the page is encached utilizing the ownership table.

### Claim 113 (depends on 112)

A method as set forth in claim 112 including 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.

### Claim 114 (depends on 113)

A method as set forth in claim 113 wherein the system includes an application program involving at least one transaction, and including the step 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,
said steps of removing all entries, making an entry and transferring being performed when all queried client computer transactions commit.

### Claim 115 (depends on 114)

A method as set forth in claim 114 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, said method including the step of looking up the page in the cache directory of the queried client computer in response to a locked query to determine if the page is locked.

### Claim 116 (depends on 115)

A method as set forth in claim 115, further comprising the steps of:
removing the entry for a page from the cache memory in response to a determination that the page is not locked at the queried client computer, and
replying to the querying server computer that the page is not locked.

### Claim 117 (depends on 116)

A method as set forth in claim 116 further comprising the steps of:
marking the entry for the page in the cache directory of the queried client computer “evict when done” in response to a determination, and
replying to the querying server computer that the page is locked,
said steps of removing the page, removing the entry, and for replying being performed when the transaction being run on the queried client computer commits.
