ToC path:

Database Class Relationships in C#

As explained in the Class Relationships page, eXtremeDB provides a number of ways to implement relationships (joins) between tables, each having distinct advantages and costs in terms of memory overhead and performance. The different techniques available to C# developers are presented in the following sections.

Index join

A simple one-to-many relationship between two tables, Department and Employee, could be implemented in SQL as follows:
 
    select e.name, d.name from Employee e 
    inner join Department d d.dept_no = d.dept_no;
     
To implement a one-to-many relationship like the Department > Employee example, we might define the two database classes as follows:
 
     
    [Persistent]
    class Department
    {
        [Indexable(Type = Database.IndexType.BTree, Unique = true)]
        public String code;
        public String name;
        [Indexable(Type = Database.IndexType.Hashtable, Unique = true)]
        public int dept_no;
    }
 
    [Index("byDept_EmployeeName", Keys = new string[] { "dept_no", "name" }, Unique = true)]
    [Persistent]
    class Employee
    {
        [Indexable(Type = Database.IndexType.BTree, Unique = false)]
        public String  name;
        public int  dept_no;
    }
     
Here the unique hash index dept_no acts as the “primary key” on the Department class, and the unique B-Tree index byDept_EmployeeName acts as the “foreign key” in the Employee class. Note that byDept_EmployeeName is a compound index consisting of two field values in the Employee class: dept_no and name. It is not necessary that a “foreign key” be compound. A simple B-Tree index on field dept_no would be sufficient to form the join, but with the compound index we have the additional advantage that we are able to order all instances with the same dept_no value in alphabetical order by the name field.

To demonstrate how the join is implemented, consider the following code snippets (taken from the SDK sample “csharp/Joins/Index_Join”) that manage Department and Employee objects. First we populate the Department class with some sample data:
 
    // Create and insert Department objects
    con.StartTransaction(Database.TransactionType.ReadWrite);
    for (short i = 0; i < N_DEPARTMENTS; i++)
    {
        Department dept = new Department();
        dept.code = DD[i].code;
        dept.name = DD[i].name;
        dept.dept_no = DD[i].dept_no;
        con.Insert(dept); // Insert object to eXtremeDB database
        Console.WriteLine("\t" + i + ") " + dept.code + ", " + dept.name +
            ", dept_no=" + dept.dept_no);
    }
    con.CommitTransaction();
     
Then we insert Employee objects associating them with the appropriate Department object:
 
    con.StartTransaction(Database.TransactionType.ReadWrite);
    // Find Department by code; extract dept_no; create Employee and assign name, dept_no
    Cursor<Department> cursor = new Cursor<Department>(con, "code");
    for (short i = 0; i < N_EMPLOYEES; i++)
    {
        Department dept = cursor.Find(ED[i].deptCode);
        Employee emp = new Employee();
        emp.dept_no = dept.dept_no;
        emp.name = ED[i].name;
        con.Insert(emp);
        Console.WriteLine("\t" + i + ") " + emp.name + ", dept_no=" + emp.dept_no);
    }
    con.CommitTransaction();
    cursor.Close();
     
Note that we instantiate a Cursor on index Department.code and call the Cursor.find() method to position to the Department object with the specified deptCode; then the Department’s dept_no is extracted to be stored in the new Employee object. This creates the association (relationship) between the Department object with the Employee object upon which the join is implemented during a subsequent query.

Now to navigate the relationship between (i.e. “join”) these two classes we might use code like the following to display all of a given employee’s coworkers in their department:
 
    // Search for all Employee objects from a specified Employee's Department
    String search_name = "William";
    Console.Write("\n\n" + search_name + "'s co-workers in ");
    con.StartTransaction(Database.TransactionType.ReadOnly);
    // 1. Find the Employee object by name
    Cursor<Employee> cursor1 = new Cursor<Employee>(con, "name");
    Employee emp1 = cursor1.Find(search_name);
     
    // 2. Find the Department object by its dept_no and display the Department name
    Cursor<Department> cursor2 = new Cursor<Department>(con, "dept_no");
    Department d = cursor2.Find(emp1.dept_no);
    Console.Write(d.name + " are:\n");
 
    // 3. Position the cursor in the byDept_EmployeeName compound index to the
    // first object with this dept_no
    con.StartTransaction(Database.TransactionType.ReadWrite);
    Cursor<Employee> cursor3 = new Cursor<Employee>(con, "byDept_EmployeeName");
    {
        if (cursor3.Search(Operation.GreaterOrEquals, emp1.dept_no, ""))
        {
            foreach (Employee e in cursor3)
            {
                if(0 != e.dept_no.CompareTo(emp1.dept_no))  // Exit loop when Dept_no is
                                        // no longer equal
                {
                    break;
                }
                else if ( !String.Equals(e.name,search_name) )  // exclude serch_name
                                            // from results
                {
                    Console.WriteLine("\t" + e.name);
                }
            }
            cursor2.MoveNext();
        }
    }
    con.CommitTransaction();
     
Note that we use a Cursor on index Employee.name to find the Employee object with the specified name; then a Cursor on index Department.dept_no to find the Department using the found Employee’s dept_no. Then we use a third Cursor on the compound index Employee.byDept_EmployeeName to position to the first object with this dept_no and scroll through the cursor until the dept_no is different. For each index node we get the Employee object from the cursor and check its name field. If this is not the name of the original employee we are searching coworkers for, we display the name and call the Cursor.MoveNext() method to go to the next node in the index tree.

Pros and Cons:

This is a typical “relational” style join familiar to many developers. While it is intuitive and straightforward to implement, it incurs significant overhead to manage several indexes. When an insert transaction is committed, a hash index and two B-Tree index nodes are created for each Department object, and two B-Tree index nodes are created for each Employee object. This results in memory consumption in addition to the space occupied by the database objects themselves and the B-Tree index structures require “balancing” which can incur significant processor cycles. Hence, the overall performance for inserting objects is not optimal.

Lookup of Department objects by dept_no is efficient due to the hash index Idept_no. And the cursor created on the Employee objects through compound index Employee.byDept_EmployeeName facilitates “scrolling” through the index tree to list employees in alphabetical order by name.

Autoid reference

An alternative technique to the index-join example above is to implement the “foreign key” relationship with a direct reference from the Employee object to its Department. An autoid field can serve this purpose. For example, we might define the two database classes as follows:
 
    [Persistent(AutoID = true)]
    class Department
    {
        [Indexable(Type=Database.IndexType.BTree, Unique=true)] // Declare unique tree index by "code" field
        public String code;
        public String name;
    }
 
    [Persistent]
    [Index("byDept_EmployeeName", Keys=new string[]{"dept","name"}, Unique=true)]
    class Employee
    {
        [Indexable(Type = Database.IndexType.BTree, Unique = true)] // Declare unique tree index by "name" field
        public String name;
        [References(typeof(Department))]
        public long dept;
    }
     
Note that the Department class no longer has the dept_no field and thus no index on field dept_no. Instead it has the annotation (autoid=true). This actually causes a “hidden” hash index to be maintained for the Department object autoid values that are automatically incremented as new objects are created. And note the field dept is of type long - it will store the autoid of the associated Department object.

To demonstrate how this join is implemented, consider the following code snippets (taken from the SDK sample “csharp/joins/Autoid_Ref”). We populate the Department class as in the Index_Join sample above, but note that to display the autoid for each Department object we retrieve it from the Connection.insert() method:
 
    // Create and insert Department objects
    con.StartTransaction(Database.TransactionType.ReadWrite);
    Console.WriteLine("\nCreate Departments:\n");
    for (short i = 0; i < N_DEPARTMENTS; i++)
    {
        Department dept = new Department();
        dept.code = DD[i].code;
        dept.name = DD[i].name;
        long autoid = con.Insert(dept);
        Console.WriteLine("\t" + i + ") " + dept.code + ", " + dept.name +", Autoid=" + autoid);
    }
    con.CommitTransaction();
     
When inserting Employee objects we extract the autoid from the corresponding Department object using the Cursor.GetAutoId() method and assign it to the reference field Employee.dept:
 
    // Create and insert Employee objects
    Console.WriteLine("\nCreate Employees and join each to a Department:\n");
    con.StartTransaction(Database.TransactionType.ReadWrite);
    Cursor<Department> cursor = new Cursor<Department>(con, "code");
    for (short i = 0; i < N_EMPLOYEES; i++)
    {
        // Find the Department object for this Employee by the BTree index on
        // Department.code
        cursor.Find(ED[i].deptCode);
        Employee emp = new Employee();
        emp.name = ED[i].name;
        // Assign the Department autoid for this Department object and insert new
        // Employee object
        emp.dept = cursor.GetAutoId();  // Note that the method GetAutoId is of the
        // Cursor class
        con.Insert(emp);
        Console.WriteLine("\t" + i + ") " + emp.name + ", Department.Autoid=" + emp.dept);
    }
    con.CommitTransaction();
    cursor.Close();
     
The code to display all of a given employee’s coworkers in their department would be nearly identical to that in the Index_Join sample above with the exception that we instantiate the Cursor on the class Department without specifying an index field. Then we call find with the Employee.dept value to lookup the Department object by its autoid. This is equivalent to the call of Cursor.find() on index Department.dept_no which uses the hash index dept_no, the difference is that the autoid is automatically generated whereas a unique value must be specified for the dept_no field. The same technique of scrolling through a cursor on compound index byDept_EmployeeName is used to display the employee names in alphabetical order:
 
 
    // Search for all Employee objects from a specified Employee's Department
    String search_name = "William";
    Console.Write("\n\n" + search_name + "'s co-workers in ");
    con.StartTransaction(Database.TransactionType.ReadOnly);
    // 1. Find the Employee object by name
    Cursor<Employee> cursor1 = new Cursor<Employee>(con, "name");
    Employee emp1 = cursor1.Find(search_name);
 
    // 2. Find the Department object by its autoid and display the Department name
    Cursor<Department> cursor2 = new Cursor<Department>(con);
    Department d = cursor2.Find(emp1.dept);
    Console.Write(d.name + " are:\n");
 
    // 3. Position the cursor in the byDept_EmployeeName compound index to the
    // first object with this Department Autoid
    Cursor<Employee> cursor3 = new Cursor<Employee>(con, "byDept_EmployeeName");
    {
        if (cursor3.Search(Operation.GreaterOrEquals, emp1.dept, ""))
        {
            foreach (Employee e in cursor3)
            {
                if (0 != e.dept.CompareTo(emp1.dept))  // Exit loop when Department
                                        // autoid is no longer equal
                {
                    break;
                }
                else if (!String.Equals(e.name, search_name))  // exclude serch_name from results
                {
                    Console.WriteLine("\t" + e.name);
                }
            }
            cursor3.MoveNext();
        }
    }
    con.CommitTransaction();
     
Pros and Cons:

This implementation uses somewhat less memory by eliminating the field dept_no and the lookup of Department objects is likewise efficient due to the hash index generated for the autoid. But some optimization might be gained by relaxing the application requirements.

Note that the major drawback for performance and memory consumption, both for this and the index_join relational approach, is incurred by the B-Tree indexes: Employee.byDept_EmployeeName, Employee.name and Department.name. For example, if it is not necessary to lookup a Department object by its name, the Department.Name index could be eliminated. And further, if it is not necessary to display the employees of a given department in alphabetical order, then we can eliminate the compound index Employee.byDept_EmployeeName. The following example illustrates this approach.

Vector of autoids

Instead of storing the autoid of the Employee object’s Department in the Employee object, we could instead store an array or vector of Employee autoids in the Department object. For example (see the SDK sample “csharp/joins/Autoid_Vector”), we might define the database classes as follows:
 
    [Persistent(AutoID = true)]
    class Department
    {
        [Indexable(Type=Database.IndexType.BTree, Unique=true)] // Declare unique tree index by "code" field
        public String code;
        public String name;
        [References(typeof(Employee))]
        public long[] employees;
    }
 
    [Persistent(AutoID = true)]
    class Employee
    {
        [Indexable(Type = Database.IndexType.BTree, Unique = true)] // Declare unique tree index by "name" field
        public String name;
        [References(typeof(Department))]
        public long dept;
    }
     
Note that both classes are defined with [Persistent(autoid = true)]. The Employee autoid will be stored in the Department class vector of references employees. We will use the Department autoid in the Employee reference field dept, as in the Autoid_Ref example above, to efficiently access the Department object from the Employee.

The code to populate the database becomes a little more complicated as we need to allocate space for the dynamic vector of autoid values in the Department objects and assign these autoids when we insert the Employee objects. So for each Employee object we execute the following code to allocate space and insert an Employee autoid into the Department employees vector:
 
    // Create and insert Department objects
    con.StartTransaction(Database.TransactionType.ReadWrite);
    Console.WriteLine("\nCreate Departments:\n");
    for (short i = 0; i < N_DEPARTMENTS; i++)
    {
        Department dept = new Department();
        dept.code = DD[i].code;
        dept.name = DD[i].name;
        // Allocate space for Employee autoids and initialize to 0
        dept.employees = new long[VECTOR_SIZE];
        for (short j = 0; j < VECTOR_SIZE; j++) dept.employees[j] = 0;
        long autoid = con.Insert(dept);
        Console.WriteLine("\t" + i + ") " + dept.code + ", " + dept.name +
                    ", Autoid=" + autoid);
    }
    con.CommitTransaction();
 
    // Create and insert Employee objects
    Console.WriteLine("\nCreate Employees and join each to a Department:\n");
    for (short i = 0; i < N_EMPLOYEES; i++)
    {
        // Find the Department object for this Employee by the BTree index on
        // Department.code
        con.StartTransaction(Database.TransactionType.ReadWrite);
        Cursor<Department> cursor = new Cursor<Department>(con, "code");
        Department d = cursor.Find(ED[i].deptCode);
        if (null != d)
        {
            // Find the first vacant Employee vector element
            for (short j = 0; j < VECTOR_SIZE; j++)
            {
                if (0 == d.employees[j])
                {
             
                    // Create Employee object and store its autoid in vector
                    // Department.employees
                    Employee emp = new Employee();
                    emp.name = ED[i].name;
                    // Assign the Department autoid for this Department object and insert
                    // new Employee object
                    emp.dept = cursor.GetAutoId();    // Note that the method GetAutoId()
                    // is of the Cursor class
                    d.employees[j] = con.Insert(emp); // Note that Insert() returns the
                                        // Employee autoid
                    con.CurrentCursor.Update();       // Assure that the inserted autoid
                            // is made perminent
                    Console.WriteLine("\t" + i + ") " + emp.name + ", Department.Autoid="
                        + emp.dept);
                    break;
                }
            }
        }
        else
        {
            Console.WriteLine("\tDepartment.code (" + ED[i].deptCode +
                ") not found!");
        }
        con.CommitTransaction();
        cursor.Close();
    }
     
Now the code to display all of a given employee’s coworkers in their department will simply find the Department object as in the Autoid_Ref sample above by instantiating the Cursor on class Department without specifying an index field. Then we call find with the Employee.dept value to lookup the Department object by its autoid. Then we simply list this department’s employees from the vector as follows:
 
    // Search for all Employee objects from a specified Employee's Department
    String search_name = "William";
    Console.Write("\n\n" + search_name + "'s co-workers in ");
    con.StartTransaction(Database.TransactionType.ReadOnly);
    // 1. Find the Employee object by name
    Cursor<Employee> cursor1 = new Cursor<Employee>(con, "name");
    Employee emp1 = cursor1.Find(search_name);
    if ( null != emp1 )
    {
        // 2. Find the Department object by its autoid and display its name
        Cursor<Department> cursor2 = new Cursor<Department>(con);
        Department dept1 = cursor2.Find(emp1.dept);
        Console.Write(dept1.name + " are:\n");
 
        // 3. Scroll through the vector of Employee autoids, find the Employee
        // object and display its name
        Cursor<Employee> cursor3 = new Cursor<Employee>(con);
        for (short j = 0; j < VECTOR_SIZE && 0 != dept1.employees[j]; j++)
        {
            // Skip if this is the autoid of the "search_name" object
            if (cursor1.GetAutoId() != dept1.employees[j])
            {
                Employee emp = cursor3.Find(dept1.employees[j]);
                Console.WriteLine("\t" + emp.name);
            }
        }
    }
     
Pros and Cons:

This implementation uses significantly less memory and reduces behind-the-scenes tree structure maintenance by eliminating two B-Tree indexes with the small sacrifice of not ordering the list of Employees in alphabetical order. However, it could be a simple matter to introduce a sorting algorithm into the application to address this; but it should be noted that this approach could become untenable if the number of Employees per Department is very large.