Re: Indexing techniques for hierarchies

From: James <jraustin1_at_hotmail.com>
Date: 4 Jan 2002 10:11:35 -0800
Message-ID: <a6e74506.0201041011.6a9ea868_at_posting.google.com>

> > > You have not convinced me that what you did cannot be represented as
> > > an adjacency list.
> >
> > The following creates 1000 classes, each with properties of various
> > data types. The properties of each class have are different name.
> > An instance is made of each class.
> > Each instance is the child of the previous.
> > The time to traverse 1000 instances starting from the last child and
> > copy the properties to local variables was approximately 4 ms (4176ms
> > / 1000 Loops).
> > See www.xdb1.com/Benchmark/8.asp for details.
>
> You ignore the names of the classes and fields;
> i.e. there is no special logic that discriminates between classes
> or fields on the basis of name

I submit the above three sentences are incorrect. The proof is in the code that was provided. The code that discriminates the different classes and fields is the index "[x]" which changes from 0 to 999. Below I reshow just the classes and boolean properties to make the point clear.

The top loop creates 1000 different classes (Test0, Test1,... Test999) and a ptr to each one is stored in pTest[x] array. The top loop also creates 1000 different classes named (PBool0, PBool1, ... PBool999) the ptr to each one stored in pPBool[x]. I won't go into details here but basically a class' alias is used to attach it as a property of another class (www.xdb1.com/Basics/Property.asp)

// Top loop
// Loop that create the 1000 different classes and 1000 different fields
for(x=0; x < MAX; ++x){
  // Create Test Cls
    _stprintf(fName_s, _T("Test%d"), x);

    pTest[x] = pO_m->InstPkg_add_(pRoot_g,        // Cls
                                  pFldrMyData_g,  // Parent
                                  fName_s);       // Inst name

  // Create cls for property pPBool
    _stprintf(fName_s, _T("PBool%d"), x);

    pPBool[x] = pO_m->InstPkg_add_(pRoot_g,        // Cls
                                   pFldrMyData_g,  // Parent
                                   fName_s);       // Inst name

    pPBoolAlias[x] = pO_m->AliasDef_get_(pPBool[x]);

  // Attach as properties of Test Cls and set default values    pO_m->Prop_childFirst_set_(pTest[x], pPBoolAlias[x], _T("True")); }

The above code creates the equivalent of the following in rdbs: T_Test0
 PBool0

T_Test1
 PBool1

.
.
.

T_Test999
 PBool999

In addition to accessing any object (class, instance, property) by its text string name, in XDb they can also be accessed by the object's ptr which is returned when the object was created (or the ptr can be retrieved later based on its name). In the bottom loop shown below, the code accesses the 1000 different PBool properties via the ptrs (pPBoolAlias[x]) rather than by their text names (PBool0, PBool1,...). As you can see the x is initialized to 999 before the loop and changes in every loop since it is decremened near the bottom (--x).

// Bottom Loop
// Loop that access the instances of different classes and different fields.
pX = pNew;
x = MAX - 1;
while (pX->cls() != pTest[0]){
 // Bool
   pPBoolX = pO_m->Prop_get_(pX, pPBoolAlias[x]);    bol = pO_m->DataBool_get_(pPBoolX->childFirst()->cls());

 // Move to parent
   pX = pX->parent();
   --x;
}

To traverse the single instance of the 1000 different classes with different properties there is no need to use pTest[x] since we traverse by moving to the parent of each instance (pX->parent()) start with the last (pNew). We check the class of each instance at the top of the loop and stop when when have reached the first instance whose class would is pTest[0].

The downloadable database at www.xdb1.com/Benchmark/8.asp makes the above points visually clear. (It contains 10 rather than 1000 to reduce download size).

If you are still unconvinced that the above is not simply an "adjacency list" I can provide a new benchmark.

> That type of benchmark, though, would have very little
> relationship to any real-world application I can think of.

I submit to you the following example: www.xdb1.com/Example/Ex046.asp Received on Fri Jan 04 2002 - 19:11:35 CET