A Model-Independent Query Paradigm Founded on Arithmetic

1 INTRODUCTION

"Query" means various things in the database literature. It is sometimes used in the sense of a query language (as in [1], for example), possibly referring to all data retrieval operations, or to all data manipulation operations, or to operations on sets or other aggregates in general. The term is sometimes used in the narrower sense of a query operation which selects things from a collection based on some criterion, often in a "select...from...where" syntactic form. We will use the term in this last sense: a query is a specific operation which generates a collection of things from some other collection. By "query semantics" we mean some formal specification of the results produced by a query operation.

Historically, relational database queries were based on a constructive paradigm. Relations are constructed from other relations via the relational algebra of join, select, and project. The SQL select-from-where query format is a syntactic sugaring firmly rooted in these constructive semantics. Thus the semantics of relational query operations are inextricably tied up with the relational data model, setting an expectation that each new form of data model must give rise to its own form of query operation. In particular, we are currently witnessing various attempts to define "object-oriented" query.

However, the semantics of queries, aggregates, and expressions can be treated as orthogonal language/model components, rendering the query operation itself largely independent of data model. The semantics of a query operator can be defined arithmetically, rather than in terms of a specific data model.

What queries essentially do is select things from collections on the basis of their properties. A query operator can be described as a form involving certain expressions, with virtually no restriction on the expressions except that some return integer values and some return some form of collection. Since expression, collection, and integer are rather universal concepts, such a query paradigm is largely model-independent. Even grouping (Group-by) can be defined in this general style. This foundation can then be refined to exploit additional functionalities provided in various specific models, object-oriented or otherwise.

In this approach, the semantics of queries can be specified and standardized independently of specific data model and computational features, which can be defined orthogonally. The full behavior of queries in any language or model is then described as a composition of query operation semantics with particular data model and computational features supported in the language.

2 MODEL-INDEPENDENT SEMANTICS

2.1 A Descriptive Model

A collection is anything which can be said to contain one or more occurrences of things. Thus a collection c is characterized by an Occurs function such that for any thing x (we avoid the term "object" for now), Occurs(x,c) returns a counter (non-negative integer) which is the number of occurrences of x in c. A collection does not have to contain duplicates. Sets are collections characterized by the constraint Occurs(x,c) =<1.

Which things occur in c? Those for which Occurs(x,c)>0. How many things are in c? The sum of the number of times each thing occurs in c. Thus the cardinality of a collection c is given by Card(c)=SUM[x]Occurs(x,c). How do we compute such a summation? The exact answer depends on the specific collection. In general, the variable x must at least range over every thing which occurs in c. It is sufficient for the summation domain to be a set X such that Occurs(x,c)>0 => x IN X, i.e., everything which occurs in c must occur in X. The cardinality of c is then the sum of the number of occurrences of each of these things in c. When the collection c is constrained to contain only instances of a certain type T, it suffices to sum over the extension of T.

A principal result of this paper is to develop arithmetic formulas defining the behavior of Occurs(x,c) for the collections produced by queries.

By expression we mean anything which can be evaluated with arguments to return results, subsuming such notions as function, procedure, operation, message, property, predicate, attribute (as in SQL dot notation), variable, etc. Thus any of these constructs can occur where an expression is called for.

We use the term filter to mean an expression which returns a counter (non-negative integer) for any possible argument. Logical predicates are a special case of filters. They can be treated arithmetically by using 1 and 0 (Boolean numbers) for True and False; corresponding computations can be defined to yield logically correct results [2][7].

The Occurs function, filters, and Boolean numbers are elements of a descriptive model used in this paper to carefully define terms and concepts you and I will use in describing other (target) models and languages. It is not assumed that these features are implemented in any real target model or language, as desirable as that might be. If they were supported, then we could be describing query in terms of other language features, rather than via a mechanism external to the language.

In the descriptive model, a collection c also serves as its own "profile function" [7], so that the notation c(x) means Occurs(x,c), giving the number of occurrences of x in c. This notation characterizes the membership of the collection c. Thus, this paper seeks to define an arithmetic formula for c(x) to characterize the collection produced by a query. Such a profile formula can be used in several ways:

• Given a particular value of x, c(x) defines the number of times that x occurs in c.
• If the members of c are known to all be included in some set X, then evaluating c(x) for each x IN X characterizes the entire contents of c.

2.2 Query Overview

In the descriptive model, a query operation Q is a form containing three expressions d, w(x), and r(x), which will be described in subsequent sections. A query might be written in a syntax such as

SELECT r(x) FROM d x WHERE w(x).

A query in a target language should be rewritten in this form for subsequent analysis. The sequence of components, and the capitalized keywords, are illustrative only. Briefly,

• The expression d defines the search domain as an initial collection cd.
• The filter expression w(x) generates a collection cw of things which occurred in cd.
• The result expression r(x) generates a collection cr.

The definition of the query operator imposes minimal requirements on the expressions d, w(x), and r(x):

• d must return a collection (cd).
• w(x) must return a counter value for each element x occurring in cd.
• r(x) must be defined for each element x occurring in cd.

It is up to the orthogonal, model-dependent portion of the language specifications to define what constructs are allowed in these expressions and how the expressions evaluate to the appropriate value.

2.3 The Search Domain

The FROM d x clause provides the expression d defining the search domain cd. As mentioned, the definition of the query operation says nothing about the search domain other than that the expression d must yield a collection. In effect, the query will search over the elements of the search domain. The FROM clause also names the variable x which will be bound to things occurring in that collection.

For the query fragment

SELECT FROM Departments x,

2.4 Generalized Selection

The notion of selection is generalized to allow injection of duplicates. In the query

SELECT FROM d x WHERE w(x),

the filter w must return a counter value for any x in cd; if w can't do anything else, then 0 would seem to be the natural default. The result of this query is a collection cw such that

cw(x) = cd(x) * w(x).

The number of occurrences of some x in cw is the number of its occurrences in cd multiplied by w(x). If x does not occur in cd then cd(x)=0 and x will not occur in cw. If w(x)=0, x will not occur in cw. This general form allows the query result to contain duplicates either because the search domain cd contained duplicates or because the filter w defines multiple occurrences, or both. Simple selection from a set occurs when the search domain cd is a set (cd(x)=<1) and the filter is a predicate, returning 1 or 0.

x is a bound variable with respect to the query as a whole. During the course of executing the query, the variable is bound once to each distinct thing occurring in cd, for which w(x) is evaluated. We could also say that x gets bound to everything in some universe, with cd(x)=0 for things not occurring in cd. In general, the collections cd and cw might be infinite.

For example (in a target language which supports the appropriate notions of types and functions), if Openings(x) gives the number of open positions in a department x, then the collection returned by

SELECT FROM Departments x WHERE Openings(x)

would contain n occurrences of a department which has n openings. This could serve as a roster of open positions containing one entry for each opening, identified by department, which could then be used in subsequent operations to fill data into the openings. This example makes sense when all the jobs in a given department are the same.

The profile (arithmetic specification) of the above sample query is

cw(x) = Department(x) * Openings(x).

A thing x will occur n times in cw if x is a department and x has n openings.

A more conventional query might arise if Hiring(x) returned 1 (True) if department x has any openings, and 0 (False) otherwise. The query

SELECT FROM Departments x WHERE Hiring(x)

returns the set of departments which have any openings. The profile of this query is

cw(x) = Department(x) * Hiring(x).

2.5 Result Generation

The results of a query are often not the things actually selected from the search domain cd. If cd contains tuples, the query result might contain a projection or restructuring of the tuples. Or the query result might contain properties of the things selected from cd.

The SELECT clause can specify a result-generating expression r, extending the query form to

SELECT r(x) FROM d x WHERE w(x).

This yields another collection cr. The collection cr contains an occurrence of r(x) for each occurrence of x in cw. This in itself could introduce duplicates in cr, when r(x1)=r(x2) for distinct x1, x2 in cw. For example, the query

SELECT Location(x) FROM Departments x WHERE Hiring(x)

will return one occurrence of a given location for each department at that location which is hiring. Each such department contributes one occurrence of its location.

In general, if z=r(x) for some x in cw, the resulting collection cr will contain an occurrence of z for each occurrence of every x in cw such that z=r(x). The number of occurrences of z in cr is therefore obtained by summing over all x's occurring in cw, accumulating those for which z=r(x). The contents of cr can thus be characterized by

cr(z) = SUM[x](cw(x) * z=r(x))
= SUM[x](cd(x) * w(x) * z=r(x)).

The value of the expression z=r(x) is 0 or 1. For a given x occurring in cw, if z¬=r(x), then nothing is contributed to the result. Otherwise, cw(x) occurrences of z are contributed to the result.

The profile of the above sample query is

cr(z) = SUM[x](Department(x) * Hiring(x) * z=Location(x)).

This expression defines the number of times a particular z will occur in the query result cr. For the summation, it suffices to let x range over all departments. The collection cr will contain a certain location z if x is a department, x is hiring, and z is the location of x. If two departments which are hiring had the same location, that location would show up twice in the summation.

To fully characterize the collection cr, it is sufficient to let the variable z run over the range of the function r, since that contains all possible things that could occur in cr. For the last example, this would be the set of all locations. More narrowly, z can run over the "domain image" of r, which in this case would be the set of locations belonging to any department.

2.6 Summary

A query is a form which takes up to three expressions as its basic components, which can be illustrated in the syntactic form

SELECT r(x) FROM d x WHERE w(x).

The sequence of components, and the capitalized keywords, are illustrative only. The query is evaluated as follows:

1. FROM d -> cd.
2. x WHERE w(x) -> cw.

   cw(x) = cd(x) * w(x).

3. SELECT r(x) -> cr.

   cr(z) = SUM[x](cw(x) * z=r(x))
   = SUM[x](cd(x) * w(x) * z=r(x)).

Duplicates can arise as follows:

• The search domain cd can contain duplicates: cd(x)>1 for some x.
• The filter w can introduce duplicates if w(x)>1.
• The result generator r can introduce duplicates if r(x1)=r(x2) for distinct x1 and x2.

2.7 Secondary Characteristics (Post-Processing)

Many features commonly associated with queries are not included in this basic query paradigm. Such features typically operate on the whole collection cr to do such things as count, sort, remove duplicates, or extract an element. These are treated in our descriptive model as general operations on collections, not necessarily unique to queries. In effect, they do "post-processing" on the query result.

For example, to model DISTINCT, we can define MakeSet as a function in the descriptive model which takes a collection as argument and returns a set. For any collection c, its behavior is defined as

MakeSet(c)(x) = [c(x)>0],

i.e.,

Occurs(x,MakeSet(c)) = [Occurs(x,c)>0].

A thing x will occur once in the set returned by MakeSet(c) if it occurs at least once in c, since the expression Occurs(x,c)>0 will then have the value 1.

With this definition, a target query of the form

SELECT DISTINCT r(x) FROM d x WHERE w(x)

can be expressed in the descriptive model as

MakeSet(SELECT r(x) FROM d x WHERE w(x)).

Such post-processing could be composite, e.g., to sort the results after removing duplicates.

Some post-processing operations yield something other than a collection. Operations which return the cardinality or extract an element fall into this category. Queries which include this kind of post-processing can be treated simply as expressions which return whatever the post-processing expression yields.

Post-processing operations like sorting or duplicate removal yield another collection cp. The profile of cp depends on the specific post-processing operations. For sorting, cp(z)=cr(z), since the cardinality of the contents is unchanged. For duplicate elimination, cp(z)=[cr(z)>0]. These may be composed over intermediate collections if, for example, duplicates are eliminated before or after sorting.

3 APPLICATIONS

3.1 Group-By as a Composition of Queries

Group-by can be described in terms of the facilities described above, still in model-independent fashion. This exercise suggests that it might also be possible to define other interesting query facilities in model-independent fashion.

Group-by essentially works in three stages. First there is a simple (inner) query. Then its results are partitioned into groups by a GROUP-BY clause. Finally, another query iterates over this collection of groups, with the HAVING clause serving as the WHERE clause for this second (outer) query.

We first extend the descriptive model with a Group operator which takes as arguments an unevaluated grouping expression g(x) and a collection c, returning a collection cg=Group(g(x),c). The Group operator partitions c into equivalence classes based on equal values of g. The collection cg is the collection of these equivalence classes (which we call groups), i.e., cg is a collection of collections. The Group operator also confers values of g onto the groups themselves, as will be described below.

A query with Group-by has the form

SELECT r(u) FROM d x WHERE w(x) GROUP-BY g(x) u HAVING h(u)

which is equivalent to

SELECT r(u)
FROM Group( g(x), [SELECT x FROM d x WHERE w(x)] ) u
WHERE h(u).

In effect, we start with an inner query

Qi ::= SELECT x FROM d x WHERE w(x).

Then we use Group as a post-processing operator to partition the result into a collection of groups

do ::= Group(g(x),Qi)
::= Group(g(x), [SELECT x FROM d x WHERE w(x)])

and then use this as the search domain for an outer query (using the variable u for the outer query to iterate over the groups)

Qo ::= SELECT r(u) FROM do u WHERE h(u)
::= SELECT r(u) FROM Group(g(x), [SELECT x FROM d x WHERE w(x)]) u WHERE h(u).

The HAVING clause provides the WHERE clause for the outer query Qo, whose search domain do is a collection of groups.

Let's continue to use cd, cw, and cr to label the collections for the inner query Qi as before. The corresponding collections for the outer query Qo will be labeled cdo, cwo, and cro. We have:

3.2 Role of MIQP in Language/Model Specifications and Standards

Query models have historically been associated with data models, which in turn are often reflected in data sublanguages embedded in host languages. The result is a chaotic overlap of specifications for query, data models, data sublanguages, and host languages. In the long run it would be useful to partition language features into orthogonally defined components which can then be used in various combinations. The present paper is an attempt to start by isolating query semantics from other features.

Although a full orthogonalization of language features is far beyond the scope of the present paper, we can suggest a plausible distinction between data model and computational features. General computational features include such aspects as the underlying computational paradigm (e.g., expression evaluation, resolution, or something else), composition of expressions, overloading, coercion, binding and scope of variables, recursion, synchronization, exceptions, special forms, flow control, etc.

Data-related features involve operations which construct, access, and determine equality of data things. These can be partitioned according to the kind of data involved. Thus there are operations for arithmetic, logic, string manipulation, data aggregates, etc.

Data models are essentially concerned with aggregate data structures, involving operations which construct them, access them, and determine their equality. These again can be partitioned according to the type of aggregate, e.g., lists, relations, arrays, various notions of "object", etc.

Some interesting issues arise in such partitioning. Union and difference of relations might not be an inherent part of the relational model: a relation is a relation whether or not the language supports a difference operator. The same with elementary data types: the semantics of relations aren't inherently different if they can or can't have dates or floating point numbers in them ("...a query language should treat data values as essentially uninterpreted objects" [1]).

In any case, however, specification of a query operator can be separated from specification of other language features.

Standards can certainly be orthogonally defined in this fashion. The core behavior of query can be standardized once in a generic way, in a manner applicable to a large variety of languages and models. Multiple standards can be defined for different sorts of data constructs, with each of these combined with the basic query standard. Multiple standards can also be defined for different sorts of computational expressiveness, which can again be combined with the other standards to arrive at the semantic component of a specific language standard. After that's been done, then one or more syntactic forms for expressing such semantics can be standardized.

MIQP illustrates a core query model whose semantics are independent of any particular data model or computational facilities. It defines the semantic behavior of queries in neutral terms, relying only on arithmetic. This level of specification can be adopted, agreed to, standardized by all languages/models claiming to support query. Further refinements can then be superimposed by standardizing details of data model and computational facilities. In the query form

SELECT r(x) FROM d x WHERE w(x),

separately standardized data model operations for constructing collections can be plugged into the specification of d for defining the search domain and also into the result generator r. Standardized data model operations for accessing collections can be plugged into all of the expressions. Similarly, general computational features can also be plugged into all of the expressions.

Such separation can organize the description of an orthogonally designed language, or it can organize the "complete" description of a separately defined query capability. For example, consider the expression d for specifying the search domain cd. In an orthogonally designed language, there would be a separate general specification of collection-valued expressions, with a simple statement that these may be used to define the search domain d. In the other case, there would be a special-case description of what sorts of expressions could be used to specify the search domain. The specification would not apply to collection-valued expressions usable elsewhere in the language.

We mention a few more examples of such orthogonality:

• Logical expressions

  Logical (Boolean-valued) expressions typically occur in the filter expression w of a query, but they can also occur elsewhere, e.g., in if-then and while statements. The definition and behavior of the components of such logical expressions can be defined separately, including such things as treatment of comparisons, negation, nulls, etc. The only requirement is that the overall expression w(x) return a counter (or Boolean) value for each x in cd. How it does so does not affect inherent query semantics.

• Composition queries

  Such things as nested queries or unions of queries should not require special definition, if queries are treated the same as any other collection-valued expression.

• Object-oriented queries

  What might make a query object oriented?

  • If search domains are types or classes or sets (as appropriate to the particular object model).
  • If the contents of search domains are objects.
  • If the query results are objects and/or contain objects.
  • If the expressions being evaluated involve operations on objects.
  • If the expressions allow user-defined operations, not limited to fixed operators of a computational language.
  • If expression evaluation involves inheritance, and resolution of overloaded operators.

  Those are all secondary characteristics, layered on top of the fundamental query paradigm. Different object models may have different capabilities and semantics for aggregate constructors and accessors. The query paradigm described here can accommodate any of them, hence is adaptable to various object models. The query paradigm will be standardized to the extent that such aggregate constructors and accessors are standardized.

  Even identity of result objects is an orthogonal issue. Query is just one possible collection-valued operation. Others might include union (concatenation), intersection, difference, construction (e.g., {x,y} or [x,x]), and evaluation of collection-valued or set-valued functions like Children(Sam). The question of whether query execution creates new objects depends on whether execution of any of those operations creates a new object.

3.3 Analysis of Query Behaviors

MIQP can help analyze and define the behavior of difficult queries. This involves two stages:

1. Express the query in terms of the MIQP descriptive model. This step itself often exposes and clarifies significant semantic issues.
2. Establish the arithmetic behavior of the query components.

We illustrate this in terms of queries involving multi-valued attributes, disjunction, and duplicates

Suppose Sam has two-year-old twins Ed and Al, and three-year-old triplets Ted, Hal, and Sue.

The question "Which parents have a child named Ed or a child named Ted?" illustrates a profound difference between functional and relational semantics. In functional terms, we think of Sam as having a set of five children, and we include Sam in the answer - once - because he has children satisfying the selection criterion.

In tuple-oriented first-normal-form semantics, we don't think of Sam's children. We think of a set of parent-child pairs. The question is applied to each such pair, extracting the parent from the pair if the child is named Ed or Ted. Sam would thus show up in the answer twice (assuming duplicates are not removed).

This distinction shows up in the syntax, which in this case turns out to be more than sugaring. The relational form of the query would include terms of the form "Person.Child=Ed" and "Person.Child=Ted" (we're eliding the quotes around people's names). It is often claimed that the dot notation Person.Child is semantically equivalent to the functional notation Child(Person). This does not work for multi-valued attributes. If Child(Sam) was a function invocation, it would have one fixed value so long as there were no updates. Child(Sam)=Ed and Child(Sam)=Ted could not simultaneously be true unless Ed and Ted were the same thing.

If we introduce Children(Sam) as a function having a set of children as its value, then a term of the form "Children(Sam)=Ed" still makes little sense. Ed is not a set, and hence can't equal the value of Children(Sam). One expedient would be to reinterpret x=y - when one is a set and the other isn't - to be true if the non-set thing belongs to the set thing. But this approach raises further complications when we go beyond first normal form: how should we interpret x=y when one is a set and the other is a set of sets? A much cleaner approach is to provide a distinct operator x IN y to be true when x is an instance of y.

Due to first normal form, the Children function could not be modeled as a base relation whose extension is stored in terms of argument-result pairs. It can only be modeled as a query which returns a set of things based on a Parent-Child predicate which can be modeled as a base relation. The relationship between Sam and his child Ed can only be modeled as a pair (tuple) which is a thing x in its own right, such that Parent(x)=Sam and Child(x)=Ed. Note the odd construction here: Sam now appears to be the parent of a tuple rather than the parent of a child.

Clearly, due to syntactic idiosyncrasies within and among languages, the first essential step in analyzing a query is to express the query in an equivalent MIQP form. This in itself could be controversial, forcing clarification of aspects of the query's semantics.

Thus it could make a difference whether the query is expressed as

Q1: SELECT x
WHERE Ed IN Children(x) OR Ted IN Children(x);

or as

Q2: SELECT Parent(x)
WHERE Ed=Child(x) OR Ted=Child(x);

The unwritten FROM clause is quite significant. The first query iterates over people, the second over tuples.

The overall semantics depends both on how the query is expressed and on how the arithmetic of OR is defined. If the expression "x OR y" is defined to return 0 if x and y are both zero and 1 otherwise, then Q1 returns Sam once while Q2 returns him twice (there is one parent x satisfying the first WHERE clause, while there are two tuples x satisfying the second). On the other hand, both queries return the same result if we define "x OR y" simply as x+y (the filter expression in the first query would have the value 2).

Things get messier with duplicates. Suppose we wanted to know which parents have a two-year-old child or a three-year old child. Depending on how we define various things, we might get Sam back once, twice, three times, or five times. Consider the queries

Q3: SELECT x
WHERE 2 IN ChildrenAges(x) OR 3 IN ChildrenAges(x);

Q4: SELECT Parent(x)
WHERE 2=ChildAge(x) OR 3=ChildAge(x);

In the relational (tuple-oriented) query Q4, we are now dealing with tuples containing a parent, a child, and the age of this child. The function ChildrenAges(x) returns the bag of ages of the children of x. It can be defined in functional form as

ChildrenAges(x) ::= SELECT Age(y) WHERE y IN Children(x);

or in tuple-oriented form as

ChildrenAges(x) ::= SELECT ChildAge(y) WHERE x=Parent(y);

In either case, ChildrenAges(Sam)=[2,2,3,3,3].

Before analyzing queries Q3 and Q4, we should observe that x IN y could be defined to return 1 if x occurs in y and 0 otherwise, or it could return the number of times that x occurs in y. Furthermore, the possible definitions of "x OR y" need to be expanded to deal with x>1 or y>1. In such cases, OR might be defined as their sum, their maximum, or possibly something else.

Based on such alternatives, the reader should be able to discover cases in which the queries Q3 and Q4 will return Sam one, two, three, or five times, and perhaps in other numbers as well.

Similar anomalies arise with conjunction. In a tuple calculus, it's hard to express the question "Which parents have a child named Ed and a child named Ted?". We essentially have to formulate it in terms of a cross-product of two copies of the original relation, so that we can seek one tuple in which Ed and Ted both occur.

Things are again messier with duplicates. Consider the question "Which parents have a two-year-old child and a three-year-old child?" If we form the cross-product as before, we actually wind up with six tuples in which Sam has a two-year-old child and a three-year-old child. Do we really want to see Sam six times in the answer? How would we rationalize that semantically?

What's the answer? How should these operators behave? MIQP does not answer such questions. MIQP frames the questions, and requires language and model definers to provide the answers. Once the questions are answered, MIQP clearly defines the semantics of the queries. Definers might choose to specify a particular behavior for operators like OR, AND, and IN, or they might choose to replace them with families of operators, each having a different behavior. Thus there might be two flavors of IN, one returning 0 or 1, the other returning the number of occurrences.

3.4 Defining Relational Operators

3.4.1 Project

Let c be a relation (collection of tuples), and let x[i] denote the component of tuple x corresponding to attribute i. Let i1...in be any sequence of attributes (allowing repetition). The projection

cp = pi [i1...in]c

yields a collection cp of tuples of the form y=<x[i1...x[in]> whose membership profile is

cp(y) = SUM[x][c(x) * y[1]=x[i1] * ... * y[n]=x[in] ].

3.4.2 Select (Restrict)

Selection is easy to characterize in terms of a selection expression S(x) which yields a Boolean number. The selection

cs = sigma [S(x)]c

yields a relation cs with the same attributes as c whose membership profile cs(x) is

cs(x) = c(x) * S(x).

3.4.3 Joins

Let x1 and x2 range over tuples in relations c1 and c2, respectively, and let p(x1,x2) be an arbitrary join predicate.

Let INJ denote the inner join of c1 and c2. Its profile is given by

INJ(z) = (z=<x1,x2>) * p(x1,x2) * c1(x1) * c2(x2).

If z=<x1,x2>, and if p(x1,x2) is true, then the number of occurrences of z in INJ is the product of the number of times x1 occurs in c1 and x2 occurs in c2. Otherwise, z does not occur in INJ.

For outer joins, we first define "appendages" R and L relative to c1 and c2. Ø denotes null.

R(z) = (z=<x1,Ø>) * c1(x1)>0 * 0=SUM[x2][p(x1,x2) * c2(x2)].
L(z) = (z=<Ø,x2>) * c2(x2)>0 * 0=SUM[x1][p(x1,x2) * c1(x1)].

For R, if:

• z=<x1,Ø>, and
• x1 occurs in c1 at least once, and
• there are zero elements x2 occurring in c2 for which p(x1,x2) is true,

then z will occur once in R. Otherwise z will not occur. Similar analysis applies to L.

Let ROJ, LOJ, and SOJ denote the right, left, and symmetric outer joins of c1 and c2. These are respectively defined as the concatenation of INJ with R, with L, and with both. Concatenation is expressed as simple addition. Hence

ROJ(z) = INJ(z) + R(z),
LOJ(z) = INJ(z) + L(z),
SOJ(z) = INJ(z) + R(z) + L(z).

3.4 Query Transformations

The correctness of query transformations can be proved via arithmetic analysis. Such analysis might also lead to the discovery of new transformations. To illustrate, we prove the correctness of the familiar transformation involving projection and selection.

Consider the projection

cp = pi [i1...in]c

The k-th element of a tuple y occurring in cp is given by y[k], and is equal to x[ik] for some x in c. If we then select from cp using a selection criterion on this k-th element, we have

cps = sigma [S(y[k])]cp = sigma [S(y[k])]pi [i1...in]c,

where S(y[k]) signifies a selection on y[k]. We are thus selecting on the k-th component of a projection. The membership profile of cp is

cp(y) = SUM[x][c(x) * y[1]=x[i1] * ... * y[n]=x[in] ].

The membership profile of cps is

cps(y) = cp(y) * S(y[k])
= [ SUM[x][ c(x) * y[1]=x[i1] * ... * y[n]=x[in] ] ] * S(y[k]).

Now let's reverse the order of the operations. Since y[k]=x[ik], we have S(y[k])=S(x[ik]), and an equivalent selection on c takes the form

cs = sigma [S(x[ik])]c.

Since cs has the same attributes as c, we can still write the projection as

csp = pi [i1...in]cs = pi [i1...in]sigma [S(x[ik])]c.

The membership profile of cs is

cs(x) = c(x) * S(x[ik]).

The membership profile of csp is

csp(y) = SUM[x]( cs(x) * y[1]=x[i1] * ... * y[n]=x[in] )
= SUM[x]( c(x) * S(x[ik]) * y[1]=x[i1] * ... * y[n]=x[in] ).

If we simply rearrange terms, and substitute S(y[k])=S(x[ik]), we see that

cps(y) = S(y[k]) * [ SUM[x]( c(x) * y[1]=x[i1] * ... * y[n]=x[in] ) ],

csp(y) = SUM[x]( S(y[k]) * c(x) * y[1]=x[i1] * ... * y[n]=x[in] ).

3.6 Query Testing and Validation

4 CONCLUSIONS

Language features can be grouped into data model, computation, and basic query. The categories do overlap: query and data model operations are part of the computational power, and queries make use of the data model and computational features. In an orthogonally designed language these features can be described separately; in other languages queries can be described as a special-case combination of the three aspects.

In any case, the external behavioral semantics of queries can be described arithmetically, regardless of the data model, by means of formulas for calculating the contents of collections produced by queries. Basic formulas describe basic semantics for any model. Relevant aspects of the data model and computational features can then also be expressed arithmetically to describe their effect on queries.

This paradigm inverts the traditional explanation process. Rather than trying to explain query semantics by describing what an underlying execution algorithm (implementation) yields, this paradigm sets an independent criterion which the execution algorithm is obliged to satisfy. This paradigm rises above the tuple or domain calculus as a vehicle for defining query semantics.

In some ways, this paradigm represents a way of "passing the buck" on the problem of defining query semantics. Once the behaviors of the constituent expressions of the query form are well defined, the behavior of the query is well defined. Most issues in query semantics are really issues in the behavior of the constituent expressions. Thus a question about the behavior of a query may be sidestepped by rephrasing it as a question about the behavior of one of the expressions. This refocuses attention on the appropriate aspect of the target language/model. The behavior of the query is well defined, once those other aspects of the language/model are defined.

Of course, the paradigm itself needs further testing and refinement. An open question: if we couldn't figure out how to express the behavior of a certain query in MIQP, should we then conclude that MIQP is deficient, or that the semantics of the query are ill-defined?

In any case, the following seems to be a natural approach to query standards:

5 ACKNOWLEDGMENTS

6 REFERENCES

7 ADDENDA

8 TYPES AND SIGNATURES

It would be useful to characterize the types and signatures of the collections and expressions involved in the query paradigm. We first need to extend the descriptive model with some relatively neutral type-related concepts and terms, sufficient to characterize the behavior of queries. These are used for descriptive purposes only, and don't have to be supported in the target model being described.

There is a set of things called "types". A thing x has an associated set of types given by Types(x). To say that "x has type t" or "x is of type t" or "x is an instance of t" means t IN Types(x), also written Types(x) CONTAINS t. We have x IN Instances(t) <=> Types(x) CONTAINS t. We sometimes write x IN t to mean x IN Instances(t). If t2 is a supertype of t1 then x IN t1=>x IN t2. To say that a variable has a type means that it may only be bound to instances of that type.

There is a type called Type. Types(x) CONTAINS t => Types(t) CONTAINS Type. We also assume that Bag is a type.

[At this point we switch terminology, using "bag" for "collection". In the context of a type system, it seems more natural to call the types Bag and BagType, rather than Collection and CollectionType. However, we do not imply that the collections are necessarily unordered.]

A type constructor is a function which returns a type. Type constructors can generally return an infinite set of possible types, hence the set of types is infinite. The type returned by a type constructor may be called a "constructed type". BagType is a particular type constructor, which takes one type as an argument. To say that x has type BagType(t) means that x is an instance of T, where T is the type returned by BagType(t). If a thing x has BagType(t) as its type, it means that x is a bag and each thing occurring in x has type t. Thus

Types(x) CONTAINS BagType(t) <=> x IN Bag AND [x(y)>0 => y IN t].

Bag is a supertype of BagType(t) for any type t. If there is a type T which is the supertype of all other types, then Bag is equivalent to BagType(T).

Set is a subtype of Bag. x IN Set => x(y)=<1. The type constructor SetType can be defined as

Types(x) CONTAINS SetType(t) <=> x IN Set AND [x(y)>0 => y IN t].

BagType(t) is a supertype of SetType(t) for any type t.

An expression e has signature e:tx->ty, meaning that e(x)=y => x IN tx AND y IN ty. Expressions are total, i.e., x IN tx=>e(x) IN ty. In the following, wherever we require a signature e:tx->ty, we can accept a signature e:tz->ty if tz is a supertype of tx.

In the descriptive model, a variable is much like an expression with no arguments. A variable v of type t effectively has the signature v:->t, and the expression f(v) can be treated as a syntactic shorthand for f(v()).

Counter is a type whose instances are the non-negative integers.

Types and signatures in a query are as follows:

We we assume the members of the search domain cd are instances of some arbitrary type td. Hence cd has type BagType(td), and the variable x has type td.

cd->cw: The filter w has signature w:td->Counter.

The bag cw has the same type as cd, i.e., BagType(td).

cw->cr: The result expression r has signature r:td->tr, where tr is any type.

The bag cr has the type BagType(tr). If the result expression is just the variable x, then tr=td. (The latter is the case when there is grouping.) cr is the query result when there is no grouping.

cr->cdo: The Group operator has signature Group:expression, BagType(td)->SetType(BagType(td)).

The bag cdo has the type SetType(BagType(td)) [a subtype of BagType(BagType(td))].

cdo->cwo: The filter h has signature h:BagType(td)->Counter.

The bag cwo has the same type as cdo, except it might have duplicates: BagType(BagType(td)).

cwo->cro: The result expression ro has signature ro:BagType(td)->tro, where tro is any type.

The bag cro has the type BagType(tro). If the result expression is simply the variable u, then tro=two.

9 ORDERING

It would be nice to define the basic query paradigm in such a way that the query result preserves any ordering defined on the search domain. However, it seems difficult to define this in a canonical way, independent of specific data structures. There are too many possibilities. For example, without duplicates being injected by the filter w, we might wish:

• If xi is selected from cd, then in cr the successor of r(xi) should be r(xj), where xj is the first successor of xi which is also selected from cd.
• If xi is the i-th element of cd, then the i-th element of cr should be r(xi) if xi is selected, and null otherwise.
• cr should be sorted by the same ordering criterion as cd.

When w injects n>1 copies of x, we might additionally wish that

• The n copies occupy n distinct positions in the result.
• The n copies occupy one position, as a bag of n things.

10 MODEL-DEPENDENT REFINEMENTS AND ELABORATIONS

10.1 Aggregates

10.1.1 Search Domains

The search domain cd can take many useful forms. In relational queries, the search domain is a set of tuples, obtained as the (flattened) cross product of relations. In the OSQL style of object-oriented query [3][4], the search domain is a set of tuples obtained as the cross product of types.

Other more general forms are useful for query refinement. In a static form, the search domain is itself specified as a query. In a dynamic form, the search domain might simply be a variable holding the results of a previous query, perhaps modified. There are other uses as well for generalized expressions specifying the search domain.

10.1.2 Extensions of Types

Some query syntaxes allow the search domain to be specified as a type, so that

SELECT FROM T x WHERE ...

signifies

SELECT FROM Instances(T) x WHERE ...

10.1.3 Indexed Things

Queries in various models and languages often involve things like lists or tuples. Indexed things provide a generic way of describing such things in the descriptive model. An indexed thing x has an index set IndexSet(x). If i IN IndexSet(x), then Index(i,x) may return something, though it need not. If i NOT IN IndexSet(x), then Index(i,x) returns nothing, and might be treated as an error. The cardinality of the index set can be considered the length of the indexed thing. The index set might be an initial subset of the positive integers (or non-negative integers for 0-origin), making x a sequence or list. The elements of the index set might be called "attributes" or "accessors", making x a tuple. If the index set contains n-long sequences of integers, then the indexed thing is an n-dimensional array.

We use the notation x[i] for Index(i,x).

A generalized model of indexed thing construction is given by

x <- <i1:e1...in:en>,

which binds x to an indexed thing with index set i1...in such that x[ij]=ej. If omitted, the index set i1...in defaults to the integers 1...n, so that a sequence constructor takes the form

x <- <e1...en>.

This definition appears circular, since one has to provide the sequence constructor with a sequence of arguments. A non-circular definition arises by defining a sequence to be an operator which yields another sequence. Thus, if s is a sequence of length n, then s(e) returns a sequence of length n+1 whose n+1st element is the value of e. There is an empty sequence denoted <>. The expression <>(e1) returns a sequence of length 1, <>(e1)(e2) returns a sequence of length 2, and so on. The syntactic form <e1...en> is equivalent to <>(e1)...(en).

10.1.4 Regular Collections

The members of a regular collection all have the same finite index set, which then becomes a characteristic of the collection itself. (Though associated with the collection, it is only the index set for its members, not for the collection itself; c[i] is not meaningful.) A relation is a regular collection, usually subject to further restrictions as well.

If the search domain cd in a query is a regular collection having index set i...j (not necessarily integers), it is convenient to introduce variables xi...xj for referring to components of the members of cd, such that xi=x[i],...,xj=x[j]. So long as there is an understood ordering of the indexes (and there usually is, e.g., for relational tuples), then a query syntax of the form

SELECT FROM d xi...xj WHERE w(xi...xj)

associates the variable xk with the index k, being equivalent to

SELECT FROM d x WHERE w(xi...xj) AND xi=x[i] AND ... AND xj=x[j].

Since the collection cw obtains its members from cd, it will also be a regular collection characterized by the same index set.

For example, if cd is a collection of triplets (3-long sequences), then a query of the form

SELECT FROM d y,z,u WHERE w(y,z,u)

is equivalent to

SELECT FROM d x WHERE w(y,z,u) AND y=x[1] AND z=x[2] AND u=x[3].

10.1.5 Cross Products

The search domain cd might be defined by various sorts of constructors. Of particular interest is a cross product constructor Xprod(c1...cn) which constructs the cross product of a list of collections c1...cn. The result is a regular collection of sequences with index set 1...n. The result contains k occurrences of <x1,...,xn>, where k is the product of the number of occurrences of xi in ci:

Occurs(x,Xprod(c1...cn)) = Pi iOccurs(x[i],ci),

i.e.,

Xprod(c1...cn)(x) = Pi ici(x[i]).

The main reason behind this excursion is to consider a further special case, namely the construction of the search domain cd as the cross product of types. The syntactic form

SELECT FROM Ti xi ... Tj xj WHERE w(xi,...,xj)

can be described as a special notation for

SELECT FROM Xprod(Instances(Ti)...Instances(Tj)) x
WHERE w(xi,...,xj) AND xi=x[i] AND ... AND xj=x[j].

10.1.6 Type Constructors

10.1.7 Usage in Grouping

Grouping by more than one property can be achieved by describing the grouping expression g as a sequence of properties:

g(x) ::= <g1(x),...,gm(x)>,

effectively creating a "vector" of functions and corresponding values. For example, grouping by salary and age could be obtained by

SELECT FROM d x WHERE w(x) GROUP-BY <Salary(x),Age(x)> u HAVING h(u).

Each group ui would contain employees having the same salary and age. The Salary and Age functions would be implicitly overloaded on the groups ui, so that Salary(ui)=Salary(x) and Age(ui)=Age(x) for any x in ui.

To tie this back into the basic model, the overloading of the function gj on the groups ui can be described as

gj(ui) ::= g(ui)[j],

i.e., the j-th element of g(ui). In the present example, letting Salary be g1 and Age be g2, the grouping function g is effectively defined as

g(x) ::= <Salary(x),Age(x)>

so that g(ui)=<si,ai>, where Salary(x)=si and Age(x)=ai for any x in ui. Then Salary(ui) is g(ui)[1], i.e., the first element of g(ui), while Age(ui) is the second element.

10.1.8 Usage in Result Generation

If supported in the model, sequence constructors can be used in several ways in the SELECT clause to generate cr as a regular collection. If u is an element of c4, the result expression r can be specified as <r1(u)...rm(u)>, e.g.,

SELECT <Name(d), Manager(d)> FROM Departments d WHERE ...

If c4 is itself a regular collection (e.g., a collection of sequences or tuples), then projections or reorderings can be obtained by result expressions of the form <u[j]...u[i]>, or equivalently <uj...ui>, e.g.,

SELECT <p,d> FROM Departments d, Employees e, Projects p WHERE ...

These forms can be combined, as in

SELECT <Leader(p), Name(d)> FROM Departments d, Employees e, Projects p WHERE ...

10.2 Expressions

10.2.1 From Clause

In general, any collection-valued expression might be used to specify the search domain. It might be itself be a query, or a variable holding the results of a prior query, allowing various forms of query refinement. Any other expression, such as Children(Sam), could be used to bound the search domain.

10.2.2 Where Clause

The filter expression w(x) in queries can take many forms, with subexpressions involving all sorts of values and structures, but the overriding consideration is that w(x) as a whole must evaluate to a counter value or Boolean number for any x that may occur in the search domain.

As illustrated in earlier examples, logical predicates are modeled as returning 1 for true and 0 for false. In the absence of duplicates, conjunction (AND) is simple multiplication or maximum, disjunction (OR) is minimum, and negation is a simple unary operator which inverts 1 and 0. (For most queries, the search domain bounds the domain in such a way that negation becomes a relative complement.) Plausible arithmetic treatments of logical operators in the presence of duplicates are examined in [2],[7].

Three-valued logics for dealing with nulls may use some form of "unknown" as an intermediate result for subexpressions, but in the end there are only two choices: the thing is either selected or not. Hence the overall result must still be a Boolean value.

Nested queries (subqueries) are collection-valued expressions (unless post-processing yields something else). As such, they may only occur within other expressions which ultimately evaluate to counters or Booleans, such as Occurs(x,Q) or Q1=Q2 or NonEmpty(Q) or Count(Q), etc. Techniques for unnesting nested queries may provide useful computational algorithms, but they need not be used to define the semantics of the result.

Quantification can be defined as general operations on collections such that ForAll(c,e) and Exists(c,e) return 1 if e(x) is true for all or some elements x of c. (These may have to be treated as special forms taking e as a quoted expression.)

Duplicates arising from nested subqueries should be explainable in terms of a counter-valued subexpression of the form Occurs(z, SELECT ...) occurring within the WHERE clause.

Other computational features such as arbitrary functions, composition of functions, etc., are useful in queries, but do not inherently change the query semantics. The filter still has to evaluate to a counter or Boolean value.

10.2.3 Complex Grouping

10.2.4 Results

10.2.5 Logical Expressions (Predicates)

Logical expressions (predicates) occur in the in the WHERE and HAVING clauses of a query, but also in other language constructs as well, such as conditionals and iteration control. They might also occur in assignment statements to Boolean variables.

Thus the semantics of logical expressions needs to be defined in a larger context than queries. How they are defined does not affect the fundamental semantics of queries, so long as they always return a Boolean value for all possible arguments.

11 ORTHOGONALITY PRINCIPLES FOR LANGUAGE DESIGN, DESCRIPTION, AND STANDARDS

11.1 Language Components

Example

The search domain for an SQL query is a relation, or a cross-product of relations, which is again a relation. An orthogonal specification would simply say that:

1. The search domain for an SQL query is a relation.
2. The data model provides certain mechanisms for constructing relations, such as cross-product, select, union, difference, etc. Join is a combination of cross-product and select. There may also be other operations which return relations - such as queries.
3. An SQL query allows certain of those forms for specifying the search domain.

Whether or not an SQL query allows the search domain to be specified as the union of relations, or as another query, is a specific idiosyncrasy of the SQL language. It does not affect the inherent behavior of the query, nor does it affect the definition of the relational data model.

Example

Union of SQL SELECT statements isn't really a query issue. Each SELECT statement has its own well-defined behavior, yielding a relation.

Union of relations is an orthogonal language feature. It could even be argued that it is purely a computational aspect; relations are relations whether or not the language supports unions of them.

In any case, union of SELECT statements can be described simply as the union of relations, not as a unique characteristic of queries.

Example

DISTINCT isn't a particularly query-specific feature. The ability to remove duplicates, i.e., convert a bag into a set, is another feature common to many data models which can be applied to the results of a query.

Example

Elementary data types are not a query issue. It could be argued that they are not even a data model issue. A query is a query - and a relation is a relation - whether or not relations may contain floating point numbers, or dates.

Elementary data types seem to belong more to the general computational aspect of a language.

Example

The essential filtering behavior of query depends on the where-clause evaluating to true or false (or to a counter value for a more general bag query model) for each element of the search domain. Potentially any expression in the language which evaluates to a Boolean (or counter) value could serve as the where clause. These expressions could be composed of any operations supported in the language.

Similar things can be said about expressions involved in restructuring.

A basic set of operations is provided by the data model, defining how values in data constructs may be retrieved. Most other aspects of the expression

Thus, none of the following is specifically a query issue:

• Whether arbitrary or user-specified procedures can be invoked.
• Whether operations can be composed.
• Whether and how negation is supported; ultimately the expression has to evaluate to a Boolean (or counter) value.
• Ditto for nulls and three-valued logic.

The treatment of negation and nulls, for example, is a general characteristic of Boolean valued expressions, which might occur in queries, if-then, while, and other statements involving truth values.

Nested queries should be describable in the same way as any subexpression which returns a collection. Such things must ultimately be involved in operations which eventually contribute to Boolean-(or counter-)valued results, e.g., Count(Q), Max(Q), Occurs(x,Q), Q1=Q2, etc.

Example

11.2 A Framework For Specification and Standardization of Languages and Models

Listed below is a plausible framework of orthogonal components for the specification and standardization of languages and models. It's not particularly original, and some details may be arguable. Our main purpose is to illustrate how queries can be isolated as an orthogonal component.

• Semantics of general computational model

  Independent of specific operations or data constructs. Includes such characteristics as

  • Underlying computational paradigm, e.g., expression evaluation, resolution, or something else.
  • Degrees of operators (e.g., unary, binary, other).
  • Composition of expressions.
  • Order of evaluation of expressions.
  • Signatures, general type constraints.
  • Overloading, coercion.
  • Binding and scope of variables.
  • Recursion.
  • Synchronization.
  • Exceptions.
  • Special forms, flow control, etc.
  • Basic equality (identity) principles might also belong here.
• Elementary data items

  Types, constructors, accessors, equality.

• Aggregate data items

  Types, constructors, accessors, equality.

• Specific operators, e.g.,
  • Arithmetic
  • Logic
  • Character manipulation
  • Input/output
  • Resource and workflow management

    (It could be argued that some of those should be included under the heading for elementary data items. It doesn't matter.)

• General query semantics.

  (Could be included under specific operators.)

• Syntax.

11.3 Why This Framework?

If you're designing a whole language, this leads to a nice orthogonal design.

For partial language (e.g., a data sublanguage), this helps identify

• Constituents of the language, and to design them orthogonally.
• Areas of overlap with companion languages., e.g., host languages.

12 APPENDIX: CASE STUDIES

12.1 SQL FROM Clause

The FROM clause in SQL is based on the cross product of relations. If orthogonally designed, such a cross product would be a general language feature, allowing something like

x <- R1xR2.

Then the syntax

SELECT FROM R1, R2 WHERE...

12.2 Object-Oriented Query

What might make a query object oriented?

• If search domains are types.
• If the contents of search domains are objects.
• If the query results are objects.
• If the expressions being evaluated involve operations on objects.
• If the expressions allow user-defined operations, not limited to fixed operators of a computational language.
• If expression evaluation involved inheritance, and resolution of overloaded operators.

Those are all secondary characteristics, layered on top of the fundamental query paradigm. Different object models may have different capabilities and semantics for aggregate constructors and accessors. The query paradigm described here can accommodate any of them, hence is adaptable to various object models. The query paradigm will be standardized to the extent that such aggregate constructors and accessors are standardized.

Even identity of result objects is an orthogonal issue. Query is just one possible collection-valued operation. Others might include union (concatenation), intersection, difference, construction (e.g., {x,y} or [x,x]), evaluation of collection-valued or set-valued functions like Children(Sam). Does each execution of one of those create a new object?

One position...

Collections are extensional, their identity being determined by their contents: y and z refer to the same collection if and only if y(x)=z(x), i.e., Occurs(x,y) = Occurs(x,z), for all x.

Queries return references to collections without creating anything new, in the same way that arithmetic operations return references to existing numbers, not creating new ones. The effect of new objects can be obtained by assigned query results to be properties of distinct objects, e.g.,

Roster(x) := SELECT ...

Roster(y) := SELECT ...

12.3 Case Studies From Rafi

Consider the following relational schema:

S (s# *, name, gpa) /* student
C (c# *, cname, units, dept) /* course
E (c# *, s# *) /* enrollment

Q1. Find names of students who are enrolled in all courses.

In SQL:

SELECT name FROM S WHERE NOT EXISTS (
SELECT * FROM C WHERE NOT EXISTS (
SELECT * FROM E WHERE E.s# = S.s# AND E.c# = C.c#));

In canonical MIQP form:

Q1(): SELECT name(s) FROM S s WHERE NOT EXISTS (
Q1a(s): SELECT c FROM C c WHERE NOT EXISTS (
Q1b(s,c): SELECT e FROM E e WHERE s#(e)=s#(s) AND c#(e)=c#(c) ));

Observe: EXISTS Q ::= 0<Card(Q), and NOT EXISTS Q ::= 0=Card(Q).

Working from the inside out:

/* Q1b(s,c) selects all the enrollments for a given student s and course c */

Q1b(s,c): SELECT e FROM E e WHERE s#(e)=s#(s) AND c#(e)=c#(c); /* the sub-query */

Q1b(s,c)(e) = E(e) * [s#(e)=s#(s)] * [c#(e)=c#(c)]; /* the profile of the sub-query */

Card(Q1b(s,c)) = SUM[e] (E(e) * [s#(e)=s#(s)] * [c#(e)=c#(c)]); /* the cardinality of the sub-query */

/* Q1a(s) selects all the courses c such that for a given student s the number of enrollments of s in c is 0 */

Q1a(s): SELECT c FROM C c WHERE NOT EXISTS Q1b(s,c); /* the sub-query */

Q1a(s)(c) = C(c) * [0=Card(Q1b(s,c))] /* the profile of the sub-query */
= C(c) * [0=SUM[e] (E(e) * [s#(e)=s#(s)] * [c#(e)=c#(c)])];

Card(Q1a(s)) = SUM[c] (C(c) * 0=Card(Q1b(s,c))) /* the cardinality of the sub-query *
= SUM[c] (C(c) * [0=SUM[e] (E(e) * [s#(e)=s#(s)] * [c#(e)=c#(c)])]);

/* Q1() selects the name of a student s if the number of courses in which s has 0 enrollments is 0 */

Q1(): SELECT name(s) FROM S s WHERE NOT EXISTS Q1a(s);/* the query */

Q1()(n) = SUM[s] (S(s) * [0=Card(Q1a(s))] * n=name(s)) /* the profile of the query */
= SUM[s] (S(s) * [0=SUM[c] (C(c) * [0=SUM[e] (E(e) * [s#(e)=s#(s)] * [c#(e)=c#(c)])])] * n=name(s))

/* that profile counts all students having the same name; the result could have duplicate names */

Q2. Get s# of students who are enrolled in at least one course being taken by at least one student who is enrolled in at least one course offered by physics department.

In SQL:

SELECT UNIQUE s# FROM E WHERE c# IN (
SELECT c# FROM E WHERE s# IN (
SELECT s# FROM E WHERE c# IN (
SELECT c# FROM C WHERE dept = "Physics")));

In canonical MIQP form:

Q2: MakeSet (
Q2a: SELECT s#(e1) FROM E e1 WHERE c#(e1) IN (
Q2b: SELECT c#(e2) FROM E e2 WHERE s#(e2) IN (
Q2c: SELECT s#(e3) FROM E e3 WHERE c#(e3) IN (
Q2d: SELECT c#(c) FROM C c WHERE dept(c) = "Physics")))));

Observe: x IN Q ::= 0<Q(x).

Working from the inside out:

/* Q2d() selects the c#'s of all the courses in the Physics department */

Q2d(): SELECT c#(c) FROM C c WHERE dept(c) = "Physics"; /* the sub-query */

Q2d()(c2d) = SUM[c](C(c) * [dept(c)="Physics"] * [c2d=c#(c)]); /* the profile of the sub-query */
/* that profile counts all the courses having the same number */

/* Q2c() selects the s#'s of students involved in enrollments in courses in the Physics department, i.e., all students enrolled in courses in the Physics department*/

Q2c(): SELECT s#(e3) FROM E e3 WHERE c#(e3) IN Q2d(); /* the sub-query */

Q2c()(s2c) = SUM[e3] (E(e3) * [0<Q2d()(c#(e3))] * [s2c=s#(e3)]) /* the profile of the sub-query */
= SUM[e3] (E(e3) * [0<SUM[c](C(c) * [dept(c)="Physics"] * [c#(e3)=c#(c)])] * [s2c=s#(e3)]);

/* Q2b() selects the c#'s of all the courses involved in enrollments involving students involved in enrollments in courses in the Physics department, i.e., all courses taken by students enrolled in courses in the Physics department*/

Q2b(): SELECT c#(e2) FROM E e2 WHERE s#(e2) IN Q2c(); /* the sub-query */

Q2b()(c2b) = SUM[e2](E(e2) * [0<Q2c()(s#(e2))] * [c2b=c#(e2)]) /* the profile of the sub-query */
= SUM[e2] (E(e2) * 0<SUM[e3] (E(e3) * 0<SUM[c](C(c) * [dept(c)="Physics"] * [c#(e3)=c#(c)]) * [s#(e2)=s#(e3)]) * [c2b=c#(e2)]);

/* Q2a() selects the s#'s of students involved in enrollments involving courses returned by query Q2b() */

Q2a(): SELECT s#(e1) FROM E e1 WHERE c#(e1) IN Q2b(); /* the sub-query */

Q2a()(s2a) = SUM[e1] (E(e1) * [0<Q2b()(c#(e1))] * [s2a=s#(e2)]); /* the profile of the sub-query */
= SUM[e1] (E(e1) * 0<SUM[e2] (E(e2) * 0<SUM[e3] (E(e3) * 0<SUM[c](C(c) * [dept(c)="Physics]" * [c#(e3)=c#(c)]) * [s#(e2)=s#(e3)]) * [c#(e1)=c#(e2)]) * [s2a=s#(e2)]);

/* Q2() eliminates duplicates from Q2a() */

Q2(): MakeSet(Q2a()); /* the query*/

Q2()(x) = 0<Q2a(x); /* the profile of the query */
= 0<SUM[e1] (E(e1) * 0<SUM[e2] (E(e2) * 0<SUM[e3] (E(e3) * 0<SUM[c](C(c) * [dept(c)="Physics"] * [c#(e3)=c#(c)]) * [s#(e2)=s#(e3)]) * [c#(e1)=c#(e2)]) * [x=s#(e2)]);

Q3. Find name of students enrolled in courses not being taken by students whose gpa's are lower than 3.0.

In SQL:

SELECT name FROM S, E WHERE S.s# = E.s# AND E.c# NOT IN (
SELECT E.c# FROM S, E WHERE S.s# = E.s# AND S.gpa < 3.0);

In canonical MIQP form:

Q3(): SELECT name(s1) FROM XProd(S, E) <s1,e1> WHERE s#(s1)=s#(e1) and c#(e1) NOT IN (
Q3a: SELECT c#(e2) FROM XProd(S, E) <s2,e2> WHERE s#(s2)=s#(e2) AND gpa(s2) < 3.0);

Observe: XProd(X,Y)(<x,y>) ::= X(x)*Y(y) (the number of occurrences of <x,y> in the cross product of X and Y is the product of the occurrences of x in X and y in Y). This can also be expressed as

XProd(X,Y)(x) ::= X(x[1])*Y(x[2]).

Thus:

/* Q3a() selects c#'s of courses involved in enrollments involving students who have gpa<3.0 */

Q3a(): SELECT c#(e2) FROM XProd(S, E) <s2,e2> WHERE s#(s2)=s#(e2) AND gpa(s2) < 3.0); /* the sub-query */

Q3a()(cn) = SUM[<s2,e2>](S(s2)*E(e2) * [s#(s2)=s#(e2)] * [gpa(s2) < 3.0] * [cn=c#(e2)] ); /* profile of the sub-query */

/* Q3() selects names of students enrolled in courses not returned by Q3a() */

Q3(): SELECT name(s1) FROM XProd(S, E) <s1,e1> WHERE s#(s1)=s#(e1) and c#(e1) NOT IN Q3a() */

Q3(n) = SUM[<s1,e1>](S(s1)*E(e1) * [s#(s1)=s#(e1)] * [0=Q3a()(c#(e1)] * [n=name(s1)] )
= SUM[<s1,e1>](S(s1)*E(e1) * [s#(s1)=s#(e1)] * [0=SUM[<s2,e2>](S(s2) * E(e2) * [s#(s2)=s#(e2)] * [gpa(s2) < 3.0] * [c#(e1)=c#(e2)] )] * [n=name(s1)]

);

12.4 Case Studies From Ganski & Wong

From G&W 3.1 [5]:

Query KQ1:

SELECT Ri.Ck FROM Ri,Rj WHERE Ri.Ch=Rj.Cm;

In MIQP:

SELECT Ck(xi) FROM XProd(Ri,Rj) <xi,xj> WHERE Ch(xi)=Cm(xj);

KQ1()(x) = SUM[<xi,xj>][Ri(xi)*Rj(xj) * Ch(xi)=Cm(xj) * x=Ck(xi)];

Query KQ2:

SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS IN (SELECT Rj.Cm FROM Rj);

In MIQP:

KQ2(): SELECT Ck(xi) FROM Ri xi WHERE Ch(xi) IN
KQ2a: SELECT Cm(xj) FROM Rj(xj);

KQ2a()(y) = SUM[xj](Rj(xj) * [y=Cm(xj)]);

KQ2()(x) = SUM[xi](Ri(xi) * [0<KQ2a()(Ch(xi))] * [x=Ck(xi)])
= SUM[xi](Ri(xi) * [0<SUM[xj](Rj(xj) * [Ch(xi)=Cm(xj)])] * [x=Ck(xi)]);

Compare:

KQ1()(x) = SUM[<xi,xj>](Ri(xi)*Rj(xj) * [Ch(xi)=Cm(xj)] * [x=Ck(xi)]);

KQ2()(x) = SUM[xi](Ri(xi) * [0<SUM[xj](Rj(xj) * [Ch(xi)=Cm(xj)])] * [x=Ck(xi)]);

Suppose there is just one pair <xi,xj>, with Ri(xi)=1, Rj(xj)=2, Ch(xi)=Cm(xj), x=Ck(xi). Then:

KQ1()(x) = SUM[<xi,xj>](1*2 * 1 * 1) = 2;

KQ2()(x) = SUM[xi](1 * [0<SUM[xj](2 * 1)] * 1) = 1;

Hence the two queries are not equivalent if Rj contains duplicates. There may be other cases as well.

Note that this analysis was done without any reference to join techniques.

From G&W 3.2:

Query KQ3:

SELECT Ri.Ck FROM Ri WHERE Ri.Ch = (
SELECT Agg(Rj.Cm) FROM Rj WHERE Rj.Cn=Ri.Cp);

In MIQP:

KQ3(): SELECT Ck(xi) FROM Ri xi WHERE Ch(xi) = Agg(
KQ3a(xi): SELECT Cm(xj) FROM Rj xj WHERE Cn(xj)=Cp(xi));

KQ3a(xi): SELECT Cm(xj) FROM Rj xj WHERE Cn(xj)=Cp(xi);

KQ3a(xi)(x) = SUM[xj](Rj(xj) * [Cn(xj)=Cp(xi)] * [x=Cm(xj)]);

KQ3(): SELECT Ck(xi) FROM Ri xi WHERE Ch(xi)=Agg(KQ3a(xi));

KQ3()(y) = SUM[xi](Ri(xi) * [Ch(xi)=Agg(KQ3a(xi))] * [y=Ck(xi)]);

[What do we need to know about the behavior of Agg?]

Query KQ4:

SELECT Ri.Ck FROM Ri WHERE Ri.Ch = (
SELECT Rt.C2 FROM Rt WHERE Rt.C1=Ri.Cp);

Rt(C1,C2) = (SELECT Rj.Cn, Agg(Rj.Cm) FROM Rj GROUP BY Rj.Cn);

13 ADDED 3/12/93

13.1 Negation

The negation of p(x) is given by the expression p(x)=0.

13.2 Conditionals

If f(x) then g(x) else h(x)

can be expressed as

(f(x)¬=0)*g(x)+(f(x)=0)*h(x).

13.3 Quantification

EXISTS x IN X p(x) can be expressed as [SUM[x] IN Xp(x)]>0. This is computable when X is finite.

13.4 Function Composition

PUT THIS WITH AN EARLIER DEFINITION OF IN : If f is not bag- or set-valued, we can take y IN f(x) to be 1 when y=f(x) and 0 otherwise, considering this case to be isomorphic with {y}=f(x). Hence we use y IN f(x) as the general case. [We don't deal with g being bag-valued. Should we?]

y IN f(g(x)) is equivalent to EXISTS z IN Z|z=g(x) AND y IN f(z). Here Z is the intersection of the result type of g and the argument type of f. For function composition, these would normally all be the same.

Arithmetically, this becomes

[y IN f(g(x))] = [SUM[z IN Z](z=g(x))*(y IN f(z))]>0.

13.5 Recursion

Recursion in general should be manageable in terms of recursive arithmetic functions. A simple form arises when Q(x) has the form

Q(x) = if f(x) then g(x) else Q(h(x)),

where f, g, and h are not recursive. The arithmetic form of if-then yields

Q(x) = (f(x)¬=0)*g(x) + (f(x)=0)*Q(h(x)).

This is computable for any x such that h*(x)=0.

Expanding the composed functions yields

[TO BE REVISED] Q(x) = (f(x)¬=0)*g(x) + (f(x)=0)*Q(h(x)).

Let's try the good old ancestor problem. First let's explore a very simple form in which Parent is a single-valued function:

Ancestors(y) = {Parent(y)} UNION Ancestors(Parent(y)).

(This doesn't even involve a query!)

The corresponding profile might be given by [CAN THIS BE FORMALIZED, NOT JUST INTUITED?]

A(y)(x) = x IN {Parent(y)} + A(y)(Parent(x))

A(y)(x) = (x=Parent(y)) + SUM[z IN Person][(z=Parent(x))*A(y)(z)].

TO BE CONTINUED!!!