Categorical Databases

Typesides

Every CQL file begins with a typeside. The typeside for this tutorial contains two java_types: String, which is bound to java.lang.String; and Integer, which is bound to java.lang.Integer. The java_constants section defines, for each java_type, javascript code that creates a value of that type from a string. For example, when the string 100 is encountered in an CQL program and needs to be interpreted as an Integer, CQL will execute the parseInt function on the string 100, yielding a java.lang.Integer. Similarly, the java_functions section defines the plus function.

Schemas

A schema on a typeside Ty contains a set of entities, a set of attributes taking entities to types, a set of foreign_keys taking entities to entities, a set of path_equations between paths of foreign_keys, and a set of observation_equations between attributes and foreign_keys.

In the following schema, the entities are Employees and Department. The manager foreign_key takes every Employee to their manager, and similarly for worksIn and secretary. The path_equations state that every Employee e's manager worksIn the Department which e works in, and that every Department d's secretary worksIn d.

The name attribute takes every Department to its name and similarly for first, last, age, cummulative_age. The observation_equations state that every Employee e's commulative_age is the sum of e's age and e's manager's age.

Instances

An instance on a schema S contains a set of generators and a set of variable-free equations between those generators. In this example, there are three generating Employees: a,b,c, and two generating Departments: m,s. The equations specify, for example, that the name of m is Math. The IDE shows the tables generated by this instance.

Note that the IDs in the tables do not directly correspond to the generators: CQL chooses IDs non-deterministically (e.g. c does not appear in the instance, but b.manager does). Note also that the tables contain nulls: a.last, for example. Finally, note that the cummulative_age attribute is automatically populated in the tables.

Tables can be sorted by clicking on their column headers.

Mappings

An mapping from schema C to schema D takes each entity in C to an entity D, each foreign_key in C to a path of foreign_keys in D, and each attribute in C to a lambda expression in D (which may be abbreviated as a path). In this example, the two entities N1,N2 are taken to N, the foreign_key f is taken to the zero-length path on N, and the attribute age is taken to age. We also define an instance on D which will be used later.

schema C = literal : Ty {
	entities
		N1 N2
	foreign_keys
		f : N1 -> N2
	attributes
		age : N2 -> Integer
		name : N1 -> String
		salary : N1 -> Integer}

schema D = literal : Ty {
	entities
		N
	attributes
		age : N -> Integer
		name : N -> String
		salary : N -> Integer}

mapping F = literal : C -> D {
	entity
		N1 -> N
	foreign_keys
		f -> identity
	attributes
		name -> lambda _x. name(_x)
		salary -> lambda x. salary(x)
	entity
		N2 -> N
	attributes
		age -> lambda x. age(x)}

We also define an instance on D which will be used later.

Delta and Sigma

Given a mapping F from schema C to schema D, the delta operation converts instances on D to instances on C. It can be thought of as projection:

instance deltaFJ = delta F J

Given a mapping F from schema C to schema D, the sigma operation converts instances on C to instances on D. It can be thought of as union, followed by merge. In this example, sigma undoes delta:

Uber-flowers (From-Where) queries

In addition to mappings, so-called uber-flower queries can be used to define relationships between schemas and to migrate data from one schema to another. Such queries can be evaluated, providing a similar semantics to SQL. However, unlike SQL, CQL guarantees, at compile time, that queries can only result in instances which obey their data integrity constraints.

A query from schema C to schema D specifies, for each entity d in D, a from-where-return statement that defines how d is to be populated. In addition, a query specifies how the foreign keys in D must be populated. Here is a query corresponding to the previous section's delta; it does not require any where clauses. The block corresponding to foreign key f says that for each x inserted into N1, the y to which x should be sent to by f is x. In general, the foreign_keys part of a query is the most difficult part to write and should be attempted only after writing the entities part.

query deltaFAsQuery = literal : D -> C {
entity N2 -> { 
	from 
		y : N
	attributes
		age -> age(y)}
	
entity N1 -> { 
	from 
		x : N
	attributes
		name -> name(x)
		salary -> salary(x)
	foreign_keys
		f -> {y -> x options }}}

instance deltaFJ_prime = eval deltaFAsQuery J

Here is a query corresponding to the previous section's sigma:

query sigmaFAsQuery = literal : C -> D {
entity N -> { 
	from 
		n1 : N1
	attributes
		age -> age(f(n1))
		name -> name(n1)
		salary -> salary(n1)}}

instance sigmaFdeltaFJ_prime = eval sigmaFAsQuery deltaFJ_prime