# Database Class Relationships in Java

> 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 Java 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) // Declare unique tree
>             // index by "code"
>             String code;
>             String name;

>             @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique Tree
>             // index by "dept_no"
>             int dept_no;
>         }

>         @Persistent()
>         @Index(name="byDept_EmployeeName", keys={@Key("dept_no"), @Key("name")}, unique=true)
>         class Employee
>         {
>             @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree
>             // index by "name"
>             String name;
>             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 “java/joins/Index_Join”) that manage Department and Employee objects. First we populate the Department class with some sample data:

>         // Create and insert Department objects
>         System.out.println("\nCreate Departments:\n");
>         con.startTransaction(Database.TransactionType.ReadWrite);
>         for (short i = 0; i < N_DEPARTMENTS; i++)
>         {
>             Department dept = new Department();
>             dept.name = DD[i].name;
>             dept.code = DD[i].code;
>             dept.dept_no = DD[i].dept_no;
>             con.insert(dept);
>             System.out.println("Code " + dept.code + ", Name " + 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, Department.class, "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);
>             System.out.println("\tEmployee: " + emp.name + "Dept_no: " + emp.dept_no);
>         }
>         con.commitTransaction();

> 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";
>         con.startTransaction(Database.TransactionType.ReadOnly);
>         // 1. Find the Employee object by name and extract dept_no
>         Cursor<Employee> cursor1 = new Cursor<Employee>(con, Employee.class, "name");
>         Employee emp1;
>         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, Department.class, "dept_no");
>         Department d = cursor2.find(emp1.dept_no);
>         System.out.println("\n\nFind " + search_name + "'s co-workers in " + d.name + " :\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, Employee.class,"byDept_EmployeeName");
>         {
>             if (cursor3.search(Cursor.Operation.GreaterOrEquals, emp1.dept_no, ""))
>             {
>                 for (Employee e : cursor3)
>                 {
>                     if(e.dept_no != emp1.dept_no)  // Exit loop when Dept_no is no longer equal
>                     {
>                         break;
>                     }
>                     else if ( !(e.name.equals(search_name)) )  // exclude search_name from results
>                     {
>                         System.out.println("\t" + e.name);
>                     }
>                 }
>                 cursor3.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"
>             String code;
>             String name;
>         }

>         @Persistent()
>         @Index(name="byDept_EmployeeName", keys={@Key("dept"), @Key("name")}, unique=true)
>         class Employee
>         {
>             @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree
>             // index by "name"
>             String name;
>             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 “java/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
>         System.out.println("\nCreate Departments:\n");
>         con.startTransaction(Database.TransactionType.ReadWrite);
>         for (short i = 0; i < N_DEPARTMENTS; i++)
>         {
>             Department dept = new Department();
>             dept.name = DD[i].name;
>             dept.code = DD[i].code;
>             long autoid = con.insert(dept);
>             System.out.println("\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
>         System.out.println("\nCreate employees and join each to a department:\n");
>         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, Department.class, "code");
>         for (short i = 0; i < N_EMPLOYEES; i++)
>         {
>             Department dept = 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);
>             System.out.println("\t" + i + ") " + emp.name + ", Department.Autoid= " + emp.dept);
>         }
>         con.commitTransaction();

> 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";
>         con.startTransaction(Database.TransactionType.ReadOnly);
>         // 1. Find the Employee object by name and extract dept_no
>         Cursor<Employee> cursor1 = new Cursor<Employee>(con, Employee.class, "name");
>         Employee emp1;
>         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.class);
>         Department d = cursor2.find(emp1.dept);
>         System.out.println("\n\nFind " + search_name + "'s co-workers in " + d.name + " :\n");

>         // 3. Position the cursor in the byDept_EmployeeName compound index to the first
>         // object with this Department Autoid
>         con.startTransaction(Database.TransactionType.ReadWrite);
>         Cursor<Employee> cursor3 = new Cursor<Employee>(con, Employee.class, "byDept_EmployeeName");
>         {
>             if (cursor3.search(Cursor.Operation.GreaterOrEquals, emp1.dept, ""))
>             {
>                 for (Employee e : cursor3)
>                 {
>                     if(e.dept != emp1.dept)  // Exit loop when Dept_no is no longer equal
>                     {
>                         break;
>                     }
>                     else if ( !(e.name.equals(search_name)) )  // exclude serch_name from results
>                     {
>                         System.out.println("\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 “java/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"
>             String code;
>             String name;

>             long[] employees;
>         }

>         @Persistent(autoid = true)
>         //@Index(name="byDept_EmployeeName", keys={@Key("dept_no"), @Key("name")}, unique=true)
>         class Employee
>         {
>             @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree
>             // index by "name"
>             String name;
>             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
>         System.out.println("\nCreate Departments:\n");
>         con.startTransaction(Database.TransactionType.ReadWrite);
>         for (short i = 0; i < N_DEPARTMENTS; i++)
>         {
>             Department dept = new Department();
>             dept.name = DD[i].name;
>             dept.code = DD[i].code;
>             // 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);
>             System.out.println("\t" + i + ") " + dept.code + ", " + dept.name +", Autoid=" + autoid);
>         }
>         con.commitTransaction();

>         // Create and insert Employee objects
>         System.out.println("\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, Department.class,"code");
>             Department dept = cursor.find(ED[i].deptCode);
>             if (null != dept)
>             {
>                 // Find the first vacant Employee vector element
>                 for (short j = 0; j < VECTOR_SIZE; j++)
>                 {
>                     if (0 == dept.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();
>                         dept.employees[j] = con.insert(emp);
>                         cursor.update();        // Assure that the inserted autoid is made permanent
>                         System.out.println("\t" + i + ") " + emp.name +
>                             ", Department.Autoid=" + emp.dept);
>                         break;
>                     }
>                 }
>             }
>             else
>             {
>                 System.out.println("\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";
>         con.startTransaction(Database.TransactionType.ReadOnly);
>         // 1. Find the Employee object by name and extract its autoid
>         Cursor<Employee> cursor1 = new Cursor<Employee>(con, Employee.class, "name");
>         Employee emp1 = cursor1.find(search_name);
>         if ( null != emp1 )
>         {
>             // 2. Find the Department object by its autoid and display the name
>             Cursor<Department> cursor2 = new Cursor<Department>(con, Department.class);
>             Department dept1 = cursor2.find(emp1.dept);
>             System.out.println("\n\n" + search_name + "'s co-workers in " + 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, Employee.class);
>             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]);
>                     System.out.println("\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.