Update of /project/elephant/cvsroot/elephant/doc
In directory clnet:/tmp/cvs-serv2708
Modified Files:
data-store-reference.texinfo docstrings.lisp
elephant-design.texinfo elephant.texinfo installation.texinfo
reference.texinfo scenarios.texinfo tutorial.texinfo
user-guide.texinfo
Log Message:
Latest edits, plus integration with Roberts
--- /project/elephant/cvsroot/elephant/doc/data-store-reference.texinfo 2007/04/02 00:51:06 1.6
+++ /project/elephant/cvsroot/elephant/doc/data-store-reference.texinfo 2007/04/27 03:14:55 1.7
@@ -8,16 +8,16 @@
This reference includes functions that need to be overridden, classes
inherited from or other action taken to implement support for a new
-data store backend. Included are the exported elephant functions that
-need methods defined on them as well as the backend-only functions
-exported in backends.lisp. Some functions here are utilities from the
+data store. Included are the exported elephant functions that
+need methods defined on them as well as the data-store-only functions
+exported in data-store-api.lisp. Some functions here are utilities from the
main elephant package that support store implementations, but are not
required. Migration, class indices and query interfaces are
implemented on top of the store API and require no special support by
implementors.
-Because the number of backend implementors is small, this is a minimal
-documentation set intended to serve as an initial guide and a
+Because the number of data store implementors is small, this is a
+minimal documentation set intended to serve as an initial guide and a
reference. However, it is anticipated that some interaction will be
needed with the developers to properly harden a datastore for release.
@@ -25,7 +25,7 @@
relevant to them.
@menu
-* Registration: DSR Registration. Register the backend to parse controller specifications.
+* Registration: DSR Registration. Register the data store for the appropriate controller specifications.
* Store Controllers: DSR Store Controllers. Subclassing the store controller.
* Handling Serialization: DSR Handling Serialization. Available facilities for serializing objects.
* Memory Utilities: DSR Memory Utilities. Writing primitive C types.
@@ -43,22 +43,22 @@
@cindex Registration and Initialization
Elephant looks at the first element of the specification list to
-determine which backend code base to use. The master table for this
-information is @code{*elephant-backends*} in elephant/controller.lisp.
-This will need to be augmented for every backend with the
+determine which data store module to use. The master table for this
+information is @code{*elephant-data-stores*} in elephant/controller.lisp.
+This will need to be augmented for every data store with the
specification keyword tag to be used (such as @code{:BDB} or
@code{:CLSQL}) and the required asdf dependencies.
-In addition, the backend source should use an eval-when statement to
+In addition, the data store source should use an eval-when statement to
call the following function:
-@include includes/fun-elephant-backend-register-backend-con-init.texinfo
+@include includes/fun-elephant-data-store-register-data-store-con-init.texinfo
-If the backend requires any special user-specified configuration,
+If the data store requires any special user-specified configuration,
augment the key types in config.sexp with what you need and use the
following function to access.
-@include includes/fun-elephant-backend-get-user-configuration-parameter.texinfo
+@include includes/fun-elephant-data-store-get-user-configuration-parameter.texinfo
@node DSR Store Controllers
@comment node-name, next, previous, up
@@ -69,25 +69,25 @@
which are called by open-store and close-store respectively.
@include includes/class-elephant-store-controller.texinfo
-@include includes/fun-elephant-backend-open-controller.texinfo
-@include includes/fun-elephant-backend-close-controller.texinfo
-@include includes/fun-elephant-backend-connection-is-indeed-open.texinfo
+@include includes/fun-elephant-data-store-open-controller.texinfo
+@include includes/fun-elephant-data-store-close-controller.texinfo
+@include includes/fun-elephant-data-store-connection-is-indeed-open.texinfo
For upgrading and opening legacy databases it is important that a
store be able to indicate which version of elephant was used to create
it. This governs the chosen serializer, mappings between elephant
symbols used in an old vs. new version, etc. Because this is called
to initialize the serializer, it must directly implemented by the
-backend without using the serializer.
+data store without using the serializer.
-@include includes/fun-elephant-backend-database-version.texinfo
+@include includes/fun-elephant-data-store-database-version.texinfo
There are some utilities for serializing simple data without a
serializer using the memutil package.
-@include includes/fun-elephant-backend-serialize-database-version-key.texinfo
-@include includes/fun-elephant-backend-serialize-database-version-value.texinfo
-@include includes/fun-elephant-backend-deserialize-database-version-value.texinfo
+@include includes/fun-elephant-data-store-serialize-database-version-key.texinfo
+@include includes/fun-elephant-data-store-serialize-database-version-value.texinfo
+@include includes/fun-elephant-data-store-deserialize-database-version-value.texinfo
@node DSR Persistent Objects and Slot Access
@@ -106,22 +106,22 @@
that functions such as map-btree do not need a store-controller
argument. (NOTE: Should this function be user visible?)
-@include includes/fun-elephant-backend-get-con.texinfo
+@include includes/fun-elephant-data-store-get-con.texinfo
All objects require a unique object identifier. During new object
-creation the backend is asked to produce a unique id.
+creation the data store is asked to produce a unique id.
-@include includes/fun-elephant-backend-next-oid.texinfo
+@include includes/fun-elephant-data-store-next-oid.texinfo
These functions are called by the metaclass protocol to implement the
appropriate operations on persistent class slots. Unless protected by
a transaction, the side effects of these functions should be atomic,
persistent and visible to other threads on completion.
-@include includes/fun-elephant-backend-persistent-slot-writer.texinfo
-@include includes/fun-elephant-backend-persistent-slot-reader.texinfo
-@include includes/fun-elephant-backend-persistent-slot-boundp.texinfo
-@include includes/fun-elephant-backend-persistent-slot-makunbound.texinfo
+@include includes/fun-elephant-data-store-persistent-slot-writer.texinfo
+@include includes/fun-elephant-data-store-persistent-slot-reader.texinfo
+@include includes/fun-elephant-data-store-persistent-slot-boundp.texinfo
+@include includes/fun-elephant-data-store-persistent-slot-makunbound.texinfo
@node DSR Collections
@comment node-name, next, previous, up
@@ -137,9 +137,9 @@
@include includes/class-elephant-btree-index.texinfo
@include includes/class-elephant-indexed-btree.texinfo
-To create the backend-appropriate type of btree, the backend
+To create the data store-appropriate type of btree, the data store
implements this method (and possibly related methods) aginst their store-controller.
-@include includes/fun-elephant-backend-build-btree.texinfo
+@include includes/fun-elephant-data-store-build-btree.texinfo
Most of the user-visible operations over BTrees must be implemented.
Class indexing functions such as @code{map-class} and
@@ -181,19 +181,19 @@
These functions must be implemented or stubbed by all data stores.
-@include includes/fun-elephant-backend-execute-transaction.texinfo
+@include includes/fun-elephant-data-store-execute-transaction.texinfo
-@include includes/fun-elephant-backend-controller-start-transaction.texinfo
-@include includes/fun-elephant-backend-controller-commit-transaction.texinfo
-@include includes/fun-elephant-backend-controller-abort-transaction.texinfo
+@include includes/fun-elephant-data-store-controller-start-transaction.texinfo
+@include includes/fun-elephant-data-store-controller-commit-transaction.texinfo
+@include includes/fun-elephant-data-store-controller-abort-transaction.texinfo
These are supporting functions and variables for implementing
transactions.
-@include includes/var-elephant-backend-star-current-transaction-star.texinfo
-@include includes/fun-elephant-backend-make-transaction-record.texinfo
-@include includes/fun-elephant-backend-transaction-store.texinfo
-@include includes/fun-elephant-backend-transaction-object.texinfo
+@include includes/var-elephant-data-store-star-current-transaction-star.texinfo
+@include includes/fun-elephant-data-store-make-transaction-record.texinfo
+@include includes/fun-elephant-data-store-transaction-store.texinfo
+@include includes/fun-elephant-data-store-transaction-object.texinfo
;; Designer considerations:
;; - with-transaction passes *current-transaction* or the user parameter to execute-transaction
@@ -229,7 +229,7 @@
@section Handling Serialization
@cindex Serialization
-Backends must initialize @ref{Class elephant:store-controller} with
+Data stores must initialize @ref{Class elephant:store-controller} with
internal serializer functions. Packages @code{elephant-serializer1}
and @code{elephant-serializer2} contains serialize and deserialize
methods on buffer-streams as defined in @code{elephant-memutil}. The
@@ -240,18 +240,18 @@
NOTE: This should perhaps become entirely the job of the data store to
decide how to serialize values and for a specific version, what
serializer to use. The elphant main package can define serializers
-for use by different backends.
+for use by different data stores.
@end verbatim
-@include includes/fun-elephant-backend-serialize.texinfo
-@include includes/fun-elephant-backend-deserialize.texinfo
+@include includes/fun-elephant-data-store-serialize.texinfo
+@include includes/fun-elephant-data-store-deserialize.texinfo
These utility functions are useful if a data store does not have the
ability to store variable length binary data. They are based on the
@code{cl-base64} library.
-@include includes/fun-elephant-backend-serialize-to-base64-string.texinfo
-@include includes/fun-elephant-backend-deserialize-from-base64-string.texinfo
+@include includes/fun-elephant-data-store-serialize-to-base64-string.texinfo
+@include includes/fun-elephant-data-store-deserialize-from-base64-string.texinfo
@node DSR Memory Utilities
@comment node-name, next, previous, up
--- /project/elephant/cvsroot/elephant/doc/docstrings.lisp 2004/09/19 17:44:43 1.1
+++ /project/elephant/cvsroot/elephant/doc/docstrings.lisp 2007/04/27 03:14:55 1.2
@@ -759,7 +759,9 @@
escaped in symbol names, but if a docstring contains invalid Texinfo
markup, you lose."
(handler-bind ((warning #'muffle-warning))
- (let ((directory (merge-pathnames (pathname directory))))
+ (let ((directory (merge-pathnames (pathname directory)))
+ (*print-right-margin* 200))
+ (declare (special *print-miser-width*))
(ensure-directories-exist directory)
(dolist (package packages)
(dolist (doc (collect-documentation (find-package package)))
--- /project/elephant/cvsroot/elephant/doc/elephant-design.texinfo 2007/04/21 17:22:35 1.4
+++ /project/elephant/cvsroot/elephant/doc/elephant-design.texinfo 2007/04/27 03:14:55 1.5
@@ -1,5 +1,6 @@
@c -*-texinfo-*-
+@c *** FINISH ***
@node Elephant Architecture
@comment node-name, next, previous, up
@chapter Elephant Architecture
@@ -10,17 +11,13 @@
support easy upgrading, repository migration, shared functionality
between data stores and general hygene.
-The current architecture is modularized into the following pieces:
+The architecture has been carefully modularized:
-@verbatim
-[Picture describing] Metaclass, Store controller, persistent objects,
-data stores, serializer & memutils. Derived features such as class
-indexing, migration, query system and root operations can also be
-illustrated?
-@end verbatim
+(a)image{ArchDiagram,,4.5in,[Architecture Diagram],.png}
To get a feeling for what is happening inside elephant, it is probably
-most useful to walk through the various major protocols:
+best to walk through the various major protocols to see how these
+components participate in implementing them.
@itemize
@item Initialization of a store controller
@@ -32,23 +29,247 @@
@section Initializing a store controller
-When the main elephant @code{open-store} function is called, it calls
-@code{get-controller} which grabs an existing store controller if the
-spec is identical, or builds a new controller. Building the
-controller requires loading any dependencies via asdf, calling a
-backend initialization function (if it is the first instance of that
-backend being created), and then calling an initialization function
-that returns a @code{store-controller} subclass instance specific to
-that backend.
+When the main elephant @code{open-store} function is called with a
+specification, it calls get-controller which first checks to see if a
+controller already exists for that spec.
+
+If there is no controller, it calls @code{build-controller} to
+construct one. If the data store code base is not present,
+@code{load-data-store} is called to ensure that any asdf dependencies
+are satisfied. The associations for asdf dependencies are statically
+configured in @code{*elephant-data-stores*} for each data store type
+supported by elephant.
+
+While being loaded, the data store is responsible for calling
+@code{register-data-store-con-init} to register a data store
+initialization function for its spec type (i.e. :BDB or :CLSQL).
+For example, from bdb-controller.lisp:
+
+@lisp
+(eval-when (:compile-toplevel :load-toplevel)
+ (register-data-store-con-init :bdb 'bdb-test-and-construct))
+@end lisp
+
+This mapping between spec types and initialization functions is
+accessed by @code{lookup-data-store-con-init} from within
+@code{build-controller}. The function returned by
+@code{lookup-data-store-con-init} is passed the full specification and
+returns a @code{store-controller} subclass instance for the specified
+data store.
+
+The new controller is stored in the @code{*dbconnection-spec*} hash
+table, associating the object with its specification. Finally
+Elephant calls open-controller to actually establish a connection to
+or create the files of the data store.
+
+Finally, if the default store controller @code{*store-controller*} is
+nil, it will be initialized with the new store controller, otherwise
+the original value is left in @code{*store-controller*} until that
+store controller is closed using @code{close-store}.
-Elephant than calls open-controller to actually establish a connection
-to or create the files of the data store.
+The data store implementor has access to various utilities to aid
+initialization.
+
+@itemize
+@item @code{get-user-configuration-parameter} - Access symbol tags
+ in my-config.sexp to access data store specific user
+configuration. You can also add special variables to variables.lisp
+and add a tag-variable pair to @code{*user-configurable-parameters*}
+in variables.lisp to automatically initialize it when the store
+controller is opened.
+@item @code{get-con} behavior when store is closed or lost
+@item @code{database-version} a store controller implements this
+ in order to tell Elephant what serializer to use. Currently,
+ version 0.6.0 databases use serializer1 and all later database
+ use serializer version 2. This is to ensure that a given version
+ of the Elephant code can open databases from prior versions in
+ order to properly upgrade to the new code base.
+@item Symbol conversions. To aid in opening legacy databases, a
+ symbol conversion facility is provided in controller.lisp to
+ be applied to any symbols extracted from the legacy data store.
+ (if, for instance, the type name of subclasses changed, such as
+ sleepycat-btree becoming bdb-btree)
+@end itemize
+
+At this point, all operations referencing the store controller should
+be able to proceed.
+
+At the end of a session,
@section Persistent Object Creation
+
+The only thing that a data store has to do to support new object
+creation, other than implement the slot protocol, is implement the
+method @code{next-oid} to return the next unique object id for the
+persistent object being created.
+
+Existing objects are created during deserialization of object
+references. The serializer subsystem is built-into the core of
+elephant and can be used by data stores. The serializer is abstracted
+so that multiple serializers can be co-resident and the data store can
+choose the appropriate one. The abstraction boundary between the
+serializer, the data store, and the core Elephant system is not
+perfect, so be aware and refer to existing data store implementations
+if in doubt.
+
+A serializer takes as arguments the store-controller, lisp object and
+a @code{buffer-stream} from the memory utility library and returns the
+buffer-stream with the binary serialized object. The deserializer
+reverses this process. For all lisp objects except persistent
+classes, this means reallocating the storage space for the object and
+recreating all its contents. Deserializing a standard object results
+in a new standard object of the same class with the same slot values.
+
+Persistent classes are dealt with specially. When a persistent object
+is serialized, it's oid and class are stored in the
+@code{buffer-stream}. On deserialization it uses the oid to check in
+the store-controller's cache for an existing placeholder object. If
+the cache misses, then it creates a new placeholder object using the
+class and oid as described in @xref{Persistent Classes and Objects}.
+The store controller contains a cache instance that is automatically
+initialized by the core Elephant object protocol.
+
+Currently the serializer is selected by the core Elephant code based
+on the store controller's database version. See the reference section
+for details on implementing the store-controller database version
+method. It is a relatively small change to have the data store choose
+its own serializer, however we will have to tighten up and document
+the contracts between the Elephant core code, serializer and data store.
+
@section Persistent Slot Protocol
-@section Persistent Slot Protocol
-@section Persistent Collection Protocol
+
+The core protocol that the data store needs to support is the slot
+access protocol. During object initialization, these functions are
+called to initialize the slots of the object. The four functions are:
+
+@itemize
+@item @code{persistent-slot-reader}
+@item @code{persistent-slot-writer}
+@item @code{persistent-slot-boundp}
+@item @code{persistent-slot-makunbound}
+@end itemize
+
+More details can be found in the data store api reference section. In
+short, these functions specialize on the specific @code{store-controller} of
+the data store and take instances, values and slotnames as appropriate.
+
+Typically the oid will be extracted from the instance and be used to
+update a table or record where the oid and slotname identifies the
+value. A slot is typically unbound when no value exists (as opposed to
+nil).
+
+@section Persistent Collection Protocols
+
+The BTree protocol is the most extensive interface that data stores must
+implement. Data store implementations are required to subclass the
+abstract classes @code{btree}, @code{indexed-btree}, and @code{index}
+and implement their complete APIs. Each class type is constructed
+by Elephant using a @code{store-controller} that builds them. These
+methods are @code{build-btree}, @code{build-indexed-btree} and
+@code{build-index}.
+
+The @code{get-value} interface is similar to the persistent
+slot reader and writer, but instead of using oid and slotname to set
+values, it uses the btree oid and a key value as a unique identifier
+for a value.
+
+The BTree protocol almost requires an actual BTree implementation to
+be at all efficient. Keys and values need to be accessible via the
+cursor API, which means they need to be walked linearly in the sort
+order of the keys (described in @xref{Persistent BTrees}).
+
+An indexed BTree automatically maintains a hash table of the indices
+defined on it so that users can access them by mapping or
+lookup-by-name. The data store also has access to this interface.
+
+A BTree index must also maintain a connection to its parent BTree so
+that an index value can be used as a primary tree key to retrieve the
+primary BTree value as part of the @code{cursor-pnext} and
+@code{cursor-pprev} family of methods.
+
+The contract of @code{remove-kv} is that the storage in the data store
+is actually freed for reuse.
+
+Persistent set implemenation is optional. A default BTree based
+implementation is provided by default
+
@section Implementing Transactions
+One of the most important pieces of functionality remaining to discuss
+is implementing transactions. In existing data stores, transactions
+are merely extensions of the underlying start, commit and abort
+methods of the 3rd party library or server being used. The Elephant
+user interfaces to these functions in two ways: a call to
+@code{execute-transaction} or explicit calls to @code{controller-start-transaction},
+@code{controller-commit-transaction} and @code{controller-abort-transaction}.
+
+@subsection Implementing Execute Transaction
+
+The macros @code{with-transaction} and @code{ensure-transaction} wrap
+access to the data store's @code{execute-transaction}. This function
+has a rich contract. It accepts as arguments the store controller, a
+closure that executes the transaction body and a set of keywords.
+Keywords required to be supported by the method (or ignored without
+loss of semantics) are @code{:parent} and @code{:retries}.
+
+The semantics of @code{with-transaction} are that a new transaction
+will always be requested of the data store. If a transaction exists,
+@code{ensure-transaction} will merely call the transaction closure.
+If not it will function as a call to @code{with-transaction}.
+
+@code{execute-transaction} is that it must ensure that the transaction
+closure is executed within a dynamic context that insures the ACID
+properties of any database operations (@code{pset},@code{btree} or
+persistent slot operations). If there is a non-local exit during this
+execution, the transaction should be aborted. If it returns normally,
+the transaction is committed. The integer in the @code{:retries}
+argument dictates how many times @code{execute-transaction} should
+retry the transaction before failing.
+
+Elephant provides some bookkeeping to the data store to help with
+nested transactions by using the @code{*current-transaction*} dynamic
+variable. In the dynamic context of the transaction closure, another
+call to @code{execute-transaction} may occur with the transaction
+argument defaulting to the value of @code{*current-transaction*}. The
+data store has to decide how to handle these cases. To support this,
+the first call to execute transaction can create a dynamic binding for
+@code{*current-transaction*} using the @code{make-transaction-record}
+call. This creates a transaction object that records the store
+controller that started the transaction and any data store-specific
+transaction data.
+
+The current policy is that the body of a transaction is executed with
+the @code{*store-controller*} variable bound to the store-controller
+object creating the transaction. This is important for default
+arguments and generally helps more than it hurts, so is an
+implementation requirement placed on @code{execute-transaction}.
+
+If two nested calls to @code{with-transaction} are made successively
+in a dynamic context, the data store can create true nested
+transactions. The first transaction is passed to the @code{:parent}
+argument of the second. The second can choose to just continue the
+current transaction (the CLSQL data store policy) or to nest the
+transaction (the BDB data store policy).
+
+@subsection Interleaving Multiple Store Transactions
+
+Finally, some provision is made for the case where two store
+controllers have concurrently active transactions in the same thread.
+This feature was created to allow for migration, where a read from one
+database happens in one transaction, and while active has to writes to
+another data store with a valid transaction.
+
+The trick is that @code{with-transaction} checks to see if the current
+transaction object is the same as the @code{store-controller} object
+passed to the @code{:store-controller} argument. If not, a fresh
+transaction is started.
+
+Currently no provision is made for more than two levels of multi-store
+nesting as we do not implement a full transaction stack (to avoid
+walking the stack on each call to handle this rare case). If a third
+transaction is started by the store controller that started the first
+transaction, it will have no access to the parent transaction which
+may be a significant source of problems for the underlying database.
+
--- /project/elephant/cvsroot/elephant/doc/elephant.texinfo 2007/04/21 17:22:35 1.9
+++ /project/elephant/cvsroot/elephant/doc/elephant.texinfo 2007/04/27 03:14:55 1.10
@@ -6,8 +6,8 @@
@copying
Original Version, Copyright @copyright{} 2004 Ben Lee and Andrew Blumberg.
-2006 SQL Backend, Copyright @copyright{} 2006 Robert L. Read.
-2007 Rewrite, Copyright @copyright{} 2007 Ian Eslick.
+Version 0.5, Copyright @copyright{} 2006 Robert L. Read.
+Versions 0.6-0.9, Copyright @copyright{} 2006-2007 Ian Eslick and Robert L. Read
@quotation
Permission is granted to copy, distribute and/or modify this document
@@ -21,7 +21,7 @@
@titlepage
@title Elephant User Manual
@subtitle Elephant version 0.9
-@author Ian Eslick and Ben Lee
+@author By Ian Eslick with Robert Read and Ben Lee
@c The following two commands
@c start the copyright page.
--- /project/elephant/cvsroot/elephant/doc/installation.texinfo 2007/04/21 17:22:35 1.10
+++ /project/elephant/cvsroot/elephant/doc/installation.texinfo 2007/04/27 03:14:55 1.11
@@ -212,7 +212,8 @@
...
=> #<BDB-STORE-CONTROLLER>
-(open-store '(:CLSQL (:POSTGRESQL "localhost.localdomain" "mydb" "myuser" ""))))
+(open-store '(:CLSQL (:POSTGRESQL "localhost.localdomain"
+ "mydb" "myuser" ""))))
...
ASDF loading messages
...
--- /project/elephant/cvsroot/elephant/doc/reference.texinfo 2007/04/25 02:27:56 1.12
+++ /project/elephant/cvsroot/elephant/doc/reference.texinfo 2007/04/27 03:14:55 1.13
@@ -8,21 +8,23 @@
@menu
* Store Controllers:: Connecting to a data store.
-* Persistent Objects:: Defining persistent classes and creating and manipulating persistent indices.
-* Persistent Object Indexing:: Convenient indexing of persistent classes.
-* Persistent Sets:: Maintaining persistent collections the easy way.
+* Persistent Object API:: Defining persistent classes and creating and manipulating persistent indices.
+* Persistent Object Indexing API:: Convenient indexing of persistent classes.
+* Persistent Set API:: Maintaining persistent collections the easy way.
@c * Query Interfaces:: Finding instances.
-* BTrees:: BTrees and indices, a low level persistent data structure.
-* Cursors:: Traversing BTrees.
-* Transactions:: Transactions.
-* Migration and Upgrading:: Migration and upgrading.
-* Miscellaneous:: Other functions and data store specific functions
+* BTree API:: BTrees and indices, a low level persistent data structure.
+* Cursor API:: Traversing BTrees.
+* Index Cursor API:: Traversing BTree Indicies.
+* Transaction API:: Transaction functions.
+* Migration and Upgrading API:: Migration and upgrading.
+* Miscellaneous API:: Other functions and data store specific functions
@end menu
-@node Store Controllers
+@node Store Controller API
@comment node-name, next, previous, up
-@section Store Controllers
-@cindex Store Controllers
+@section Store Controller API
+@cindex Store Controller
+@cindex API
Store controllers provide the persistent storage for CLOS objects and
BTree collections. Any persistent operations must be done in the
@@ -45,10 +47,11 @@
@include includes/fun-elephant-root-existsp.texinfo
@include includes/fun-elephant-map-root.texinfo
-@node Persistent Objects
+@node Persistent Object API
@comment node-name, next, previous, up
-@section Persistent Objects
+@section Persistent Object API
@cindex Persistent Objects
+@cindex API
@ref{Class elephant:persistent-metaclass} can be used as the
:metaclass argument in a defclass form to create a persistent object.
@@ -58,15 +61,17 @@
@include includes/macro-elephant-defpclass.texinfo
@include includes/fun-elephant-drop-pobject.texinfo
-@node Persistent Object Indexing
+@node Persistent Object Indexing API
@comment node-name, next, previous, up
-@section Persistent Object Indexing
+@section Persistent Object Indexing API
@cindex Persistent Object Indexing
+@cindex API
+
@subsection Indexed Object Accessors
@include includes/fun-elephant-map-class.texinfo
-@include includes/fun-elephant-map-class-index.texinfo
+@include includes/fun-elephant-map-inverted-index.texinfo
@include includes/fun-elephant-get-instances-by-class.texinfo
@include includes/fun-elephant-get-instance-by-value.texinfo
@@ -93,10 +98,10 @@
@include includes/fun-elephant-add-class-derived-index.texinfo
@include includes/fun-elephant-remove-class-derived-index.texinfo
-@node Persistent Sets
+@node Persistent Set API
@comment node-name, next, previous, up
-@section Persistent Sets
-@cindex Persistent Sets
+@section Persistent Set API
+@cindex Persistent Set API
Persistent sets are a simple persistent collection abstraction. They
maintain an unordered collection of objects. Unlike the normal
@@ -125,10 +130,12 @@
@c @include includes/fun-elephant-get-query-results.texinfo
@c @include includes/fun-elephant-map-class-query.texinfo
-@node BTrees
+@node BTree API
@comment node-name, next, previous, up
-@section BTrees
-@cindex BTrees
+@section BTree API
+@cindex BTree
+@cindex API
+
Persistent collections inherit from @ref{Class elephant:persistent-collection}
and consist of the @ref{Class elephant:btree}, @ref{Class elephant:indexed-btree} and
@@ -142,29 +149,40 @@
@include includes/fun-elephant-setf-get-value.texinfo
@include includes/fun-elephant-remove-kv.texinfo
@include includes/fun-elephant-existsp.texinfo
-
+@include includes/fun-elephant-drop-btree.texinfo
@include includes/fun-elephant-map-btree.texinfo
-@include includes/fun-elephant-map-index.texinfo
+
+These functions are only defined on indexed btrees.
+
+@include includes/fun-elephant-make-indexed-btree.texinfo
@include includes/fun-elephant-add-index.texinfo
@include includes/fun-elephant-get-index.texinfo
@include includes/fun-elephant-get-primary-key.texinfo
@include includes/fun-elephant-remove-index.texinfo
-@include includes/fun-elephant-drop-pset.texinfo
-@node Cursors
+This function is only valid for indexes.
+
+@include includes/fun-elephant-map-index.texinfo
+
+@node Cursor API
@comment node-name, next, previous, up
-@section Cursors
+@section Cursor API
@cindex Cursors
+@cindex API
Cursors are objects of type cursor (@pxref{Class elephant:cursor})
-which provide methods for complex traversals of BTrees.
+which provide methods for complex traversals of BTrees.
@include includes/macro-elephant-with-btree-cursor.texinfo
@include includes/fun-elephant-make-cursor.texinfo
@include includes/fun-elephant-cursor-close.texinfo
-
@include includes/fun-elephant-cursor-duplicate.texinfo
+@include includes/fun-elephant-cursor-initialized-p.texinfo
+
+Each of the following methods return multiple values consisting of
+@code{(exists? key value)}.
+
@include includes/fun-elephant-cursor-current.texinfo
@include includes/fun-elephant-cursor-first.texinfo
@include includes/fun-elephant-cursor-last.texinfo
@@ -177,6 +195,25 @@
@include includes/fun-elephant-cursor-delete.texinfo
@include includes/fun-elephant-cursor-put.texinfo
+@node Index Cursor API
+@comment node-name, next, previous, up
+@section Cursor API
+@cindex Cursors
+@cindex Index
+@cindex Indices
+@cindex API
+
+Index cursors are made the same way standard cursors are, with a call
+to @code{make-cursor}, except with the index as the argument instead
+of a standard btree. In addition to the standard cursor operations,
+which provide the direct key and value of a @code{btree-index}, the
+following class of ``p'' cursors work on an index and allow you to get
+the primary value of the @code{indexed-btree} that the
+@code{btree-index} belongs to.
+
+They each return multiple values @code{(exists? key primary-value
+primary-key)}.
+
@include includes/fun-elephant-cursor-pcurrent.texinfo
@include includes/fun-elephant-cursor-pfirst.texinfo
@include includes/fun-elephant-cursor-plast.texinfo
@@ -194,10 +231,11 @@
@include includes/fun-elephant-cursor-prev-nodup.texinfo
@include includes/fun-elephant-cursor-pprev-nodup.texinfo
-@node Transactions
+@node Transaction API
@comment node-name, next, previous, up
-@section Transactions
-@cindex Transactions
+@section Transaction API
+@cindex Transaction API
+@cindex API
@include includes/macro-elephant-with-transaction.texinfo
@@ -210,10 +248,11 @@
@include includes/fun-elephant-controller-abort-transaction.texinfo
@include includes/fun-elephant-controller-commit-transaction.texinfo
-@node Migration and Upgrading
+@node Migration and Upgrading API
@comment node-name, next, previous, up
-@section Migration and Upgrading
+@section Migration and Upgrading API
@cindex Migration and Upgrading
+@cindex API
Upgrade is a call to Migrate with checks for compatability. The
migrate methods are included here in case you wish to develop a more
--- /project/elephant/cvsroot/elephant/doc/scenarios.texinfo 2007/04/25 03:18:13 1.8
+++ /project/elephant/cvsroot/elephant/doc/scenarios.texinfo 2007/04/27 03:14:55 1.9
@@ -82,7 +82,9 @@
(unless *system
(let ((appname (get-application-name))
(url (get-system-url)))
- (setf *system* (make-instance 'system-object :name appname :url url))))
+ (setf *system* (make-instance 'system-object
+ :name appname
+ :url url))))
*system*)
(sys-object)
@@ -102,7 +104,8 @@
(defclass system-object ()
((appname :accessor system-appname :initarg :name)
(url :accessor system-url :initarg :url)
- (laststate :accessor system-laststate :initarg :state :initform 'idle)
+ (laststate :accessor system-laststate :initarg :state
+ :initform 'idle)
(state :accessor system-state :initarg :state :transient t)
(:metaclass persistent-metaclass))
@@ -163,7 +166,8 @@
@lisp
(defclass phash ()
- ((btree :accessor phash-btree :initarg :btree :initform (make-btree))))
+ ((btree :accessor phash-btree :initarg :btree
+ :initform (make-btree))))
(defun make-persistent-hash (name)
(let ((btree (get-from-root name)))
@@ -423,7 +427,8 @@
:transient t)
(touched :accessor snapshot-set-touched
:initform (make-array 20 :element-type 'fixnum
- :initial-element 0 :fill-pointer t :adjustable t)
+ :initial-element 0 :fill-pointer t
+ :adjustable t)
:transient t))
(:documentation "Keeps track of a set of standard objects
allowing a single snapshot call to update the store
@@ -455,7 +460,8 @@
@lisp
(defmethod register-object ((object standard-object) (set snapshot-set))
- "Register a standard object. Not recorded until snapshot is called on db"
+ "Register a standard object. Not recorded until
+ the snapshot function is called on db"
(aif (lookup-cached-id object set)
(values object it)
(let ((id (incf (snapshot-set-next-id set))))
@@ -506,8 +512,11 @@
(defmethod snapshot ((set snapshot-set))
"Saves all objects in the set (and any objects reachable from the
current set of objects) to the persistent store"
- (with-transaction (:store-controller (get-con (snapshot-set-index set)))
- (loop for (obj . id) in (get-cache-entries (snapshot-set-cache set)) do
+ (with-transaction (:store-controller (get-con
+ (snapshot-set-index set)))
+ (loop for (obj . id) in
+ (get-cache-entries (snapshot-set-cache set))
+ do
(save-snapshot-object id obj set))
(collect-untouched set)))
@@ -581,11 +590,12 @@
@lisp
(defmethod restore ((set snapshot-set))
- "Restores a snapshot by setting the snapshot-set state to the last snapshot.
- If this is used during runtime, the user needs to drop all references
- to objects and retrieve again from the snapshot set. Also used to initialize
- the set state when a set is created, for example pulled from the root of a
- store-controller, unless :lazy-load is specified"
+ "Restores a snapshot by setting the snapshot-set state to the last
+snapshot. If this is used during runtime, the user needs to drop all
+references to objects and retrieve again from the snapshot set. Also
+used to initialize the set state when a set is created, for example
+pulled from the root of a store-controller, unless :lazy-load is
+specified"
(clear-cache set)
(map-btree (lambda (id object)
(load-snapshot-object id object set))
@@ -597,7 +607,8 @@
(load-proxy-object id object set))
((hash-table-p object)
(load-proxy-hash id object set))
- (t (error "Unrecognized type ~A for id ~A in set ~A" (type-of object) id set)))))
+ (t (error "Unrecognized type ~A for id ~A in set ~A"
+ (type-of object) id set)))))
@end lisp
If an object has a reference object in a slot, then we simply restore
@@ -700,7 +711,8 @@
hash table indirections with a little macro:
@lisp
-(defmacro def-snapshot-reference-wrapper (accessor-name (source-classname target-classname hashname uid))
+(defmacro def-snapshot-wrapper
+ (accessor-name (source-classname target-classname hashname uid))
(with-gensysms (obj key ref)
`(progn
(defmethod ,accessorname :around ((,obj ,source-classname))
@@ -723,7 +735,8 @@
((pointer-to-island2 :accessor child :initform nil)
(pointer-to-island1 :accessor neighbor :initform nil)))
-(def-snapshot-reference-wrapper neighbor (island2 island1 *island1-hash* *unique-id*))
+(def-snapshot-wrapper neighbor
+ (island2 island1 *island1-hash* *unique-id*))
@end lisp
Of course this doesn't work for multi-threaded environments, or for
@@ -815,7 +828,7 @@
relationships such as ``PartOf'', ``DesireOf'' and ``EffectOf''
between English phrases.
-Elephant's persistence capabilities is used to keep full records of
+Elephant's persistence capability is used to keep full records of
all source material, extracted relationships and search queries so
that it is always possible to trace the source of a learned relation
and to avoid repeated queries to web search engines. Conceptminer
@@ -828,13 +841,14 @@
@itemize
@item Bulk storage of post-processed web data: Elephant was used to
-store hundreds of thousands of processed web pages as strings and index
-the queries and resulting metadata.
-@item Derived index: a custom string hash function was used to populate
-a class derived index, allowing fast identification of pages from their URL.
+store hundreds of thousands of processed web pages as strings, associate
+pages with queries and store related metadata.
+@item Derived index: a custom string hash function over URLs was used to populate
+a class derived index, allowing fast identification of pages from
+their URL without requiring expensive eql comparisons.
@item Inverted document index: a (not terribly efficient) data structure
that efficiently maps words to documents allowing pages to indexed by
-the words contained in them. Allows for eash phrase and conjunction searches.
+the words contained in them. Allowed for phrase and conjunction searches.
@item User association data structure: a data structure based on oids that supports
general one-to-many mappings between classes. Had a custom migrate
method to support migration of associations. Supplanted by persistent
@@ -845,13 +859,13 @@
architecture to cover in-memory lisp operations. @code{PCOMP} (Process
Components) is a framework for constructing and managing simple,
dataflow-style multi-threaded applications in Common Lisp. The goal
-is to simplify the process sufficiently so that the ordinary user does
-not hurt themselves easily. To this end, the model provides for safe,
-asynchronous communications among a set of components which may be
-scheduled together in a single process or communicate across separate
-threads (and potentially processes). Components are packaged into a
-system inside a Container object which schedules execution and
-mediates communications.
+is to simplify the process sufficiently so that the ordinary user can
+hide from many of the details associated with aborting transactions.
+To this end, the model provides for safe, asynchronous communications
+among a set of components which may be scheduled together in a single
+process or communicate across separate threads (and potentially
+processes). Components are packaged into a system inside a Container
+object which schedules execution and mediates communications.
Communications between components can be in a dataflow style or using messages. Each
component has a single port for receiving incoming data items. These items, if access
--- /project/elephant/cvsroot/elephant/doc/tutorial.texinfo 2007/04/25 02:27:56 1.18
+++ /project/elephant/cvsroot/elephant/doc/tutorial.texinfo 2007/04/27 03:14:55 1.19
@@ -63,19 +63,22 @@
@item @strong{Store controller:} the interface between lisp and a data store.
Most operations require or accept a store controller, or a default
store controller stored in @code{*store-controller*} to function.
+@item @strong{Persistent Sets:} A simple persistent collection is provided
+which allows the creation of persistent sets.
@item @strong{BTrees:} Elephant provides a persistent key-value
abstraction based on the BTree data structure. Values can be written
to or read from a BTree and are stored in a sorted order.
-@item @strong{Values:} most lisp values, including standard objects, arrays, etc
+@item @strong{Stored values:} most lisp values, including standard objects, arrays, etc
can be used as either key or value in a persistent BTree.
@item @strong{Persistent objects:} An object where most slot values are stored in
the data store and are written to or retrieved from disk on slot
-accesses. Any value that can be written to an index can be written to
-a persistent slot.
-@item @strong{Transactions:} a dynamic context for executing operations on persistent
-objects or BTrees that ensures that a set of changes is made atomically.
-@item @strong{BTree indices:} A BTree index is a BTree that stores
-an alternative ordering of the elements in a reference BTree.
+accesses. Storing a persistent object stores only a reference,
+allowing for object identity.
+@item @strong{Object indexing:} The ability to lookup and sort objects by their slot
+values rather than by explicit inclusion in a collection.
+@item @strong{Transactions:} a dynamic context for executing operations on objects
+or collections such that the side effects exhibit the ACID (atomicity, consistency,
+isolation and durability) properties of database.
@end itemize
There are a set of more advanced concepts you will learn about later,
@@ -112,7 +115,8 @@
@lisp
(open-store '(:CLSQL (:SQLITE "/users/me/db/sqlite.db")))
-(open-store '(:CLSQL (:POSTGRESQL "localhost.localdomain" "mydb" "myuser" ""))))
+(open-store '(:CLSQL (:POSTGRESQL "localhost.localdomain"
+ "mydb" "myuser" ""))))
@end lisp
We use Berkeley DB as our example backend. To open a BDB
@@ -197,7 +201,7 @@
=> #<DB-BDB::BDB-BTREE @ #x10e86042>
@end lisp
-It is an instance of a class "btree"; @pxref{Using BTrees}.
+It is an instance of a class "btree"; @pxref{Persistent BTrees}.
@node Serialization
@comment node-name, next, previous, up
@@ -255,7 +259,7 @@
This will affect all aggregate types: objects, conses, hash-tables, et
cetera. (You can of course manually re-store the cons.) In this sense
elephant does not automatically provide persistent collections. If you
-want to persist every access, you have to use BTrees (@pxref{Using BTrees}).
+want to persist every access, you have to use BTrees (@pxref{Persistent BTrees}).
@item @strong{Serialization and deserialization can be costly}. While
serialization is pretty fast, but it is still expensive to store large
@@ -504,7 +508,8 @@
@lisp
(defpclass person ()
((name :accessor person-name :initarg :name))
- ((friends :accessor person-friends :initarg :friends :initform (make-pset))))
+ ((friends :accessor person-friends :initarg :friends
+ :initform (make-pset))))
(defmethod add-friend ((me person) (them person))
(insert-item them (person-friends me)))
@@ -522,7 +527,8 @@
@lisp
(defpclass person ()
((name :accessor person-name :initarg :name))
- ((friends :accessor person-friends-set :initarg :friends :initform (make-pset))))
+ ((friends :accessor person-friends-set :initarg :friends
+ :initform (make-pset))))
(defmethod person-friends ((me person))
(pset-list (person-friends-set me)))
@@ -609,7 +615,8 @@
@lisp
(map-btree (lambda (k v)
(format t "name: ~A utime: ~A~%" k
- (subseq (multiple-value-list (decode-universal-time v)) 3 6)))
+ (subseq (multiple-value-list
+ (decode-universal-time v)) 3 6)))
*friends-birthdays*)
"Andrew"
"Ben"
@@ -675,11 +682,15 @@
@lisp
(defun print-friend (friend)
- (format t " name: ~A birthdate: ~A~%" (name friend) (birthday friend)))
+ (format t " name: ~A birthdate: ~A~%"
+ (name friend) (birthday friend)))
-(make-instance 'friend :name "Carlos" :birthday (encode-date '(1 1 1972)))
-(make-instance 'friend :name "Adriana" :birthday (encode-date '(24 4 1980)))
-(make-instance 'friend :name "Zaid" :birthday (encode-date '(14 8 1976)))
+(make-instance 'friend :name "Carlos"
+ :birthday (encode-date '(1 1 1972)))
+(make-instance 'friend :name "Adriana"
+ :birthday (encode-date '(24 4 1980)))
+(make-instance 'friend :name "Zaid"
+ :birthday (encode-date '(14 8 1976)))
(get-instances-by-class 'friends)
=> (#<Carlos> #<Adriana> #<Zaid>)
@@ -782,7 +793,8 @@
name: Carlos birthdate: (1 1 1972)
=> NIL
-(map-class-index #'print-friend 'friend 'name :start "Adam" :end "Devin")
+(map-class-index #'print-friend 'friend 'name
+ :start "Adam" :end "Devin")
name: Adriana birthdate: (24 4 1980)
name: Carlos birthdate: (1 1 1972)
=> NIL
@@ -817,7 +829,7 @@
specification differs.
This same facility is also available for your own use. For more
-information @pxref{Secondary Indices}.
+information @pxref{BTree Indexing}.
@node Using Transactions
@@ -1195,12 +1207,12 @@
and iterating of duplicate or unique values.
@item @strong{Using the Map Operators}
Mapping operators can be very efficient if properly utilized.
-@item @strong{Using Multiple Stores}
- Multiple store controllers can be open simultaneously. However it
-does make the code more complex and you need to be careful about how
-you use them to avoid crashes and other unpleasant side effects.
-@item @strong{Custom Transaction Architecture}
- You can implement your own version of with-transaction using the
+@item @strong{Using Multiple Stores} Multiple store controllers can
+be open simultaneously. However it does make the code more complex
+and you need to be careful about how you use them to avoid crashes
+and other unpleasant side effects.
+@item @strong{Custom Transaction Architecture} You can implement your
+own version of @code{with-transaction} using the
underlying controller methods for starting, aborting and committing
transactions. You had better know what you are doing, however!
@item @strong{Handling Errors and Conditions}
--- /project/elephant/cvsroot/elephant/doc/user-guide.texinfo 2007/04/26 03:10:13 1.18
+++ /project/elephant/cvsroot/elephant/doc/user-guide.texinfo 2007/04/27 03:14:55 1.19
@@ -10,8 +10,8 @@
* Serialization details:: The devil hides in the details.
* Persistent Classes and Objects:: All the dirt on persistent objects.
* Class Indices:: In-depth discussion about indexing objects.
-* Persistent Sets:: Using the persistent set.
-* Persistent BTrees:: Using the native btree.
+* Persistent Sets:: Using the persistent set collection.
+* Persistent BTrees:: Using the native btree collection.
* BTree Cursors:: Low-level access to BTrees.
* BTree Indexing:: Alternative ways to reference objects in btrees.
* Index Cursors:: Low-level access to BTree indices.
@@ -172,9 +172,10 @@
@end lisp
This will affect all aggregate types: objects, conses, hash-tables, et
-cetera. (You can of course manually re-store the cons.) In this sense
-elephant does not automatically provide persistent collections. If you
-want to persist every access, you have to use BTrees (@pxref{Using BTrees}).
+cetera. (You can of course manually re-store the cons.) In this
+sense elephant does not automatically provide persistent collections.
+If you want to persist every access, you have to use Persistent Sets
+(@pxref{Persistent Sets}) or BTrees (@pxref{Persistent BTrees}).
@item @strong{Serialization and deserialization can be costly}. While
serialization is pretty fast, but it is still expensive to store large
@@ -382,8 +383,10 @@
@lisp
(defpclass my-pclass ()
((pslot1 :accessor pslot1 :initarg :pslot1 :initform 'one)
- (pslot2 :accessor pslot2 :initarg :pslot2 :initform 'two :persistent t)
- (tslot1 :accessor tslot1 :initarg :tslot1 :initform 'three :transient t)))
+ (pslot2 :accessor pslot2 :initarg :pslot2 :initform 'two
+ :persistent t)
+ (tslot1 :accessor tslot1 :initarg :tslot1 :initform 'three
+ :transient t)))
@end lisp
In the definition above the class @code{my-pclass} is an instance of
@@ -706,8 +709,9 @@
Because the instance is guaranteed to be resident, the operation has none of the
resident/non-resident conflicts above.
-Changing a persistent instance to a non-persistent class is not
-allowed and will result in an error.
+Change class cannot convert between persistent and non-persistent classes and will
+flag an error if you try to do so. @emph{(Note: this could be implemented in the
+future if users request it)}
@node Class Indices
@comment node-name, next, previous, up
@@ -860,7 +864,6 @@
database for reuse. The oid used by the btree, however, will not be
recovered.
-@c *** FINISH ***
@node BTree Cursors
@comment node-name, next, previous, up
@section BTree Cursors
@@ -869,27 +872,139 @@
database, you can also traverse the BTree structure one key-value pair
at a time.
-Creating cursors (inside transactions)
-Duplicating cursors
+Cursors must be created in the context of an active transaction
+(i.e. a @code{with/ensure-transaction} body). A cursor is made
+through a call to the @code{make-cursor} method of the BTree you wish
+to traverse.
+
+An existing cursors can also be duplicated within the same transaction
+by calling @code{cursor-duplicate} which avoids the overhead of
+setting a second cursor to the same location.
-Initializing cursors to location
-- first, last, set
-Traversing
-- next, prev, (set)
-Side effects
-- delete
-- put
-- Can also use setf get-value while traversing
+Cursors can be in two states: initialized and uninitialized.
+@ref{Cursor API} for details.
-Large cursor operations (locks, resources?)
+To initialize a cursor, you have to use one of the initializing
+functions to select a key-value pair in the btree.
+
+@itemize
+@item @code{cursor-first} and @code{cursor-last}: initialize the
+cursor to the first and last element of the btree, respectively.
+@item @code{cursor-set} and @code{cursor-set-range}: Sets the cursor
+to the first key-pair values according to the specified key. If the
+set fails, the cursor will remain uninitialized. The ranged set will
+set it to the first key-value pair where the key is equal to or
+greater than the key argument.
+@end itemize
+
+A valid cursor will return multiple values: @code{(exists? key
+value)}. The first argument tells whether or not the cursor is
+initialized and pointing at a proper value. The second two arguments
+are self-explanatory.
+
+@code{cursor-current} returns the current state of the cursor, nil if
+it is uninitialized.
+
+Once a cursor is properly initialized, it can be incremented or
+decremented, a simple constant-time operation on BTrees.
+
+@code{cursor-next} and @{cursor-prev} move the cursor a single step
+forward or back across the sorted key-value pairs. @code{cursor-next}
+moves in ascending order, @code{cursor-prev} in descending order.
+
+Finally cursors can be used for side effects on the current key-value
+pair. The function @code{cursor-put} replaces the value (but does not
+increment the current value) and @code{cursor-delete} deletes the
+key-value pair and become uninitialized. It is a valid operation to
+use the @code{(setf get-value)} method while the cursor is active to
+change the value at the current cursor.
+
+If cursors take place within a transaction, what happens when
+traversing a very large BTree? This depends on the data store policy
+regarding whether a cursor read locks its entire btree (or the subset
+that is being iterated over) or allows changes to any pairs its
+transaction has not changed. See your data store documenation for
+details.
-@c *** FINISH ***
@node BTree Indexing
@comment node-name, next, previous, up
@section BTree Indexing
+One powerful feature of Elephant is the ability to add indexes to
+BTrees. An indexed btree is a subclass of the standard @code{btree}
+called @code{indexed-btree}. The indexed btree maintain a set of
+indices (instances of @code{btree-index}) which provide alternative
+ways of indexing into the values of the main btree.
+
+Each index is itself a btree, but with the property that its values
+are matched to the keys of the main btree. That is if you have a btree
+with key-value pairs:
-@c *** FINISH ***
+@lisp
+("henry" . #<name: Henry, age: 45>)
+("larry" . #<name: Larry, age: 29>)
+@end lisp
+
+You can define an index that is populated by the age of the person object:
+
+@lisp
+(29 . "Larry")
+(45 . "Henry")
+@end lisp
+
+Now when you call @code{(get-value 29 index)} you get back
+@code{#<name: Larry, age: 29>}! Note also that these new pairs are
+ordered by age, the opposite of the alphabetic ordering of the names
+in the first two pairs. If you read through the tutorial, you may
+have guessed by now that this is the mechanism used to implement the
+class indexing capabilities previously described.
+
+An index is created by using the @code{add-index} function. This
+function takes the @code{indexed-btree} you wish to index, an
+index-name for later retrieval, a key-form which dictates how
+the index populates it's keys as a function of the main btree's
+keys and values.
+
+A simple, contrived example is shown in the figure below:
+
+@center @image{IndexedBtrees1,,4.0in,[BTree Index Diagram],.png}
+
+Here we have a primary, indexed btree with a set of keys and values
+represented by symbols. We'll declare the function @code{val} to take
+a value symbol and extract it's number. The key-form in the
+@code{mod5 * 2} index is:
+
+@lisp
+(lambda (k v)
+ (if (= 0 (mod (val v) 5))
+ (values t (* 2 (val v)))
+ (values nil nil)))
+@end lisp
+
+When a key-value pair is written to the primary btree, the index is
+automatically updated through a call to the key-form. If the key-form
+above is called with @code{key1} and @code{value1}, @code{val} will
+return 1 which fails the if test. The second values statement,
+@code{(values nil nil)} indicates that this pair is not to be indexed.
+If I pass @code{key5} and @code{value5} to this same key form, I get
+back 10 as the @code{(val 'value5)} is 5 and @code{(= 0 (mod 5 5))} so
+the form returns @code{(values t 10)} meaning the index should add an
+index entry of 10 (@code{(* 2 5)}) associated with the key value
+@code{key5}.
+
+So, of course, making the call @code{(get-value 10 index-mod5)} will
+return @code{value5}.
+
+The second index in our little example calculates the number of bits
+in all odd numbered values. This illustrates an important property of
+the @code{btree-index}: it allows duplicate keys. Standard
+@code{btree} and @code{indexed-btree} classes are not allowed to have
+duplicate elements. The odd index allows us to ask simple questions
+like: ``what are all the odd values with ids that fit into 4 bits?''.
+
+To extract this set, we have to use cursor functions specifically
+designed for the index that iterate over duplicate values.
+
@node Index Cursors
@comment node-name, next, previous, up
@section Index Cursors
@@ -897,19 +1012,29 @@
Index cursors are just like BTree cursors except you can get the main
BTree value instead of the index value. There are also a parallel set
of operations such as @code{cursor-pnext} instead of
-@code{cursor-next} which returns @code{exists}, @code{key}, @code{primary-btree-value}
-and @code{index-value = primary-btree-key}.
-
-Operations that have the same behavior, but return primary btree values and keys are:
+@code{cursor-next} which returns @code{exists}, @code{key},
+@code{primary-btree-value} and @code{index-value = primary-btree-key}.
-@c need table here
+Operations that have the same behavior, but return primary btree
+values and keys are:
-@itemize
-@item cursor-first -> cursor-pfirst, cursor-last -> cursor-plast
-@item cursor-current -> cursor-pcurrent
-@item cursor-next -> cursor-pnext, cursor-prev -> cursor-pprev
-@item cursor-set-range
-@end itemize
+@table @samp
+@item @code{cursor-first}
+@code{cursor-pfirst}
+@samp{@code{cursor-first}}
+@item @code{cursor-last }
+@code{cursor-plast}
+@item @code{cursor-current }
+@code{cursor-pcurrent}
+@item @code{cursor-next }
+@code{cursor-pnext}
+@item @code{cursor-prev}
+@code{cursor-pprev}
+@item @code{cursor-set}
+@code{cursor-pset}
+@item @code{cursor-set-range}
+@code{cursor-set-prange}
+@end table
The big difference between btree cursors and index cursors is that
indices can have duplicate key values. This means we have to choose
@@ -1256,6 +1381,10 @@
@item @strong{@code{:txn-sync}} This is the default behavior and specifies that the transaction log
of the current transaction is flushed to disk before the transaction commit routine returns. This
provides full ACID compliance.
+@item @strong{@code{:transaction}} This argument is for advanced use. It tells
+ the Berkeley DB transaction subsystem the transaction it should use rather
+than to create a new one. The @code{:parent} argument provides a parent transaction
+that can result in a true nested transaction.
@end itemize
@subsection Special Commands
@@ -1357,7 +1486,9 @@
@comment node-name, next, previous, up
@section Native Lisp Data Store
-The native lisp data store is vaporware at this time.
+The native lisp data store is unimplemented. It is tentatively
+planned for a 1.1 release sometime in the distant future. Yes,
+this is a deliberatively vague declaration.
@c @node Querying persistent instances
@c @comment node-name, next, previous, up
