Language

i3Ql is a domain specific query language that is embedded in the Scala programming language. Queries formulated in i3QL are translated to incremental computations that automatically maintain results in the event of changes to the inputs. Queries are formulated in an SQL-inspired query language that allows a declarative formulation of incremental computations, is compositional, and broadly applicable due to i3QL's support for general recursion.

This page gives an overview of the language features and how to use them.

An extent represents a multiset that provides a standard collections interface permitting the addition, removal, and update of elements. For example, the following code declares an extent students containing Student objects.

val students: Extent[Students] = new VirtualExtent[Student]()

Extents are the basic type multiset over which queries are formulated using an SQL-like syntax. In the following example query sallies we filter the students multiset to select only those students whose first name is Sally.

The result of a query is a view that is again a multiset and can be traversed by the user or processed by further queries.

val sallies: View[Student] = 
(SELECT (*) FROM students WHERE (s => s.firstName == “Sally”)).asMaterialized

The i3QL views are incrementally maintained and updated whenever the queried multisets change. To this end, i3QL registers a query with all involved relations to receive change notifications. For example, the query sallies receives a change notification whenever the multiset students is changed. The result of sallies is updated incrementally. In particular the predicated s => s.firstName == “Sally”)is executed exactly once for each student consecutively added in the code below.

students.add(new Student(“Sally”, “Fields”))
students.add(new Student(“George”, “Tailor”))
sallies.foreach(s => println(s.lastName)) // prints: “Fields”
students.add(new Student(“Sally”, “Joel”)) // incremental update of sallies
sallies.foreach(s => println(s.lastName)) // prints: “Fields” and “Joel”

Without support for incremental maintenance, the first two students would be tested twice, once for evaluating the first foreach traversal and again in the second foreach. Instead of recomputing a query's result, i3QL incrementally maintains a query's result. While both views and extents are multisets, only extents are designed to trigger the incremental maintenance. This keeps the semantics for views simple, since updates of a view's elements raises the question whether a reverse maintenance, i.e., from views to extents, is possible.

An i3QL multiset occurs either as virtual or as a materialized. A virtual multiset does not store any of its elements and is only used to notify dependent queries about changes. For example, the students extent is declared as a virtual multiset. As a consequence, the Student object “George Tailor” is not persisted (in memory) in our example. When adding “George Tailor” to students in the extent does not store the object, but only notifies the query sallies, whose result does not contain “George Tailor” either. Thus, the usage of a virtual multiset has allowed us to forego persistence of objects that are irrelevant to the user that defined the query. A materialized multiset is different from a virtual multiset in that it also stores the elements of the relation for later use. For example, we declared that the view sallies should produce a materialized multiset, because we want to use the resulting elements outside of i3QL queries; namely in the two foreach traversals.

i3QL queries can be composed from existing queries, since extents and views uniformly represent multisets. For example, the following query computes the average age of students whose first name is Sally:

val averageAge = SELECT AVG((_:Student).age) FROM sallies 
println(averageAge.head)

i3QL incrementally maintains the multiset averageAge by updating the result whenever the multiset sallies changes. Note that changes to students do not directly affect averageAge; only students that pass the filter in sallies lead to an update of averageAge. This allows the modular specification and composition of incrementally maintained queries in i3QL.

i3QL contains incremental versions of all standard operators from SQL. In the above examples we already saw selection, projection, and average aggregation. In addition to the standard operators, i3QL also features general recursion, which makes i3QL a Turing-complete language for incremental computations. In particular, i3QL is not limited to traditional SQL-style computations, but supports incrementality for all kinds of computations.