Database memory compaction and reclamation method

Claim 1

A method for effecting recovery of database memory resources when necessary for use by a digital data processing system for performing real-time operations, said digital data processing system including a limited amount of memory, said memory having a plurality sequentially numbered memory pages, said database comprising a plurality of child tuples and one or more parent tuples, each of said parent tuples having at least one reference to one or more child tuples, said child tuples being stored in sequentially numbered memory locations on said memory pages and each child tuple having the capability of referencing another child tuple, said method comprising: copying child tuples from higher numbered memory locations to lower numbered memory locations by repetitively copying a child tuple from the highest numbered occupied memory location into the lowest unused memory location until the next lowest unused memory location has a higher number than the highest memory location in which a child tuple is located; resetting references to said copied child tuples in all tuples referencing said copied child tuples; marking all child tuples that are referenced from any of said tuples; collecting all unmarked child tuples, and collecting all copied child tuples from said higher numbered memory locations thereby creating unused higher numbered memory pages.

Claim 2

A method for effecting recovery of database memory resources when necessary for use by a digital data processing system for performing real-time operations, said digital data processing system including a limited amount of memory, said memory having a plurality sequentially numbered memory pages, said database comprising a plurality of child tuples and one or more parent tuples, each of said parent tuples having at least one reference to one or more child tuples, said child tuples being stored in sequentially numbered memory locations on said memory pages and each child tuple having the capability of referencing another child tuple, said method comprising: copying child tuples from higher numbered memory locations to lower numbered memory locations by repetitively copying a child tuple from the highest numbered occupied memory location into the lowest unused memory location until the next lowest unused memory location has a higher number than the highest memory location in which a child tuple is located; resetting references to said copied child tuples in all tuples referencing said copied child tuples; marking all child tuples that are referenced from any of said tuples; collecting all unmarked child tuples, and collecting all copied child tuples from said higher numbered memory locations thereby creating unused higher numbered memory pages.

Claim 5

A method for effecting recovery of database memory resources when necessary for use by a digital data processing system for performing real-time operations, said digital data processing system including a limited amount of memory, said memory having a plurality of sequentially numbered memory pages, said database comprising a plurality of child tuples and one or more parent tuples, said parent tuples having at least one reference each to one or more child tuples, said child tuples being stored in sequentially numbered memory locations on said memory pages, each of said child tuples having unique data and a link to another of said child tuples, selected ones of said child tuples being linked into lists, said data base further comprising an index list having a plurality of links to a plurality of linked lists of child tuples, said method comprising: selecting unused memory locations among said child tuples in lower numbered memory locations; compressing child tuples from higher numbered memory locations to lower numbered memory locations by copying said child tuples from higher numbered memory locations into said selected unused memory locations; resetting references of child tuples from said higher numbered memory locations to said lower numbered memory locations, said resetting including linking said lower numbered memory child tuples into the linked list of said higher numbered memory child tuple; marking all child tuples referenced from said parent tuples; collecting all unmarked child tuples; and collecting all compressed child tuples from said higher numbered memory locations.

Claim 6

A method for effecting recovery of database memory resources when necessary for use by a digital data processing system for performing real-time operations, said digital data processing system including a limited amount of memory, said memory having a plurality of sequentially numbered memory pages, said database comprising a plurality of child tuples and one or more parent tuples, said parent tuples having at least one reference each to one or more child tuples, said child tuples being stored in sequentially numbered memory locations on said memory pages, each of said child tuples having unique data and a link to another of said child tuples, selected ones of said child tuples being linked into lists, said data base further comprising an index list having a plurality of links to a plurality of linked lists of child tuples, said method comprising: selecting unused memory locations among said child tuples in lower numbered memory locations; compressing child tuples from higher numbered memory locations to lower numbered memory locations by copying said child tuples from higher numbered memory locations into said selected unused memory locations; resetting references of child tuples from said higher numbered memory locations to said lower numbered memory locations, said resetting including linking said lower numbered memory child tuples into the linked list of said higher numbered memory child tuple; marking all child tuples referenced from said parent tuples; collecting all unmarked child tuples; and collecting all compressed child tuples from said higher numbered memory locations.