VOODOO

VOODOO stands for "a Visual Object-Oriented Database language for ODMG OQL". It is a visual query formulation tool for OQL. Our design goal was to develop a visual language that can capture most OQL queries and at the same time is uniform and very simple to learn and use. Since query nesting is an important feature of any OODB query language, we designed our language in such a way that the composition of complex queries from simple ones is natural and intuitive.

A VOODOO query has a tree form that reflects the structure of the database schema, where every class or type reference in the schema is expanded, potentially leading to an infinite tree. The root of the tree is the persistent root and each tree node represents a class or a structure in the database schema. The tree nodes, which are called templates, are expanded on demand, so that only the minimal information is displayed. A query is formulated by mapping templates into values in some domain using a number of buttons and menus inside the template layout. The value of a template depends on the values of its children templates in the query tree as well as on the settings of its buttons and menus. The structure of the database, which is reflected in the query tree, determines the methods for accessing the database to retrieve data (i.e. it specifies which data paths to follow and which collections to traverse) and it is specified from the root to the tree leaves. The actual data manipulation and the formulation of the query result is specified from the tree leaves to the root by mapping each template to some value, which in turn is passed to the parent of the template to form the value of the parent template. The template mappings as well as the composition of the template values are formed in a pure functional way. Since new value domains are formed in each template, type information about these mapped values is very important to the user. There is sufficient type information displayed by the system that guides every stage of the query construction. In addition, VOODOO uses type information to reject invalid queries, so that queries constructed in our system are always type correct.

The VOODOO interface is invoked by executing:

./voodoo

The host name can be either an IP number or a name, such as functor.uta.edu. Here the server is the same as the client (the local machine). Each server may export many schemas, but each schema must have its unique port number. If the connection succeeds, the main VOODOO interface is displayed. The following image shows a snapshot of the VOODOO interface after the complete drawing of a query:

There are two main windows in the interface: the VOODOO query formulation canvas and the OQL query window. After a user completes the drawing of a VOODOO query on the canvas, the OQL textual form of the query can be constructed and displayed on the upper half of the OQL query window by pushing the button 'generate OQL'. The query can then be sent to a remote interpreter and evaluated by pushing the button 'evaluate'. The results of the evaluation are displayed on the lower half of the OQL query window. The button 'clear' clears the OQL query window. The menu item 'trace' indicates that all optimization phases will be displayed along with the results. The menu 'level=2' indicates how many levels deep the printer will print the nested collections and objects. Collections at a deeper level are printed as C(#n), where C is the collection name and n is the number of elements, while objects at a deeper level will contain the key values only.

Examples of Queries

In this section we present eight queries to show the basic features of our visual query language. For our examples, we use the School ODL schema, which describes a University database.

Our query formulation interface consists of a drawing canvas that contains a number of rectangles, called templates, connected by lines. For example, the following query

finds the name of the department whose head is Smith. This query can be expressed in OQL as follows:

select name: d.name
from d in Departments
where d.head.name = "Smith"

Initially, when its button has not been pushed, the type of an attribute is the type defined in the database schema. This is called the original attribute type of the button, to be distinguished from the derived attribute type, which depends on the types of the children templates of this button, as we will see next. For example, the original type of the Department attribute in the Persistent Root template is set<Department>. When a button is pushed, it creates a template that reflects the structure of its original attribute type. For example, if we push the Departments button we create the Department template, which is displayed next to the Persistent Root template and is connected to the Departments button by a line. This new template contains the attributes of the class Department. When the head button in the Department template is pushed, an Instructor template is created (since the original type of the head is Instructor). Finally, when the name button in the Instructor template is pushed, another template for the string type is constructed (since the original type of the Instructor name is string). This template is similar to the other templates but has no attributes.

A template, which is generated by pushing a button, specifies a function that maps the original attribute type of the button into some domain. The derived attribute type of the button is equal to this domain type, which may be different from the original attribute type. The buttons and menus inside a template are used in specifying this mapped value of the template. The P check-button at the left of an attribute button indicates whether this attribute should be considered in the mapped value (when P is on) or not (when P is off). (The G button is for grouping-by and will be explained later.) The mapped value of the template is an OQL struct that contains all the P-checked attributes in the template. If this struct contains one element only, the struct is dropped and the mapped value becomes the element itself.

At the top left side of the Department template there is a menu, called an accumulator, which indicates how to accumulate the selected attributes to form the mapped value. For each collection type in the original attribute type, there is one accumulator next to the template name that indicates how to handle this collection. The Instructor and string templates in our example do not have accumulators because their original types were not collections. The Department template though has one accumulator since the original type was set<Department>. The Department accumulator indicates that we form a bag out of the selected values. Thus the mapped value of the Department template has the type bag<string>, which also indicates that the derived attribute type of the button Departments in Persistent Root is also bag<string>, which in turn is the type of the query result.

The cond entry window in a template indicates a condition to be satisfied by the mapped value of this template. The syntax of the condition is similar to that of the Microsoft Access Query-by-Example interface. For example, if the mapped value is an integer, then one valid condition is: >100 and <200, which indicates that the integer value must be between 100 and 200. In our example, the string template indicates that the string must be equal to "Smith". If no attribute is selected and the cond is not empty, then the template is mapped into a boolean, which is the result of the condition. If the condition is empty too, the derived type is equal to the original type. For example, the string template is mapped into a boolean, which indicates that the Instructor name has now a boolean attribute type. Since the Instructor name is P-checked, the Instructor template is mapped into a boolean too. If the derived type of an attribute is a boolean, then this boolean is used as a condition to be satisfied by the template. This means that, since the Department head attribute is of type boolean, it is used as a condition, namely in d.head.name="Smith" for every department d.

To summarize, it took us five button clicks and the typing of the word "Smith" to construct our first query. In fact most OQL queries can be constructed using a small number of button clicks and the unavoidable typing of some constant values.

Type information is very important when constructing queries in our framework. To simplify this process, our interface displays all the necessary type information and, more importantly, it restricts any type inconsistent query construction. For example, if the mouse cursor is positioned on top of a button, a small label is displayed on the canvas with the derived type of the attribute associated with the button. A similar label is displayed when the mouse cursor is positioned on top of the template header. This label contains the derived type of the button associated with the template. Guiding labels with usage help are also displayed when the mouse cursor is on top of labels and buttons. There is also support for tree editing functionality, which allows us to display queries nicely. For example, if we click and drag the template from its header using the left mouse button, we can move the template into a new position on the canvas, dragging its connected lines along with it. If we do the same with the middle mouse button, we drag the template along with all its descendent templates. If we click a template header using the right mouse button, then this template, all its descendent templates, and all their connecting lines are removed from the canvas.

A more challenging example of a query construction is the following query

It finds the names and addresses of all instructors in the CSE department who earn more than 10K. This query can be expressed in OQL as follows:

select name: e.name, address: e.address
from d in Departments,
     e in d.instructors
where d.name = "CSE"
and e.salary > 10000

bag<struct( name: string, address: struct( street: string, zipcode: string ) )>

There are many other types of accumulators. For instance, the following query

uses the accumulators "all" and "some" to express universal and existential quantifications. This query can be expressed in OQL as follows:

select e.name
from e in Instructors
where for all  c in e.teaches:
          exists d in c.has_prerequisites: d.name = "CSE5331"

If we select "list" as an accumulator, then a new button S is displayed next to every attribute in the template (which disappears when the accumulator changes to something else). If an S button is pushed, then the corresponding attribute is chosen for sorting. For example, the following query

sorts departments by the number of full professors. It corresponds to the OQL query:

select name: d.name, instructors: count(select  * from e in d.instructors
                                        where e.rank = "Full Professor")
from d in Departments
order by count(select  * from e in d.instructors
               where e.rank = "Full Professor")

The group-by construct is syntactic sugar in OQL; it can be easily (and better) expressed using nested queries. The same is true for our query language. Even though the group-by construct is non-functional and often confusing, we decided to supported it directly in our framework in order to be compliant with legacy query languages. We will present later an alternative way of performing a group-by. For example, the following query

groups all instructors by their department name and by the number of CSE courses they teach. It corresponds to the OQL query:

select salary: max(e.salary), dept: e.dept.name
from e in Instructors
group by dept: e.dept.name,
      teaches: count(select  *
                     from c in e.teaches
                     where c.offered_by.name = "CSE")

Arbitrary join predicates between template attributes can be constructed using join lines on the canvas. The following query

for example, finds all courses taught by the heads of the offering departments, and has the following OQL form:

select c.name
from c in Courses
where c.taught_by = c.offered_by.head

The last query displayed below

is an alternative way of performing a group-by using nested queries. It represents the OQL query:

select dept: e.dept.name,
       Instructors: max(select  s.salary
                        from s in Instructors
                        where e.dept.name = s.dept.name)
from e in Instructors

select dept: e.dept.name, Instructors: max(e.salary)
from e in Instructors
group by e.dept.name

Limitations

Even though our framework can capture most OQL queries, there are some serious limitations that we hope to address in a future research. The most important limitations are listed below:

• record construction in our framework is very limited, namely, there is no choice on attribute names and record attributes are constructed only in the order listed in the templates;
• our group-by construct allows having conditions (i.e., conditions after group-by) for non grouped-by values, and regular conditions (before group-by) for grouped-by values only;
• the OQL code in the cond part of a template is not type-checked by our system (this can be fixed by calling the OQL compiler when a condition is written);
• there is no support for constructing constant collections, disjunctive predicates, unions, and array operations (e.g. the nth element of a list);
• finally, there is no visual way of calling methods and some predefined operations.