fastdb.htm

FastDb是高效的内存数据库系统

GigaBASE has builtin support of spatial data. It provides <code>rectangle</code> type.
By default it has dimension 2 and integer coordinate types. It is possible to easily change
dimension or use floating point coordinates, but recompilation of GigaBASE is needed in 
this case.<P>

It is possible to use this type not only in geographical system for 
representing spatial objects but also in many other cases when date is organized as hyper-cube and queries specify range of values for each dimension, for example:

<PRE>
      select * from CAR where price between 20000 and 30000 
                          and producedYear between 1997 and 1999 
                          and mileage between 50000 and 100000;
</PRE>

If <code>%lt;price, producedYear, milage&gt;</code> are dimensions of the rectangle, 
then this query can be executed using only one indexed search in R-Tree.<P>

Rectangle fields can be indexed - <B>R-Tree</B> index is used in this case
The R-tree provides fast access to spatial data. Basically the idea behind
the R-Tree and the B-Tree are the same:
use a hierarchical structure with a high branching factor to reduce the
number of disk accesses. The R-tree is the extension of the B_tree for a
multidimensional object. A geometric object is represented by its minimum 
bounding rectangle (MBR). Non-leaf nodes contain entries of the form 
(R,<I>ptr</I>) where <I>ptr</I> is a pointer to a child node in the R-tree; R 
is the MBR that covers all rectangles in the child node. Leaf nodes contain 
entries of the form (obj-id, R) where
obj-id is a pointer to the object, and R is the MBR of the object. The main 
innovation in the R-tree is that the father nodes are allowed to overlap. By
this means the R-tree guarantees at least 50% space utilization and remains 
balanced. 
The first R-tree implementation was proposed by Guttman. The Gigabase <B>R-Tree</B>
class is based on Guttman's implementation with a quadratic split algorithm.
The quadratic split algorithm is the one that achieves the best trade-off
between splitting time and search performance.<P>

Rectangle class provides method for calculating distance between two rectangle, 
rectangle area, checking whether two rectangle overlap or one contains another.
Rectangle is specified by coordinates of two it's vertices. Rectangle class
contains array of coordinates. Coordinates of first vertex are placed at the 
beginning of array, and then - coordinates of another vertex.
Each coordinate of first vertex should not be large than correspondent coordinate of 
the second vertex. Singular rectangle with one or more coordinates of first vertex equals 
to the correspondent coordinate of the second vertex are allowed - this is a way of storing
points in the database.<P>

SubSQL provides some special operators for dealing with rectangle. First of all - 
all comparison operators can be used with the following semantic:<P>

<TABLE BORDER ALIGN=CENTER>
<TR><TD><code>a == b</code></TD><TD>Rectangle <code>a</code> is the same as rectangle <code>b</code></TD></TR>
<TR><TD><code>a != b</code></TD><TD>Rectangle <code>a</code> is not the same as rectangle <code>b</code></TD></TR>
<TR><TD><code>a &lt;= b</code></TD><TD>Rectangle <code>b</code> contains rectangle <code>a</code></TD></TR>
<TR><TD><code>a &lt; b</code></TD><TD>Rectangle <code>b</code> contains rectangle <code>a</code> and them are not the same</TD></TR>
<TR><TD><code>a &gt;= b</code></TD><TD>Rectangle <code>a</code> contains rectangle <code>b</code> and are not the same</TD></TR>
<TR><TD><code>a &gt; b</code></TD><TD>Rectangle <code>b</code> contains rectangle <code>a</code> and them are not the same</TD></TR>
</TABLE><P>

Also SubSQL provides <code>overlaps</code> and <code>in</code> operators.
First checks if two rectangles overlap, the second is equivalent to <code>&lt;=</code> operator.
Rectangles can be added - result is minimal rectangle containing both rectangles-operands.
It is possible to access rectangle as array of coordinates - using <code>[index]</code>
notation. Coordinates in query are always returned as real numbers.<P>

Optimizer is able to use spatial index for all comparison operators (except <code>!=</code>)
and for <code>overlaps</code> operator.<P>


<H3><A NAME = "function">Functions</A></H3>
<TABLE BORDER ALIGN="center">
<CAPTION>Predefined functions</CAPTION>
<TR><TH>Name</TH><TH>Argument type</TH><TH>Return type</TH><TH>Description</TH></TR>
<TR><TD>abs</TD><TD>integer</TD><TD>integer</TD><TD>absolute value of the argument</TD</TR>
<TR><TD>abs</TD><TD>real</TD><TD>real</TD><TD>absolute value of the argument</TD</TR>
<TR><TD>area</TD><TD>rectangle</TD><TD>real</TD><TD>area of the rectangle</TD></TR>
<TR><TD>integer</TD><TD>real</TD><TD>integer</TD><TD>conversion of real to integer</TD</TR>
<TR><TD>length</TD><TD>array</TD><TD>integer</TD><TD>number of elements in array</TD</TR>
<TR><TD>lower</TD><TD>string</TD><TD>string</TD><TD>lowercase string</TD</TR><TR><TD>real</TD><TD>integer</TD><TD>real</TD><TD>conversion of integer to real</TD</TR>
<TR><TD>string</TD><TD>integer</TD><TD>string</TD><TD>conversion of integer to string</TD</TR>
<TR><TD>string</TD><TD>real</TD><TD>string</TD><TD>conversion of real to string</TD</TR>
<TR><TD>upper</TD><TD>string</TD><TD>string</TD><TD>uppercase string</TD</TR>
</TABLE><P>

FastDB allows user to define its own functions and operators.
Function should have at least one but no more than 3 parameters of string, integer, 
boolean, reference or user defined (raw binary) type. It should return value of integer, real, string or
boolean type.<P>
User functions should be registered by the <code>USER_FUNC(f)</code> macro, 
which creates a static object of the <code>dbUserFunction</code> class, binding 
the function pointer and the function name.<P>
There are two ways of implementing these functions in application.
First can be used only for functions with one argument. This argument should be of <code>int8, real8,
char*</code> types. And the function return type should be <code>int8, real8, char*</code> or <code>bool</code>.
If function has more than one parameters or it can accept parameters of different types (polymorphism)
then parameters should be passed as reference to <code>dbUserFunctionArgument</code> structure.
This structure contains <code>type</code> field, which value can be used in function implementation to
detect type of passed argument and union with argument value.
The following table contains mapping between argument types and where the value should be taken from:<P>

<TABLE BORDER ALIGN=CENTER>
<TR><TH>Argument type</TH><TH>Argument value</TH><TH>Argument value type</TH></TR>
<TR><TD><code>dbUserFunctionArgument::atInteger</code></TD><TD><code>u.intValue</code></TD><TD><code>int8</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atBoolean</code></TD><TD><code>u.boolValue</code></TD><TD><code>bool</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atString</code></TD><TD><code>u.strValue</code></TD><TD><code>char const*</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atReal</code></TD><TD><code>u.realValue</code></TD><TD><code>real8</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atReference</code></TD><TD><code>u.oidValue</code></TD><TD><code>oid_t</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atRawBinary</code></TD><TD><code>u.rawValue</code></TD><TD><code>void*</code></TD></TR>
</TABLE><P>


For example the following
statements make it possible to use the <code>sin</code> function in SQL
statements:

<PRE>
        #include &lt;math.h&gt;
	...
        USER_FUNC(sin);
</PRE>


Functions can be used only
within the application, where they are defined. Functions are not accessible
from other applications and interactive SQL. If a function returns a string
type , the returned string should be copied by means of the operator
<code>new</code>, because
FastDB will call the destructor after copying the returned value.<P>

In FastDB, the function argument can (but not necessarily must) be enclosed in 
parentheses. So both of the following expressions are valid:

<PRE>
        '$' + string(abs(x))
	length string y
</PRE><P>

Functions with two argument can be also used as operators. Consider the following example, 
in which function <code>contains</code> which performs case insensitive search for substring is defined:

<PRE>
     bool contains(dbUserFunctionArgument& arg1, dbUserFunctionArgument& arg2) { 
         assert(arg1.type == dbUserFunctionArgument::atString 
	     && arg2.type == dbUserFunctionArgument::atString);
         return stristr(arg1.u.strValue, arg2.u.strValue) != NULL;
     }

     USER_FUNC(contains);
    
     dbQuery q1, q2;
     q1 = "select * from TestTable where name contains 'xyz'";
     q2 = "select * from TestTable where contains(name, 'xyz')";
</PRE>

In this example, queries <code>q1</code> and <code>q2</code> are equivalent.<P>



<H2><A NAME = "cpp">C++ interface</A></H2>
One of the primary goals of FastDB is to provide a flexible and convenient
application language interface. Anyone who has  to use 
ODBC or similar SQL interfaces will understand what I am speaking about.
In FastDB, a query can be written in C++ in the following way:<P>

<PRE>
    dbQuery q; 
    dbCursor&lt;Contract&gt; contracts;
    dbCursor&lt;Supplier&gt; suppliers;
    int price, quantity;
    q = "(price >=",price,"or quantity >=",quantity,
        ") and delivery.year=1999";
    // input price and quantity values
    if (contracts.select(q) != 0) { 
        do { 
            printf("%s\n", suppliers.at(contracts->supplier)->company);
        } while (contracts.next());
    } 
</PRE>

<H3><A NAME = "table">Table</A></H3>

Data in FastDB is stored in tables which correspond to C++ classes
whereas the table records correspond to class instances. 
The following C++ types are accepted as atomic components of
FastDB records:<P>

<TABLE BORDER ALIGN="center">
<TR><TH>Type</TH><TH>Description</TH></TR>
<TR><TD>bool</TD><TD>boolean type (<code>true,false</code>)</TD></TR>
<TR><TD>int1</TD><TD>one byte signed integer (-128..127)</TD></TR>
<TR><TD>int2</TD><TD>two bytes signed integer (-32768..32767)</TD></TR>
<TR><TD>int4</TD><TD>four bytes signed integer (-2147483648..2147483647)</TD></TR>
<TR><TD>int8</TD><TD>eight bytes signed integer (-2**63..2**63-1)</TD></TR>
<TR><TD>real4</TD><TD>four bytes ANSI floating point type</TD></TR>
<TR><TD>real8</TD><TD>eight bytes ANSI double precision floating point type</TD></TR>
<TR><TD>char const*</TD><TD>zero terminated string</TD></TR>
<TR><TD>dbReference&lt;T&gt;</TD><TD>reference to class T</TD></TR>
<TR><TD>dbArray&lt;T&gt;</TD><TD>dynamic array of elements of type T</TD></TR>
</TABLE><P>

In addition to types specified in the table above, FastDB records can
also contain nested structures of these components. 
FastDB doesn't support unsigned types to simplify the query language,
to  eliminate bugs caused by signed/unsigned comparison
and to reduce the size of the database engine.<P>

Unfortunately C++ provides no way
to get metainformation about a class at runtime (RTTI is not supported by all 
compilers and also doesn't provide enough information).
Therefore the programmer 
has to explicitly enumerate class fields to be included in the database table 
(it also makes mapping between classes and tables more flexible). 
FastDB provides a set of macros and classes to make such mapping as simple as 
possible.<P>

Each C++ class or structure, which will be used in the database, should 
contain a special method describing its fields. The macro 
<code>TYPE_DESCRIPTOR(</code><I>field_list</I><code>)</code> will construct 
this method. The single argument of this macro is - enclosed in parentheses -
a list of class field descriptors.
If you want to define some methods for the class
and make them available for the database, then the macro 
<code>CLASS_DESCRIPTOR(</code><I>name, field_list</I><code>)</code>
should be used instead of <code>TYPE_DESCRIPTOR</code>. The class name is
needed to get references to member functions.<P>

The following macros can be used for the construction of field
descriptors:

<DL>
<DT><B>FIELD(</B>name<B>)</B><DD>Non-indexed field with specified name.
<DT><B>KEY(</B>name, index_type<B>)</B><DD>Indexed field. <I>index_type</I> 
should be a combination of <code>HASHED</code> and <code>INDEXED</code> flags.
When the <code>HASHED</code> flag is specified, FastDB will create a hash table
for the table using this field as a key. When the <code>INDEXED</code> flag is 
specified, FastDB will create a (special kind of index) T-tree for the table 
using this field as a key. 
<DT><B>UDT(</B>name, index_type, comparator<B>)</B><DD>User defined raw binary type. 
Database deals with this type just as with sequence of bytes of specified size.
This field can be used in query (compared with query parameter of the same type), 
may be indexed and used in <code>order by</code> clause. Comparison is performed by means of
<code>comparator</code> function provided by programmer. Comparator functions receives three
arguments: two pointers to the compared raw binary objects and size of binary object.
The semantic of <I>index_type</I> is the same as of <code>KEY</code> macro.
<DT><B>RAWKEY(</B>name, index<B>)</B><DD>Raw binary type with predefined comparator.
This macro is just specialized version of <code>UDT</code> macro with <code>memcmp</code>
used as comparator.
<DT><B>RAWFIELD(</B>name<B>)</B><DD>One more specialization of <code>UDT</code> macro
for raw binary fields with predefined comparator <code>memcmp</code> and without indices.
<DT><B>SUPERCLASS(</B>name<B>)</B><DD>Specifies information about the base class
(parent) of the current class.
<DT><B>RELATION(</B>reference, inverse_reference<B>)</B>
<DD>Specifies <I>one-to-one, one-to-many</I> or <I>many-to-many</I>
relationships between classes (tables). Both <I>reference</I>
and <I>inverse_reference</I>
fields should be of reference or of array of reference type.
<code>inverse_reference</code> is a field of the referenced table
containing the inverse reference(s) to the current table. Inverse references
are automatically updated by FastDB and are used for query optimization
(see <A HREF="#inverse">Inverse references</A>).
<DT><B>OWNER(</B>reference, inverse_reference<B>)</B>
<DD>Specifies <I>one-to-many</I> or <I>many-to-many</I>
relationship between classes (tables) of owner-member type. 
When owner record is removed all referenced member records are also removed
(cascade delete). If member record has reference to owner class, it should be 
declared with RELATION macro.
<DT><B>METHOD(</B>name<B>)</B><DD>Specifies a method of the class.
The method should be a parameterless instance member function
returning a
boolean, numeric, reference or string type. Methods should be specified after 
all other attributes of the class. 
</DL><P>

Although only atomic fields can be indexed, an index type can be specified 
for structures. The index will be created for components of the structure
only if such type of index is specified in the index type mask of the 
structure. This allows the programmers to enable or disable indices for 
structure fields depending on the role of the structure in the record.<P>

The following example illustrates the creation of a type descriptor 
in the header file:<P>

<PRE>
class dbDateTime { 
    int4 stamp;