Resolving Cycles

The basic principles for resolving cycles in a single-class recursive object model are outlined in link Data Structures Can Have a Unique Root(s), but not Always.

The challenges of resolving cycles and roots are, in fact, significantly more complex because a single class can have multiple direct or indirect references to itself, multiple classes may participate in recursion, and cycles can occur even without a truly recursive class in the object model. Inheritance adds further complexity, as a class may have many inherited subclasses, each with varying numbers of references to their own class hierarchy or to other classes.

The image below illustrates a simple object model consisting of seven classes (A–F). For example, a database search with the search condition set for class F (value = 50) must navigate through classes D and C to locate root objects in classes A and B. While there is no recursion, even such a basic query is not supported by any relational database using the SQL command language.

The object model from the previous example has been modified so that the reference fields of classes C, E, F, and D form a cycle, but the query remains the same. Now, resolving the root objects in classes A and B also requires resolving the cycle involving F, D, C, E, and back to F.

Before proceeding with the multi-class object model, it is easier to begin with examples of a simple single-class recursive object model.

One Class Recursive Object Model

Resolving Root Objects and Cycles

The following discussion focuses on an object model with only a single class, Person. However, the concepts presented for resolving root objects would still apply and function correctly even if there were classes inherited from the Person class. This includes scenarios where these inherited classes have recursive relationships with the Person class or among themselves, as well as recursion within other classes in the inheritance hierarchy.

Below is a source code excerpt of the Person class, which includes a Person list reference field, friends, that can be used to build a network of Person objects. In other words, the object model is recursive and is well suited for constructing data structures that may contain cycles.

public class Person {
    public Long id;
    public String name;
    public List<Person> friends;

    public Person() {
    }
}

The Person class has only one recursive field, but there could be several, and this would not significantly impact efficiency, for instance.

The example below features a wide variety of cycle structures. The cycles are interconnected, with many objects participating in multiple cycles, and two cycles forming loops in both directions through the same objects.

Example with Many Cycles: The Person objects and their names are shown in the image below.

RQL Query: The search condition name = 'p12' is set for the Person objects. The method call setResolveCycles(true) is explicitly shown, although it is unnecessary as the default value is true. Setting the resolveRoots attribute to true automatically resolves all root objects for the query result (the found Person objects with name = 'p12') within the recursive data structure of the Person class. Additionally, the parts attribute is set to true, meaning the returned root objects will include only those objects in their data structures that matched the search condition or were encountered during the process of resolving the root objects.

RootStore r1 = rdb.getRootStore("fi.rootrql.example1.Person");
Query query = Query.createQuery()
		.addQuery(r1, "(name = 'p12')")
		.setParts(true)
		.setResolveRoots(true)
		.setResolveCycles(true);
List<Person> list = query.queryObjects();

Query Results: The results are illustrated in the image below. The searched and found object p12 is marked in red, the resolved root objects p30, p50, and p23 are marked in blue, and their data structures are highlighted in dark yellow.

The query result contains three objects: p23, p30, and p50. For each, a complete data structure is returned, extending up to the searched object p12. Object p23 has a simple data structure, containing only object p22 and the searched object p12. Objects p30 and p50 are more complex, and it may not be immediately clear what their data structures will include. The root-resolving algorithm returns all paths from the found root objects to the searched object. In this case, the data structures show that both objects p30 and p50 can reach all objects, except p22 and p23, on their routes to the searched object p12. Therefore, the data structures of both contain all objects marked in dark yellow between them and p12.

Several Classes without Direct Recursion in the Object Model

Resolving Roots and Cycles is a Big Challenge

Below is a source code excerpt of 21 Java classes that can be used to simulate the network of Person objects created earlier, but now without direct recursion in the object model. Each Java class includes the necessary reference fields used to establish relationships in the Person object network, though the relationships are now between Cn objects. Resolving root objects and cycles in a data structure formed by multiple classes presents a significantly more complex algorithmic challenge than resolving a data structure based on a single recursive class. Note that, in this case as well, each Cn class can have an inheritance hierarchy, and the root objects would still be resolved correctly.

In other words, even if none of the classes in the object model are recursive, the model can still be used to create data structures that contain cycles, for example.

public class C10 {
    public Long id;
    public String name;
    public List<C11> f11;
}

public class C11 {
    public Long id;
    public String name;
    public List<C17> f17;
    public List<C27> f27;
}

public class C12 {
    public Long id;
    public String name;
}

public class C13 {
    public Long id;
    public String name;
    public List<C21> f21;
}

public class C14 {
    public Long id;
    public String name;
    public List<C17> f17;
}

public class C15 {
    public Long id;
    public String name;
    public List<C24> f24;
}

public class C16 {
    public Long id;
    public String name;
}

public class C17 {
    public Long id;
    public String name;
    public List<C10> f10;
    public List<C11> f11;
    public List<C27> f27;
}

public class C21 {
    public Long id;
    public String name;
    public List<C43> f43;
}

public class C22 {
    public Long id;
    public String name;
    public List<C12> f12;
}

public class C23 {
    public Long id;
    public String name;
    public List<C22> f22;
}

public class C24 {
    public Long id;
    public String name;
    public List<C40> f40;
}

public class C25 {
    public Long id;
    public String name;
    public List<C12> f12;
}

public class C26 {
    public Long id;
    public String name;
    public List<C16> f16;
}

public class C27 {
    public Long id;
    public String name;
    public List<C11> f11;
    public List<C17> f17;
    public List<C43> f43;
}

public class C30 {
    public Long id;
    public String name;
    public List<C10> f10;
}

public class C40 {
    public Long id;
    public String name;
    public List<C15> f15;
    public List<C25> f25;
    public List<C26> f26;
    public List<C41> f41;
}

public class C41 {
    public Long id;
    public String name;
    public List<C42> f42;
}

public class C42 {
    public Long id;
    public String name;
    public List<C43> f43;
}

public class C43 {
    public Long id;
    public String name;
    public List<C13> f13;
    public List<C14> f14;
    public List<C40> f40;
}

public class C50 {
    public Long id;
    public String name;
    public List<C40> f40;
}

The example below, consisting of objects from 21 Cn classes, has the same basic structure and cycle patterns as the previous example, which used the recursive Person class. However, resolving root objects and cycles is now a more complex challenge, as the objects are instances of multiple distinct classes.

Example 1 with Many Cycles: The same object names (pn) are used as in the previous example with the Person class. The class names (Cn) and their corresponding object names (pn) share the same numbering.

RQL Query 1: The search condition name = 'p12' is set for objects of class C12. The method call setResolveCycles(true) is explicitly shown, although it is unnecessary since the default value is true. Setting the resolveRoots attribute to true automatically resolves all root objects for the query result (the found C12 objects with name = 'p12') within the recursive data structure of the Person class. Additionally, the parts attribute is set to true, meaning the returned root objects will include only those objects in their data structures that matched the search condition or were encountered during the process of resolving the root objects.

RootStore r12 = rdb.getRootStore("fi.rootrql.example1bb.C12");
Query query = Query.createQuery()
		.addQuery(r12, "(name = 'p12')")
		.setParts(true)
		.setResolveObjectModel(true)
		.setResolveCycles(true);
List<C12> list = query.queryObjects();
List<C50> list50 = r12.transferObjectList("fi.rootrql.example1bb.C50");
List<C30> list30 = r12.transferObjectList("fi.rootrql.example1bb.C30");
List<C23> list23 = r12.transferObjectList("fi.rootrql.example1bb.C23");

Query Results 1: The results are illustrated in the image below. The searched and found object p12 is marked in red, the resolved root objects p30, p50, and p23 are marked in blue, and their data structures are highlighted in dark yellow.

Note that the actual database search is executed with the method call query.queryObjects(), which returns objects of class C12 that meet the search condition.

Resolved root objects must be queried or, more precisely, transferred from the query result using the query's RootStore object, r12. Its method transferObjectList returns the result objects of the canonical name passed as a parameter. This method must be called three times, once for each of the classes C50, C30, and C23

The resolved root objects are the three objects p23, p30, and p50. For each, a complete data structure is returned, extending up to the searched object p12. Object p23 has a simple data structure, containing only objects p22 and the searched object p12. Objects p30 and p50 are more complex, and it may not be immediately obvious what their data structures will include. The root-resolving algorithm returns all paths from the found root objects to the searched object. In this case, the data structures show that both objects p30 and p50 can reach all objects, except p22 and p23, on their routes to the searched object p12. Therefore, the data structures of both contain all objects marked in dark yellow between them and p12.

Example 2, C50 to C12: When the path through object fields to the searched object(s) is known, it can be used as a search condition. However, automatic resolving of root objects offers a convenient and efficient alternative when the path is unknown. Both options are presented below. It's important to note that automatic resolving of root objects may be a better and more reliable option when multiple paths exist to the searched object(s), as it is not always certain that all objects are present in the known or expected path.

Field names of classes from C50 to C12 are written in the search condition, separated by dots, following standard object-oriented programming (OOP) practices.

RootStore r50 = rdb.getRootStore("fi.rootrql.example1bb.C50");
Query query = Query.createQuery()
				.addQuery(r50, "(f40.f25.f12.name = 'p12')")
				.setParts(true);
List<C50> list = query.queryObjects();

OR:

Resolving root objects is limited to the four classes C12, C25, C40, and C50, as only objects from these classes are intended to be included in the results. To achieve this, the setResolveRoots method is called, with its parameter list specifying the classes to include. Note that the order of the classes does not matter.

RootStore r12 = rdb.getRootStore("fi.rootrql.example1bb.C12");
Query query = Query.createQuery()
				.addQuery(r12, "(name = 'p12')")
				.setParts(true)
				.setResolveRoots("fi.rootrql.example1bb.C12",
                                 "fi.rootrql.example1bb.C25",
                                 "fi.rootrql.example1bb.C40",
                                 "fi.rootrql.example1bb.C50");
List<C12> list = query.queryObjects();
List<C50> list50 = r12.transferObjectList("fi.rootrql.example1bb.C50");

Query Results 2: Both of the above alternatives for searching object p12 return the same result: object p50 and its data structure extending to object p12. The data structure includes objects p40, p25, and p12.

The searched object p12 is marked in red, the root p50 is marked in blue, and its data structure is highlighted in dark yellow in the image below.

Example 3, C30 to C12: In a similar manner to the example above, database searches can be constructed to retrieve the data structure of object p30, with only one route to object p12.

Field names of classes from C30 to C12 are written in the search condition, separated by dots, following standard object-oriented programming (OOP) practices.

RootStore r30 = rdb.getRootStore("fi.rootrql.example1bb.C30");
Query query = Query.createQuery()
        .addQuery(r30, "(f10.f11.f27.f43.f40.f25.f12.name = 'p12')")
        .setParts(true);
List<C30> list = query.queryObjects();

OR:

Resolving root objects is limited to the eight classes C12, C25, C40, C43, C27, C11, C10, and C30, as only objects from these classes are intended to be included in the results. Note that the order of the classes in the parameter list of the setResolveRoots method does not matter.

RootStore r12 = rdb.getRootStore("fi.rootrql.example1bb.C12");
Query query = Query.createQuery()
				.addQuery(r12, "(name = 'p12')")
				.setParts(true)
				.setResolveRoots("fi.rootrql.example1bb.C12",
						         "fi.rootrql.example1bb.C25",
						         "fi.rootrql.example1bb.C40",
						         "fi.rootrql.example1bb.C43",
						         "fi.rootrql.example1bb.C27",
						         "fi.rootrql.example1bb.C11",
						         "fi.rootrql.example1bb.C10",
						         "fi.rootrql.example1bb.C30");
List<C12> list = query.queryObjects();
List<C30> list30 = r12.transferObjectList("fi.rootrql.example1bb.C30");

Query Results 3: Both of the above alternatives for searching object p12 return the same result: object p30 and its data structure extending to object p12. The data structure includes objects p10, p11, p27, p43, p40, p25, and p12.

The searched object p12 is marked in red, the root object p50 is marked in blue, and its data structure is highlighted in dark yellow in the image below.

Example 4, C30 to C12: The long list of dot-separated field names in Example 3 above can also be split into two or more query parts.

Below, the database search is divided into two parts: Q1 and Q2. Query part Q1 includes a search condition that covers objects from classes C30 to C40. It ends with the condition that the f40 field of class C43 must contain an object that exists in the result of query part Q2. Query part Q2 includes a search condition for class C40 and defines a route to class C12, where an object with the name 'p12' is being searched for.

RootStore r30 = rdb.getRootStore("fi.rootrql.example1bb.C30");
RootStore r40 = rdb.getRootStore("fi.rootrql.example1bb.C40");                        
Query query = Query.createQuery()
				.addQ1Query(r30, "(f10.f11.f27.f43.f40 IN (Q2))")
				.addQ2Query(r40, "(f25.f12.name = 'p12')")
				.setParts(true);
List<C30> list = query.queryQ1Objects();

Query Results 4: The result is the same object p30 and its data structure extending to object p12, as in Example 3 above. The data structure includes objects p10, p11, p27, p43, p40, p25, and p12.

Splitting the search condition into multiple parts is particularly useful when the result of one query part is needed in several places within the search conditions of other query parts. Additionally, some programmers may find that dividing search criteria into smaller parts improves the readability of database searches.

The searched object p12 is marked in red, the root object p50 is marked in blue, and its data structure is highlighted in dark yellow in the image below.

The query result object p30 is displayed in the debug view below.

The examples above are quite complex and would be extremely difficult to implement using relational databases. Relational databases and the SQL command language do not provide any automatic mechanisms for resolving root objects, requiring case-specific solutions to be programmed for each database structure (schema). In practice, this results in a time-consuming and resource-intensive programming task. Moreover, it is highly unlikely that such ad hoc solutions would match the efficiency of RootDB's generic, performance-optimized approach.

In fact, the automatic resolving of root objects introduces a new way of thinking about database searches and writing query expressions. It represents a novel category of database queries, likely previously unexplored due to the dominance of relational databases and SQL, which lack any support for objects. A common use case for database searches is shown in RQL query 3: search for User objects, where automatic root object resolution can also be applied.