Select OPTIONS select-list
   From table-list
   {Where predicate}
   {Group By attribute-list {Having predicate}}
   {Order By attribute-list}

   {Merged | Distinct}
   {Flatten | GroupAlts(attribute-list)}
   {NoConf | NoMaybe}
   {NoLineage}

What follows is an informal description of logical query evaluation beginning with the From, stepping through the Where and Group-By clauses, creating the result tuples, and applying the OPTIONS. This description is informal and not a complete syntactic or semantic specification. Further details (although still not a complete formal specificaiton) are supplied in the remainder of the document.

The following query finds (possible) sightings that involve Toyotas:

   Select * From Saw Where car = 'Toyota'

The following query finds the colors of (possibly) sighted Mazdas and Toyotas:

   Select color From Saw Where car = 'Mazda' or car = 'Toyota'

   Select Merged color From Saw Where car = 'Mazda' or car = 'Toyota'

   Select S.witness, D.person as suspect, D.color, D.car
   From Drives D, Saw S
   Where D.color = S.color and D.car = S.car

• Lineage details for interested readers: Lineage reflects the derivations just described, but at the finer granularity of alternatives. (Here the term "alternative" denotes a complete tuple comprised of the certain attributes together with one choice of alternative values for the uncertain attributes.) For example, the lineage of (Diane,Frank,blue,Toyota) in the second tuple of the result is specifically the second alternative of Drives tuple 1 and the second alternative of Saw tuple 4. The lineage of (Amy,Frank,red,Toyota) in the result (the first tuple) is the first alternative of Drives tuple 1 and the second alternative of Saw tuple 1. Notice that these two tuples cannot coexist in a possible instance of the result, since they require disjoint alternatives of Drives tuple 1. Lineage encodes these types of constraints "behind the scenes", so that query results always capture the correct possible-instances semantics.

Running the same query but omitting the witness returns:

   Select color, car From Drives
   Where (color,car) Not In (Select color, car From Saw)

   Select Distinct color, car from Saw

   Select Merged color, Count(*) as #sightings
   From Saw
   Group By color

In general, grouping and aggregation can be very expensive -- just the result data (never mind its computation or lineage) can be exponential in the size of the input data. Thus, TriQL also includes more efficient variants for the aggregate functions. Specifically, for each of the five standard SQL aggregation functions -- Count, Min, Max, Aum, and Avg -- TriQL includes three variants: low, high, and expected.

If the full result of an aggregation in a TriQL query (without horizontal merging) is the set of possible values {A1, A2, ..., An}, then the corresponding low aggregate is the least value in the set, the corresponding high aggregate is the greatest value in the set, and the corresponding expected aggregate is the "expected value" of the set in a probabilistic sense: the average of the values, weighted by confidences if present.

For example, suppose we modify our "sightings by car color" query to:

   Select color, Lcount(*) as low, Hcount(*) as high, Ecount(*) as exp
   From Saw
   Group By color

With five standard aggregate functions and four possibilities for each, TriQL offers 20 built-in aggregate functions as shown in the following table. (Currently, TriQL does not include the Distinct versions of the aggregate functions, e.g., "Select Count(Distinct witness)..." is not included. Equivalent queries can be written -- albeit less conveniently -- using extra subqueries and standard aggregation.)

As a simple example, the following query finds cars (without colors) that appear in both Saw and Drives.

   (Select car from Saw) Intersect (Select car from Drives)

1. Only certain attributes may be specified in the Order-By clause.
2. A special "attribute" Confidences may be included in the list, to indicate ordering by the total confidence value in each result tuple.

   Select S.witness, D.person as suspect, D.color, D.car
   From Drives D, Saw S
   Where D.color = S.color and D.car = S.car
   Order By S.witness

   Select Flatten * From Saw

Subqueries enclosed in [] instead of the usual () are "horizontal": they refer to the set of alternatives in each tuple being evaluated. Horizontal subqueries can be used in the Where and Select clauses. Enclosing a subquery in "[]" signals that instead of evaluating the subquery over the entire database, it should instead be evaluated over the set of alternatives comprising the "current tuple" being processed by the Where or Select clause. Thus, the From list in a horizontal subquery must only include tables in the From list of the outer query.

The following query finds all sighting tuples with at least two alternatives involving Toyotas:

   Select * From Saw
   Where 2 <= [Select Count(*) From Saw Where car = 'Toyota']

The next example finds all Saw tuples for which no car appears in more than one alternative, returning witnesses and cars.

   Select witness, car From Saw
   Where 1 =All [Select Count(*) From Saw Group By car]

Although horizontal subqueries refer to all the alternatives of the "current tuple", the Where predicate is still evaluated on one alternative at a time, and each alternative may contribute to the result. For example, suppose we modify our first query to select the car attribute only:

   Select car From Saw
   Where 2 <= [Select Count(*) From Saw Where car = 'Toyota']

In the examples so far, predicates on horizontal subqueries have been true for all alternatives of a tuple or for none of them. However, once horizontal subquery results are compared to attributes, or horizontal subqueries have correlated references, this property no longer holds. For example, the following query returns only those alternatives whose color is lexicographically <= to all other colors in its tuple:

   Select * From Saw
   Where color <=All [Select color From Saw]

   Select * From Saw S1
   Where Exists [Select * From Saw S2
                 Where S1.car = S2.car and S1.color <> S2.color]

Next consider horizontal subqueries when the outer query involves more than one table. The following query joins Drives and Saw to generate a set of suspects, as in the original join example, but now it keeps only those result tuples where at least one alternative mentions Johnny or Diane.

   Select S.witness, D.person as suspect, D.color, D.car
   From Drives D, Saw S
   Where D.color = S.color and D.car = S.car
   And Exists [Select * From Drives, Saw
               Where suspect = 'Johnny' Or witness = 'Diane']

   (Exists [Select * From Drives Where suspect = 'Johnny'] Or
    Exists [Select * From Saw Where witness = 'Diane'])

Shortcut 1: Implicit table-list

where the table-list in the expanded version implicitly lists all tables in the outer query. ("{}" encloses optional clauses, and note that the "Select" keyword is also dropped in this shortcut.)

"Value-producing" case

  Select Merged witness, [Count(Distinct color)] as #colors
  From Saw

Similarly, the following query associates with every Toyota alternative the number of non-Toyota alternatives in its tuple:

   Select witness, color, car,
          [Count(*) as #nonToyota Where car <> 'Toyota']
   From Saw
   Where car = 'Toyota'

"Tuples-producing" case

In the two previous examples the horizontal subquery always produces a single value, so the usual SQL (TriQL) semantics for the Select clause can be followed. If the horizontal subquery in a Select clause may produce a tuple or set of tuples, then it must be the only component of the Select clause, and the tuples produced by the horizontal subquery become the alternatives of the result tuple.

As an example, the following query returns the number of alternatives for each car-color combination in the tuples resulting from joining Drives and Saw.

   Select [Select D.color, D.car, Count(*) as #alts
           From Drives D, Saw S
           Where D.color = S.color and D.car = S.car
           Group By D.color, D.car]
   From Drives, Saw

A syntactic subtlety occurs with horizontal subqueries when the outer query includes two or more occurrences of a single table (i.e., self-joins). Tables in the From clause of a horizontal subquery correspond to tables in the outer query by table name. However, if a horizontal subquery includes table T, and table T occurs more than once in the From clause of the outer query, then the inner reference is ambiguous. This ambiguity is resolved by defining that the nth reference to a table T in the From clause of a horizontal subquery corresponds to the nth reference to T in the outer query's From clause.

As an example, suppose we perform a self-join on two instances of Saw to find pairs of witnesses who saw the same type of car:

   Select S1.witness as witness1, S2.witness as witness2,
          S1.car, S1.color as color1, S2.color as color2
   From Saw S1, Saw S2
   Where S1.car = S2.car And S1.witness < S2.witness

Now suppose we only want to keep those tuples where in at least one of the alternatives, the colors of the two sighted cars are the same. We write this query as:

   Select S1.car, S1.witness as witness1, S1.color as color1,
          S2.witness as witness2, S2.color as color2
   From Saw S1, Saw S2
   Where S1.car = S2.car And S1.witness < S2.witness
   And Exists [Select * from Saw S3, Saw S4 Where S3.color = S4.color]

Neither of the syntactic shortcuts described above can be used in horizontal subqueries when the outer query has self-joins. For both shortcuts, ambiguity would be guaranteed in any query that used them.

   Select S.witness, D.person as suspect, D.color, D.car
   From Drives D, Saw S
   Where D.color = S.color and D.car = S.car
   And Conf(D) > 0.3 And Conf(S) > 0.3

Queries may also filter tuples based on whether they include ?'s. With confidences, a query could determine if a tuple in a table T has a "?" by checking "[Select Sum(Conf(T)) From T] < 1". However, without confidences -- or simply for convenience -- a special built-in function Maybe() can be used. Maybe() takes a table name or variable from the From clause as a parameter, and it returns true if and only if the "current alternative" being evaluated from that table comes from a tuple with a "?". For example, the following query generates suspects based only on data from non-maybe tuples:

   Select S.witness, D.person as suspect, D.color, D.car
   From Drives D, Saw S
   Where D.color = S.color and D.car = S.car
   And (Not Maybe(D)) And (Not Maybe(S))

• When a result alternative maps directly to a single alternative in a table being queried, frequently the original confidence value carries over directly to the result.
• When horizontal duplicates are merged, by default the confidence values of the alternatives are summed.
• When a query joins multiple tables all having confidence values, the confidence on a result tuple alternative is usually the product of the confidences on the alternatives from which the result alternative was produced, unless there is an underlying dependency among some alternatives. (If any tables in a join are without confidences, then the result is also without confidences, unless confidence values are generated explicitly using "as conf", described below.)

• Result confidence details for interested readers: In the formal model for ULDBs with confidences, each possible instance has a probability based on the confidences of the data in that instance. (The model guarantees that these probabilities sum to 1.) When a query result is computed, lineage effectively ties the possible result instances to the possible instances of the queried data. Thus, each result alternative has a confidence value that captures the fraction of possible instances in which its lineage appears. In most cases this confidence value is a simple function of the confidence values in the immediate lineage, as in the examples above. However, the computation becomes more complicated when lineage includes both conjunction and disjunction, and when multiple levels of lineage create confidence values that may not be independent.

A query can override the default result confidence values by assigning values in its Select clause to the reserved attribute name conf. Suppose in the join example with confidences above, instead of multiplying to get result confidences, the lesser of the two confidences on the contributing alternatives should propagate to the result. The query is:

   Select S.witness, D.person as suspect, D.color, D.car,
          smaller(Conf(D),Conf(S)) as conf
   From Drives D, Saw S
   Where D.color = S.color and D.car = S.car
   And Conf(D) > 0.3 And Conf(S) > 0.3

   Select witness, color, car, rel/[sum(rel)] as conf
   From (Select witness, color, car,
                (Select reliability From ColorRel
                 Where color = Saw.color) as rel
         From Saw)

The subquery in the From clause adds a reliability measure to each alternative in Saw based on its color. In the Select clause, rel refers to the value in the "current alternative", while [sum(rel}] sums all rel values in the current tuple. The result of the From subquery on the sample data is:

Confidence values may be computed via a user-defined plug-in function. Suppose for the sake of illusration that a user-defined function ToyotaConf takes as parameters an input confidence and a color, and adjusts the confidence in some fashion based on the color. Consider the query:

   Select witness, color, car, ToyotaConf(Conf(Saw),color) as conf
   From Saw
   Where car = 'Toyota'

   Select Merged car, 0.1 as conf From Drives

The special keyword uniform used with "as conf" assigns confidence values to a tuple as follows:

• If the tuple has n alternatives and no "?", assign confidence 1/n to each alternative.
• If the tuple has n alternatives and a "?", assign confidence 1/(n+1) to each alternative.

• If the tuple has no confidence values and n alternatives, assign confidence 1/n to each alternative.
• If the tuple has confidence values that sum to s, assign confidence value c/s to each alternative, where c is the existing confidence value for that alternative.

As an example of uniform, consider the following simple query:

   Select *, uniform as conf From Saw

The keyword uniform can also precede a table name in the From clause of a query. The following two are equivalent:

   From ..., uniform T, ...
   From ..., (Select *, uniform as conf From T) as T, ...

As an example of scaled, consider the following simple query:

   Select *, scaled as conf From Saw

   scaled as conf
   Conf(*)/[Sum(Conf(*))] as conf

Adding "compute confidences" to the end of a query causes result confidences to be computed as part of query execution, instead of on-demand. For example:

     Select S.witness, D.person as suspect, D.color, D.car
     From Drives D, Saw S
     Where D.color = S.color and D.car = S.car
     Compute Confidences

   Create Table Suspects as
     Select S.witness, D.person as suspect, S.color, S.car Into Suspects
     From Drives D, Saw S
     Where D.color = S.color and D.car = S.car

   Create Table NMSuspects as
     Select Suspects.* Into NMSuspects
     From Suspects, Drives, Saw
     Where Lineage(Suspects,Drives) And Lineage(Suspects,Saw)
     And (Not Maybe(Drives)) And (Not Maybe(Saw))

   Select *
   From Suspects
   Where Not Exists (Select * from Drives
                     Where Lineage(Suspects,Drives) And Maybe(Drives))
   And Not Exists (Select * from Saw
                   Where Lineage(Suspects,Saw) And Maybe(Saw))

   Select *
   From NMSuspects
   Where 2 <=All (Select [Count(*)] from Drives
                  Where Lineage(NMSuspects,Drives))
   And  2 <=All (Select [Count(*)] from Saw
                 Where Lineage(NMSuspects,Saw))

The NoLineage option says that lineage should not be retained for any data in the query result. In general omitting lineage improves efficiency (both time and space) at the expense of eliminating the possibility of querying or examining the derivation of result data. However, omitting lineage can have semantic ramifications in some cases. Recall the join query producing suspects:

The NoConf option is very simple: it omits confidence values from the query result. The NoMaybe option similarly omits ?'s from the query result. NoMaybe automatically omits confidence values as well, since confidence values can implicitly generate ?'s. As an example, the earlier query generating suspects based on high-confidence data only can be rewritten to drop the ?'s, and therefore also drop the confidence values:

   Select NoMaybe S.witness, D.person as suspect, D.color, D.car
   From Drives D, Saw S
   Where D.color = S.color and D.car = S.car
   And Conf(D) > 0.3 And Conf(S) > 0.3

   Insert Into table-name Values (tuple-spec)
   Insert Into table-name subquery

   Insert Into Saw Values ('Mary', [('black','Acura'):0.7 | ('purple','Mazda'):0.2])
   Insert Into Drives Values ([('Hank','black','Acura') | ('Hank','purple','Mazda')])?

The syntax for Delete is the same as SQL, except for an added option "AdjConf":

   Delete {AdjConf} From table-name
   {Where predicate}

If all alternative values for a given tuple are deleted, then the tuple is removed entirely from the table. Consider a tuple where some but not all alternative values are deleted. Then:

• If the table has confidences, by default the confidence values of the deleted alternatives move implicitly to "?". If option AdjConf is specified, instead the deleted confidence values are added proportionately to the remaining alternatives.

• If the table is without confidences, then by default a "?" is added to the tuple if one was not there already. If option AdjConf is specified, "?" is not added.

   Delete From Saw Where car = 'Toyota'

Now consider the original Drives table without confidences:

   Delete From Drives Where color = 'blue'

The basic Update statement is the same as in SQL:

   Update table-name
   Set attr-list = expression-list
   {Where predicate}

As in Select and Delete statements, the predicate can be any SQL predicate, possibly including regular or horizontal subqueries, and TriQL built-in functions and predicates Conf(), Maybe(), and Lineage(). Each attribute in the attr-list is updated with the result of the corresponding expression on the right-hand side of the =, just as in SQL. The expression can be composed from attributes, constants, and regular or horizontal subqueries that always produce single-value results. In the special case where the updated attribute is "conf", the alternatives' confidence values are updated.

In general both certain and uncertain attributes may be updated, however updating certain attributes incurs some restrictions on the Update statement. Specifically, the corresponding expression on the right-hand-side of the =, and the query's Where predicate, must produce the same value across all alternatives in each tuple. (Otherwise whether or not to update the certain attribute, and what its new value is, can be ambiguous.) This requirement can be enforced syntactically by ensuring that every reference to an uncertain attribute, Conf(), or Lineage() occurs within a horizontal subquery.