In the prequel paper we introduced the Unied State Model (USM), i.e. a single model that allowed conveying objects of popular programming languages and databases. That model exploited and emphasized common properties of all these objects. We showed mappings between those popular data models and USM. Our natural next research goal is the Unied Query Language (UQL). UQL is intended to be a minimalistic and elegant query language that allows expressing queries of major query languages. We plan to build a concise set of operators and show its coverage for mentioned languages' constructs. In this paper we present our initial eorts towards UQL. We present a set of language operators. We also provide a number of redolent examples of queries expressed in UQL.
Our research originates from the so called object-relational impedance mismatch
[
In our prequel paper [
Having the data model of major programming and storage environments (USM), we were naturally tempted to pose a new research question. Is it possible to dene a Universal Query Language (UQL) on the USM? UQL should subsume query languages for models that were subsumed by USM. This will supply evidence that also mapping queries between major programming and storage systems is a not miracle but a natural consequence of numerous similarities.
In this paper we show initial results of our research, i.e. a preliminary list
of UQL operators and a number of representative examples of queries and their
expression in UQL. Of course, the naturalness of the example mapping prove
nothing. However, it suggests that building UQL is feasible. The next genuine
step will be to establish a full set of UQL operators and to develop proofs that
UQL subsumes query part of SQL, OQL [
In fact, the success of Hibernate, observed on the market place, and objectrelational mapping systems show that after C++ ceased to be the programming language of the rst choice in favour of e.g. Java, Python and the C#, the development of object-relation mapping became signicantly easier.
The paper is organized as follows. In Section 2 we sketch basic denitions of the Universal State Model (USM). Section 3 enumerates operators of the preliminary version of the Universal Query Language (UQL). In Section 4 we show a number of example queries and disccus their smooth mapping to UQL. Section 5 concludes. 2
In this Section we remind some denition of the Unied State Model (USM)
introduced in [
We use the following symbols. V is a set of atomic values. We assume that it contains all simple values. N V is a set of external names of objects with a chosen value 2 N to tag nameless objects. External names are used by designers and programmers to access objects. Nameless objects can only be accessed through object references. I V is a set of identities with a chosen value nil 2 I to represent empty identier/address. We assume that N \ I = ;.
For any set S we denote by S = Lt2N S, i.e. the set of all nite sequence of elements of S.
Denition. A state of an object of the level 0 is a triple (i; n; v) 2 I N V . By O0 we mean the set of all states of the level 0. This set is also denoted by S0. Denition. Let t 2 N be a positive natural number and assume that we have dened states of objects of the level k for all k < t and St 1 denotes the set of all states of objects of the levels lesser than t. A state of an object of the level t is a triple (i; n; L) 62 St 1 where i 2 I; n 2 N and L 2 St 1 is a nite sequence of elements of St 1 and L 2= St 2. We assume that S 1 = ;. The set of all states of objects of the level t will be denoted by Ot. By St = Ot [ St 1 we denote the set of all states of objects of the levels not greater than t. Members of the list L will be called states of subobjects of the object state o.
Each object has a name, an identier and a value. This value can be simple (like in objects of the level 0) or be a list of objects. According to the above denition an object of level t > 0, i.e. a member of Ot, has at least one subobject of level t 1. Therefore, the level of an object is the maximum subobject nesting depth in this object.
S1 is the set of all states of objects of all natural levels.
In [
Since in Section 4 we use SQL queries to illustrate concepts of UQL, below we
also remind some information on the mapping between USM and the relational
model presented in [
Let R be a relational schema, also called the type of a relation denoted by dom(R) such that dom(R) = dom(A1) ::: dom(An), where dom(A) V is some domain.
We dene a tuple of a relation of type dom(R) as a state of an object o =
(i; R; o1; :::; on) such that for k = 1; :::; n ok = (ik; Ak; vk) is an atomic object
such that vk 2 dom(Ak). In particular, a tuple o 2 O1 is a state of the rst level.
Let us recall a denition from [
= (i; emp; f
o0 = (i0; person; f
Next we deal with relations that are dened by Grefen [
Denition. Let the states o = (i; R; T ) 2 O2 and o0 = (i0; R; T 0) 2 O2 be of the second level, where T and T 0 are sequences of states of the rst level. Assume also that o R o0. States o and o0 are called relationally equal i jT j = jT 0j and there is a permutation p of the sequence T , such that for each t = 1; :::; jT j the states of the tuples p(T )t and Tt0 are relationally equal.
Note that states of the second level from the above denition model multisets of tuples and the relational equality of states dened above is an equivalence relation. 3
In this Section we introduce operators of the Universal Query Language (UQL). Let SS be the set of all functions Q : S ! S. Queries of UQL are functions from the set SS. These functions are compositions of UQL operators dened below. 3.1
Renaming The operator as gives an object a new name:
as : N ! SS as(n)((i; n0; v)) = (i; n; v)
Flattening For a complex object the operator f lat replaces its subjects with the contents of these subobjects. If the argument complex object is simple or has any simple subjects, f lat returns an empty object. Assume o = (i; n; (o1; o2; : : : ; ok)). If for all t = 1 : : : k ot 62 O0 and ot = (it; nt; (ot;1; : : : ; ot;jt ), then f lat(o) = (i; n; (o1;1; o1;2; : : : ; o1;j1 ; o2;1; : : : ; ok;jk ))
f lat(o) = (i; n; nil) The purpose of the operator map is the application of a function to all subobjects of the given object. The functor map : SS ! SS is dened as follows. Let f : S ! S be the function to be applied. Then: map(f )(o) = (i; n; (f (o1); : : : ; f (on)) if o = (i; n; (o1; o2; : : : ; ok)) 62 O0 (i; n; nil) if o 2 O0: 3.4
Evaluating Given a function on simple values we can apply it to the simple values stored inside an object. We introduce a family of functors eval. For a given natural t evalt maps any function f : V t ! V to the query evalt(f ) such that: evalt(f )(i; n; (o1; : : : ; ok)) = 8 (i0; ; f (v1; : : : ; vt)) < : (i0; ; nil) if k = t and
oj = (ij ; nj ; vj ) 2 O0 otherwise. 3.5
Getting k-th subobject Let o = (i; n; (o1; o2; : : : ; ot)) be a state of an object. We dene: takek(i; n; (o1; : : : ; ot)) = ok (i0; ; nil) if k < t and otherwise.
For k = 1 we will use notation takeF irst instead of take1. 3.6
Filtering Filtering is also performed by a functor. Assume a function p : S ! V that returns Boolean values. Then:
f ilter(p)(o = (i; n; (o1; o2; : : : ; ok))) = (i; n; (oi1 ; oi2 ; : : : ; oi0k )) where the sequence (oi1 ; oi2 ; : : : ; oi0k ) is the subsequence of (o1; o2; : : : ; ok) composed of all objects oj such that eval1(p(oj )) = true. 3.7
Nesting 3.8
Cloning The operator nest creates a new nameless object and puts the argument object into it:
nest(o) = (i0; ; o) The operator clonet for natural t > 1 duplicates the state of the given object t times. This operator does not preserve the propriety of the object since the clones will have repeated identities inside. The operator clonet : SS ! SS is dened as follows:
clonet(o = (i; n; x)) = (i0; n; ((i1; n; x1); : : : ; (in; n; xt))) where x1; x2; : : : ; xt are fresh object identiers. Let o = (i; n; (o1; :::; ot)); o0 = (i0; n0; (o01; :::; o0t0 )) be complex objects. The cross product operator is dened as follows:
cross(o; o0) = (i; ; ((o11; :::; o1t0 ; :::; ott0 ), where ojk = (ijk; ; (oj; o0k)) Let be an equivalence relation on a subset of states S (i; n; (o1; :::; ot)) be a complex object such that fo1; :::; otg abstract is dened as follows: S . Let o =
1
S. The operator where uj = (ij; n; (oj1; :::; ojtj )) and the following conditions are satised: a. The sequence (oj1; :::; ojtj ) is a subsequence of (o1; :::; ot) for all j = 1; : : : ; k and the sequence o11; :::; ok1 is a subsequence of (o1; :::; ot). b. The items in (oj1; :::; ojtj ) are pairwise related with respect to . c. For any j 6= j0 and m; m0 it is true that ojm 6 oj0m0 . 3.11
Transposing Let o = (i; n; (o1; :::; om)) be a complex state of an object, such that there exists a number t and a name n0, such that for all j = 1; :::; m, we have oj = (ij; n0; (oj;1; :::; oj;t)). In other words the state o represents a two dimensional m t matrix of states of objects. We dene the transpose operator as follows:
transpose(o) = (i0; n; (o1; :::; ot)); where ok = (i0k; n0; (o1;k; :::; ot;k)); for k = 1:::t 3.12
Folding Let o = (i; n; (o1; :::; ot)) be an complex model and f : S operator. We dene f old via induction: S ! S be a binary f oldf (o = (i; n; fo1; :::; otg)) = o , if t = 1 f oldf ((i0; n; (f (o1; o2); o3; :::; ot))) , if t > 1
In this Section we show some examples of SQL queries mapped to UQL. As we mentioned in the introduction, we do not treat them as a proof of the quality of UQL. However, the smoothness of the mappings in an indicator of the feasibility of our research goal.
In order to simplify the presentation we are going to use the following notation. When two unary operators op1; op2 are applied to a pair of objects, it is expressed as (op1 op2)(o1; o2).
Let us assume that we have the following relational database schema with two well-known tables: emp: empno, firstname, lastname, salary, deptno dept: deptno, deptname, location
Let us assume that the variable o represents the state of the database with the above schema. Our example query gets the following form in UQL: map( f iltername=0firstname0_name=0lastname0 ( f ilter9on:name(on)=0lastname0^value(on)=0Schmidt0 ( f latten( f iltername=0emp0 (o) ) Now let us consider a join. The following query is a natural join with an equality selection: ) )
)
Let us build the mapping step by step. Again we assume that the variable o is the state of the database. A from clause for a single table is realised as follows (we lter out other tables):
f iltername=0tablename0 (o) Thus, the clause from dept d is mapped as (the operator as augments the column name with d_):
map(asd_+name; f iltername=0dept0 (o)) Furthermore, from dept d, emp e is expressed as: (map(asd_+name; : : :) (f iltername=0dept0 duplicate2(o) ) )
map(ase_+name; : : :))( f iltern0ame=0emp0 )( Now the obtained objects are glued together:
f latten(cross(: : :)) and ltered:
f ilterval(d_deptno)=val(e_deptno)^val(d_deptname)=0IT 0 (: : :) Finally, we have to select the columns that constitute the result of the query: Altogether, our query formulated in UQL has the following form: map(f iltername=0firstname0_name=0lastname0 ; ) map(f iltername=0firstname0_name=0lastname0 ; f latten(cross( (map(asd_+name; :) (f iltername=0dept0 duplicate2(o) ) map(ase_+name; :))( f iltern0ame=0emp0 )( )
) )) Note that this construction of standard SPJ queries is quite regular. We start from the from clause, then goes where and nally select. Note that in all three steps most of the eort is in fact ltration. The process is compositional, so the mapping of subqueries will be similarly smooth. This way we can map other query languages: SBQL: emp where lastname = ’Schmidt’ HQL: from emp where lastname = ’Schmidt’ SQL: SELECT * from emp where lastname = ’Schmidt’ All of these queries simply map to the following UQL query:
f iltervalue(lastname)=0Schmidt0 (f latten(f iltername=0emp0 )) Finally, let us consider the aggregation. The example query follows:
Like previously, at the beginning we need to select the emp objects, atten them and lter out uninteresting subobjects: selo = map(f iltername=0deptno0_name=0salary0 ;
f latten(f iltername=0emp0 (o)) ) In the next step we cluster resulting objects using relation dn. Two objects are related by dn, if their subobjects deptno have the same value:
grpo = abstractdn(selo) The subobjects of grpo contain collections of pairs, but in order to f old them we need pairs of collections, so we transpose the matrices:
trso = map(transpose; grpo)
map(takeF irst (f laten f old+); trso) Eventually we have received a state containing a collection of pairs composed of deptno and the sum of salary. Thus, the example aggregation query maps to: map(takeF irst( f laten f old+); map(translate; abstractdn( map(f iltername=0deptno0_name=0salary0 ;
f latten(f iltername=0emp0 (o)) ) ) )
) The construction of this UQL query has been stepwise and natural. We are convinced that even complex SQL (and other QL as well) queries will smoothly map to UQL.
After successfully constructing USM (the Unied State Model), i.e. the unied model for a number of major programming and storage environments, we were naturally excited, if it is possible to build a Universal Query Language (UQL) on the USM? UQL is planned to subsume query languages for models that were covered by USM.
In this paper we made an initial attempt to answer this question. We presented a pilot list of UQL operators and a number of representative examples of queries and their expression in UQL. We chose two SPJ queries and one aggregate query, showed their smooth mapping to UQL and concluded that such queries seem to map well. Of course, this proves nothing. However, it indicates that building UQL is feasible.
The next step planned in our research it to found a nal robust set of UQL operator and show that UQL allows expressing the query part of SQL, OQL, SQBL, XQuery and other interesting query languages.