Storage and File Structure:Storage for Object-Oriented Databases.

Storage for Object-Oriented Databases∗∗

The ﬁle-organization techniques described in Section 11.7 — the heap, sequential, hashing and clustering organizations — can also be used for storing objects in an object-oriented database. However, some extra features are needed to support object- oriented database features, such as set-valued ﬁelds and persistent pointers.

Mapping of Objects to Files

The mapping of objects to ﬁles is in many ways like the mapping of tuples to ﬁles in a relational system. At the lowest level of data representation, both tuples and the data parts of objects are simply sequences of bytes. We can therefore store object data in the ﬁle structures described in this chapter, with some modiﬁcations which we note next.

Objects in object-oriented databases may lack the uniformity of tuples in relational databases. For example, ﬁelds of records may be sets; in relational databases, in contrast, data are typically required to be (at least) in ﬁrst normal form. Furthermore, objects may be extremely large. Such objects have to be managed differently from records in a relational system.

We can implement set-valued ﬁelds that have a small number of elements using data structures such as linked lists. Set-valued ﬁelds that have a larger number of elements can be implemented as relations in the database. Set-valued ﬁelds of objects can also be eliminated at the storage level by normalization: A relation is created containing one tuple for each value of a set-valued ﬁeld of an object. Each tuple also contains the object identiﬁer of the object. However, this relation is not made visible to the upper levels of the database system. The storage system gives the upper levels of the database system the view of a set-valued ﬁeld, even though the set-valued ﬁeld has actually been normalized by creating a new relation.

Some applications include extremely large objects that are not easily decomposed into smaller components. Such large objects may each be stored in a separate ﬁle. We discuss this idea further in Section 11.9.6.

Implementation of Object Identiﬁers

Since objects are identiﬁed by object identiﬁers (OIDs), an object-storage system needs a mechanism to locate an object, given an OID. If the OIDs are logical OIDs — that is, they do not specify the location of the object — then the storage system must maintain an index that maps OIDs to the actual location of the object. If the OIDs are physical OIDs — that is, they encode the location of the object — then the object can be found directly. Physical OIDs typically have the following three parts:

1. A volume or ﬁle identiﬁer

2. A block identiﬁer within the volume or ﬁle

3. An offset within the block

A volume is a logical unit of storage that usually corresponds to a disk.

In addition, physical OIDs may contain a unique identiﬁer, which is an integer that distinguishes the OID from the identiﬁers of other objects that happened to be stored at the same location earlier, and were deleted or moved elsewhere. The unique identiﬁer is also stored with the object, and the identiﬁers in an OID and the corresponding object should match. If the unique identiﬁer in a physical OID does not match the unique identiﬁer in the object to which that OID points, the system detects that the pointer is a dangling pointer, and signals an error. (A dangling pointer is a pointer that does not point to a valid object.) Figure 11.21 illustrates this scheme.

Such pointer errors occur when physical OIDs corresponding to old objects that have been deleted are used accidentally. If the space occupied by the object had been reallocated, there may be a new object in the location, and it may get incorrectly addressed by the identiﬁer of the old object. If a dangling pointer is not detected, it could cause corruption of a new object stored at the same location. The unique identiﬁer helps to detect such errors, since the unique identiﬁers of the old physical OID and the new object will not match.

Suppose that an object has to be moved to a new block, perhaps because the size of the object has increased, and the old block has no extra space. Then, the physical OID will point to the old block, which no longer contains the object. Rather than change the OID of the object (which involves changing every object that points to this one), we leave behind a forwarding address at the old location. When the database tries to locate the object, it ﬁnds the forwarding address instead of the object; it then uses the forwarding address to locate the object.

Management of Persistent Pointers

We implement persistent pointers in a persistent programming language by using OIDs. In some implementations, persistent pointers are physical OIDs; in others, they are logical OIDs. An important difference between persistent pointers and in-memory pointers is the size of the pointer. In-memory pointers need to be only big enough to address all virtual memory. On most current computers, in-memory pointers are usually 4 bytes long, which is sufﬁcient to address 4 gigabytes of memory. The most recent computer architectures have pointers that are 8 bytes long, Persistent pointers need to address all the data in a database. Since database systems are often bigger than 4 gigabytes, persistent pointers are usually at least 8 bytes long. Many object-oriented databases also provide unique identiﬁers in persistent pointers, to catch dangling references. This feature further increases the size of persistent pointers. Thus, persistent pointers may be substantially longer than in-memory pointers.

The action of looking up an object, given its identiﬁer, is called dereferencing. Given an in-memory pointer (as in C++), looking up the object is merely a memory reference. Given a persistent pointer, dereferencing an object has an extra step — ﬁnding the actual location of the object in memory by looking up the persistent pointer in a table. If the object is not already in memory, it has to be loaded from disk. We can implement the table lookup fairly efﬁciently by using a hash table data structure, but the lookup is still slow compared to a pointer dereference, even if the object is already in memory.

Pointer swizzling is a way to cut down the cost of locating persistent objects that are already present in memory. The idea is that, when a persistent pointer is ﬁrst dereferenced, the system locates the object and brings it into memory if it is not already there. Now the system carries out an extra step — it stores an in-memory pointer to the object in place of the persistent pointer. The next time that the same persistent pointer is dereferenced, the in-memory location can be read out directly, so the costs of locating the object are avoided. (When persistent objects have to be moved from memory back to disk to make space for other persistent objects, the system must carry out an extra step to ensure that the object is still in memory. Correspondingly, when an object is written out, any persistent pointers that it contained and that were swizzled have to be deswizzled, that is, converted back to their per- sistent representation. Pointer swizzling on pointer dereference, as described here, is called software swizzling.

Buffer management is more complicated if pointer swizzling is used, since the physical location of an object must not change once that object is brought into the buffer. One way to ensure that it will not change is to pin pages containing swizzled objects in the buffer pool, so that they are never replaced until the program that performed the swizzling has ﬁnished execution. See the bibliographical notes for more complex buffer-management schemes, based on virtual-memory mapping techniques, that make it unnecessary to pin the buffer pages.

Hardware Swizzling

Having two types of pointers, persistent and transient (in-memory), is inconvenient. Programmers have to remember the type of the pointers, and may have to write code twice — once for the persistent pointers and once for the in-memory pointers. It would be simpler if both persistent and in-memory pointers were of the same type.

A simple way to merge persistent and in-memory pointer types is just to extend the length of in-memory pointers to the same size as persistent pointers, and to use 1 bit of the identiﬁer to distinguish between persistent and in-memory pointers. However, the storage cost of longer persistent pointers will have to be borne by in-memory pointers as well; understandably, this scheme is unpopular.

We shall describe a technique called hardware swizzling, which uses the virtual memory-management hardware present in most current computer systems to address this problem. When data in a virtual memory page are accessed, and the operating system detects that the page does not have real storage allocated for it, or has been access protected, then a segmentation violation is said to occur.3 Many operating systems provide a mechanism to specify a function to be called when a segmentation violation occurs, and a mechanism to allocate storage for a page in virtual address space, and to set that page’s access permissions. In most Unix systems, the

mmap system call provides this latter functionality. Hardware swizzling makes clever use of the above mechanisms.

Hardware swizzling has two major advantages over software swizzling:

1. It is able to store persistent pointers in objects in the same amount of space as in-memory pointers require (along with extra storage external to the object).

2. It transparently converts between persistent pointers and in-memory pointers in a clever and efﬁcient way. Software written to deal with in-memory pointers can thereby deal with persistent pointers as well, without any changes.

Pointer Representation

Hardware swizzling uses the following representation of persistent pointers contained in objects that are on disk. A persistent pointer is conceptually split into two parts: a page identiﬁer in the database, and an offset within the page.4 The page identiﬁer in a persistent pointer is actually a small indirect pointer, which we call the short page identiﬁer. Each page (or other unit of storage) has a translation table that provides a mapping from the short page identiﬁers to full database page identiﬁers. The system has to look up the short page identiﬁer in a persistent pointer in the translation table to ﬁnd the full page identiﬁer.

The translation table, in the worst case, will be only as big as the maximum number of pointers that can be contained in objects in a page; with a page size of 4096, and a pointer size of 4 bytes, the maximum number of pointers is 1024. In practice, the translation table is likely to contain much less than the maximum number of elements (1024 in our example) and will not consume excessive space. The short page identiﬁer needs to have only enough bits to identify a row in the table; with a maximum table size of 1024, only 10 bits are required. Hence, a small number of bits is enough to store the short page identiﬁer. Thus, the translation table permits an entire persistent pointer to ﬁt into the same space as an in-memory pointer. Even though only a few bits are needed for the short page identiﬁer, all the bits of an in-memory pointer, other than the page-offset bits, are used as the short page identiﬁer. This architecture facilitates swizzling, as we shall see.

The persistent-pointer representation scheme appears in Figure 11.22, where there are three objects in the page, each containing a persistent pointer. The translation table gives the mapping between short page identiﬁers and the full database page identiﬁers for each of the short page identiﬁers in these persistent pointers. The database page identiﬁers are shown in the format volume.page.offset.

Each page maintains extra information so that all persistent pointers in the page can be found. The system updates the information when an object is created or deleted in the page. The need to locate all the persistent pointers in a page will become clear later.

Swizzling Pointers on a Page

Initially no page of the database has been allocated a page in virtual memory. Virtual- memory pages may be allocated to database pages even before they are actually loaded, as we will see shortly. Database pages get loaded into virtual-memory when the database system needs to access data on the page. Before a database page is loaded, the system allocates a virtual-memory page to the database page if one has not already been allocated. The system then loads the database page into the virtual- memory page it has allocated to it.

When the system loads a database page P into virtual memory, it does pointer swizzling on the page: It locates all persistent pointers contained in objects in page P , using the extra information stored in the page. It takes the following actions for each persistent pointer in the page. (Let the value of the persistent pointer be (pi, oi), where pi is the short page identiﬁer and oi is the offset within the page. Let Pi be the full page identiﬁer of pi, found in the translation table in page P .)

1. If page Pi does not already have a virtual-memory page allocated to it, the system now allocates a free page in virtual memory to it. The page Pi will reside at this virtual-memory location if and when it is brought in. At this point, the page in virtual address space does not have any storage allocated for it, either in memory or on disk; it is merely a range of addresses reserved for the database page. The system allocates actual space when it actually loads the database page Pi into virtual memory.

2. Let the virtual-memory page allocated (either earlier or in the preceding step) for Pi be vi. The system updates the persistent pointer being considered, whose value is (pi, oi), by replacing pi with vi.

Figure 11.23 shows the state of the page from Figure 11.22 after the system has brought that page into memory and swizzled the pointers in it. Here, we assume that the page whose database page identiﬁer is 679.34278 has been mapped to page 5001 in memory, whereas the page whose identiﬁer is 519.56850 has been mapped to page 4867 (which is the same as the short page identiﬁer). All the pointers in objects have been updated to reﬂect the new mapping, and can now be used as in-memory pointers.

At the end of the translation phase for a page, the objects in the page satisfy an important property: All persistent pointers contained in objects in the page have been converted to in-memory pointers. Thus, objects in in-memory pages contain only in- memory pointers. Routines that use these objects do not even need to know about the existence of persistent pointers! For example, existing libraries written for in-memory objects can be used unchanged for persistent objects. That is indeed an important advantage!

Pointer Dereference

Consider the ﬁrst time that an in-memory pointer to a virtual-memory page vi is dereferenced, when storage has not yet been allocated for the page. As we described, a segmentation violation will occur, and will result in a function call on the database system. The database system takes the following actions:

1. It ﬁrst determines what database page was allocated to virtual-memory page vi; let the full page identiﬁer of the database page be Pi. (If no database page has been allocated to vi, the pointer is incorrect, and the system ﬂags an error.)

2. It allocates storage space for page vi, and loads the database page Pi into virtual-memory page vi.

3. It carries out pointer swizzling out on page Pi, as described earlier in “Swizzling Pointer on a Page”.

4. After swizzling all persistent pointers in P , the system allows the pointer dereference that resulted in the segmentation violation to continue. The pointer dereference will ﬁnd the object for which it was looking loaded in memory.

If any swizzled pointer that points to an object in page vi is dereferenced later, the dereference proceeds just like any other virtual-memory access, with no extra overheads. In contrast, if swizzling is not used, there is considerable overhead in locating the buffer page containing the object and then accessing it. This overhead has to be incurred on every access to objects in the page, whereas when swizzling is performed, the overhead is incurred only on the ﬁrst access to an object in the page. Later accesses operate at regular virtual-memory access speeds. Hardware swizzling thus gives excellent performance beneﬁts to applications that repeatedly dereference pointers.

Optimizations

Software swizzling performs a deswizzling operation when a page in memory has to be written back to the database, to convert in-memory pointers back to persistent pointers. Hardware swizzling can avoid this step — when the system does pointer swizzling for the page, it simply updates the translation table for the page, so that the page-identiﬁer part of the swizzled in-memory pointers can be used to look up the table. For example, as shown in Figure 11.23, database page 679.34278 (with short identiﬁer 2395 in the page shown) is mapped to virtual-memory page 5001. At this point, not only is the pointer in object 1 updated from 2395255 to 5001255, but also the short identiﬁer in the table is updated to 5001. Thus, the short identiﬁer 5001 in object 1 and in the table match each other again. Therefore, the page can be written back to disk without any deswizzling.

Several optimizations can be carried out on the basic scheme described here. When the system swizzles page P , for each page P I referred to by any persistent pointer in P , it attempts to allocate P I to the virtual address location indicated by the short page identiﬁer of P I on page P . If the system can allocate the page in this attempt, pointers to it do not need to be updated. In our swizzling example, page 519.56850 with short page identiﬁer 4867 was mapped to virtual-memory page 4867, which is the same as its short page identiﬁer. We can see that the pointer in object 2 to this page did not need to be changed during swizzling. If every page can be allocated to its appropriate location in virtual address space, none of the pointers need to be translated, and the cost of swizzling is reduced signiﬁcantly.

Hardware swizzling works even if the database is bigger than virtual memory, but only as long as all the pages that a particular process accesses ﬁt into the virtual memory of the process. If they do not, a page that has been brought into virtual

memory will have to be replaced, and that replacement is hard to do, since there may be in-memory pointers to objects in that page.

Hardware swizzling can also be used at the level of sets of pages (often called segments), instead of for a single page. For set-level swizzling, the system uses a single translation table for all pages in the segment. It loads pages in the segment and swizzles them as and when they are required; they need not be loaded all together.

Disk Versus Memory Structure of Objects

The format in which objects are stored in memory may be different from the for- mat in which they are stored on disk in the database. One reason may be the use of software swizzling, where the structures of persistent and in-memory pointers are different. Another reason may be that we want to have the database accessible from different machines, possibly based on different architectures, and from different languages, and from programs compiled under different compilers, all of which result in differences in the in-memory representation.

Consider, for example, a data-structure deﬁnition in a programming language such as C++. The physical structure (such as sizes and representation of integers) in the object depends on the machine on which the program is run.5 Further, the physical structure may also depend on which compiler is used — in a language as complex as C++, different choices for translation from the high-level description to the physical structure are possible, and each compiler can make its own choice.

The solution to this problem is to make the physical representation of objects in the database independent of the machine and of the compiler. The system can convert the object from the disk representation to the form that is required on the speciﬁc machine, language, and compiler, when that object is brought into memory. It can do this conversion transparently at the same time that it swizzles pointers in the object, so the programmer does not need to worry about the conversion.

The ﬁrst step in implementing such a scheme is to deﬁne a common language for describing the structure of objects — that is, a data-deﬁnition language. One such language is the Object Deﬁnition Language (ODL) developed by the Object Database Management Group (ODMG). ODL has mappings deﬁned to the Java, C++, and Smalltalk languages, so potentially we may manipulate objects in an ODMG-compliant database using any of these languages.

The deﬁnition of the structure of each class in the database is stored (logically) in the databases. The code to translate an object in the database to the representation that is manipulated with the programming language (and vice versa) depends on the machine as well as on the compiler for the language. We can generate this code automatically, using the stored deﬁnition of the class of the object.

An unexpected source of differences between the disk and in-memory representations of data is the hidden-pointers in objects. Hidden pointers are transient pointers

that compilers generate and store in objects. These pointers point (indirectly) to tables used to implement certain methods of the object. The tables are typically compiled into executable object code, and their exact location depends on the executable object code; hence, they may be different for different processes. Therefore, when a process accesses an object, the hidden pointers must be ﬁxed to point to the correct location. The hidden pointers can be initialized at the same time that data-representation con- versions are carried out.

Large Objects

Objects may also be extremely large; for instance, multimedia objects may occupy several megabytes of space. Exceptionally large data items, such as video sequences, may run into gigabytes, although they are usually split into multiple objects, each on the order of a few megabytes or less. Large objects containing binary data are called binary large objects (blobs), while large objects containing character data, are called character large objects (clobs), as we saw in Section 9.2.1.

Most relational databases restrict the size of a record to be no larger than the size of a page, to simplify buffer management and free-space management. Large objects and long ﬁelds are often stored in a special ﬁle (or collection of ﬁles) reserved for long-ﬁeld storage.

Allocation of buffer pages presents a problem with managing large objects. Large objects may need to be stored in a contiguous sequence of bytes when they are brought into memory; in that case, if an object is bigger than a page, contiguous pages of the buffer pool must be allocated to store it, which makes buffer management more difﬁcult.

We often modify large objects by updating part of the object, or by inserting or deleting parts of the object, rather than by writing the entire object. If inserts and deletes need to be supported, we can handle large objects by using B-tree structures (which we study in Chapter 12). B-tree structures permit us to read the entire object, as well as to insert and delete parts of the object.

For practical reasons, we may manipulate large objects by using application pro- grams, instead of doing so within the database:

• Text data. Text is usually treated as a byte string manipulated by editors and formatters.

• Image/Graphical data. Graphical data may be represented as a bitmap or as a set of lines, boxes, and other geometric objects. Although some graphical data often are managed within the database system itself, special application software is used for many cases, such as integrated circuit design.

• Audio and video data. Audio and video data are typically a digitized, compressed representation created and displayed by separate application soft- ware. Data are usually modiﬁed with special-purpose editing software, out- side the database system.

The most widely used method for updating such data is the checkout/checkin method. A user or an application would check out a copy of a long-ﬁeld object, operate on this copy with special-purpose application programs, and then check in the modiﬁed copy. Checkout and a checkin correspond roughly to read and write. In some systems, a checkin may create a new version of the object without deleting the old version.

Search This Blog

Database Management System course