Browse Prior Art Database

Virtual Relational Memory

IP.com Disclosure Number: IPCOM000104453D
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 107K

Publishing Venue

IBM

Related People

Robinson, JT: AUTHOR

Abstract

Consider a shared relational database management system in which various application programs execute in separate virtual address spaces. Disclosed is a method for providing such application programs a simple flat view, within their virtual address space, of one or more relations derived via completely arbitrary relational algebra operators from other base relations, without any movement of tuples or records, by means of a more complex method of address translation than that typically used in page-based virtual memory systems.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Virtual Relational Memory

      Consider a shared relational database management system in
which various application programs execute in separate virtual
address spaces.  Disclosed is a method for providing such application
programs a simple flat view, within their virtual address space, of
one or more relations derived via completely arbitrary relational
algebra operators from other base relations, without any movement of
tuples or records, by means of a more complex method of address
translation than that typically used in page-based virtual memory
systems.

      In more detail, suppose we want to "materialize" a virtual
relation V in some portion of an application's address space,
starting at address A sub 'base'.  Assume byte-level addressing (for
other granularities of addressing, replace "byte" with the unit of
addressing in this description).  Suppose V has record (or tuple)
length R (where R is in bytes), and that there are m fields (or
domains) in each record (tuple), of lengths (in bytes) L sub 0, L sub
1,....., L sub m-1, where Sum of < L sub i > is R.  Define field
offsets F sub i as follows:

                          F sub 1 = L sub 0

                     F sub 2 = L sub 0 + L sub 1

      F sub m-1 = L sub 0 + L sub 1 + % ellipsis % + L sub m-2.

      Unlike page tables, the address translation tables for virtual
relational memory, or relation translation tables (RTTs), are two
dimensional and will require two indexes.  Furthemore, in addition to
the base address A sub 'base', the field offsets F sub i have to be
associated with each RTT for a virtual relation such as V.  If A is a
virtual address falling in the range of V, then the first index for
the RTT will be (A - A sub 'base' ) DIV R.  Next, let
                A sub O = (A - A sub 'base')  MOD R.

      Define a field number function F, 0 <=  F <=  m-1, as follows.

             F (A sub O) = 0 if A sub <O> <  F sub <1>,

        F (A sub O) = 1 if F <sub 1> <=  A <sub O> <  F sub 2,

        F (A sub O) = 2 if F <sub 2> <=  A <sub O> <  F sub 3,

                                etc.

      This field number can be computed quickly and efficiently in
hardware, assuming the field offsets have been loaded into
special-purpose hardware registers, for example as shown in Fig. 1.
Note that all the comparisons of A sub O with field offsets can be
done simultaneously.  Also note that the box labelled "+" is not
necessarily an adder; it can be a combinatorial circuit that has as
output the binary number for the number of the highest order input
line that's on.

      Now address translation for V can be described.  If T is the
RTT for V, virtual addres...