This tutorial explains, through the use of detailed examples, how to write application programs in C++ that store and manipulate complex data structures in Shore.
This tutorial illustrates many aspects of Shore, including
This tutorial does not try to do everything. In particular:
The example program stree uses an unbalanced binary search tree as an inverted index to a set of documents. The tree contains one node for each distinct word appearing in any of the documents. Associated with each word is a set of citations, each of which indicates a document and the offset within the document of the start of a line containing the word. Each tree node, citation, and document is a separate object stored in the Shore database. Although the documents are actually stored in the Shore database, they are stored in such a way that existing Unix programs can manipulate them as if they were ordinary files.
The program has options to add and remove documents from the database and to list the lines containing a given word. It also has a debugging option that dumps all the objects in the database. This option illustrates how to write a maintenance program that iterates through the objects in the database in a "raw" form.
The tutorial then shows how to modify the example to use the index facility of Shore to accomplish the same task in a different way.
The example programs illustrate how to define objects with methods ("member functions" in C++) linked together with pointers (called "references" in Shore). They show how to use relationships, which generalize pointers, adding the ability to represent "1-to-N" and "M-to-N" associations and automatically maintain inverse "pointers". They also illustrate the Unix-compatibility features of Shore.
First and foremost, the binary search tree program does not illustrate the best-or even a good-way to build inverted indices. The second example, which uses Shore's built-in index feature, is closer to the way a real application would accomplish this task. A binary search tree is not a very good data structure for disk-based data structures, since fetching each node requires a disk access. In fact, even this program was designed to run in main memory, a hash table would be better! The example was chosen to illustrate how a program that manipulates linked data structures can easily be adapted to make those structures persistent, but converting a main-memory program to run efficiently with persistent data generally requires a careful re-design of data structures and algorithms.
The examples do not illustrate all the features of Shore or the SDL data-definition language. They do not use all the available pre-defined data structures (such sequences or bags), the "module" facility for managing large complex designs, or inheritance (SDL supports multiple inheritance). See The SDL Reference Manual) for more details.
This tutorial walks through the sources of the search-tree program in detail. These sources, as well as associated test programs and data, may be found in the src/examples/stree sub-directory of the distribution. They are also included in the Appendix. The next few sections walk through this example in detail. It will be useful to keep a copy of the program sources close to hand. Throughout this tutorial, we will assume (as does the Shore Software Installation Manual), that the environment variable $SHROOT contains the absolute path name of the root directory of the installed Shore software.