Subject: Benchmark initiative

From: [email-masked] (Alexander Tuzhilin)
Date: Tue, 16 Mar 93 14:40:27 EST

We would like to make two comments on the proposal to develop a
comprehensive set of natural language queries as a test of "goodness"
of various query languages and algebras.

First, we feel that a certain classification of various queries has to
be established before the set of queries is proposed.  As an *initial*
suggestion, we can classify temporal queries as follows.

		 | HISTORICAL 	| ROLLBACK  | BITEMPORAL
--------------------------------------------------------
UNGROUPED	 |		|	    |
		 |		|	    |
GROUPED		 |		|	    |
		 |		|	    |
TEMP. AGGREGATES |		|	    |
		 |		|	    |
SCHEMA VERSIONING|		|	    |
		 |		|	    |
OTHER FEATURES	 |		|	    |
--------------------------------------------------------

Then we can place one or several queries in each cell of this matrix.

We want to stress that this is only an *initial* proposal to classify
various temporal queries which should be elaborated further.  Perhaps,
the two-dimensional matrix is not sufficient.  Perhaps, this matrix
should be reorganized as a three-dimensional cube
(historical/rollback/bitemporal is one dimension, grouped/ungrouped
another, and temporal aggregates and schema versioning the third).
Perhaps, it can be an n-dimensional cube.

The second comment is that the development of the benchmark should not
be a substitute for a rigorous *theoretical* study of expressive
powers of various temporal query languages and algebras.  It is not
entirely clear what the goal of the benchmark is.  What seems
necessary is a kind of typography of temporal data models as suggested
by the above table and discussion.  For example, one data model can be
grouped bitemporal, another be ungrouped historical with aggregates.
Perhaps, the benchmark can be useful in developing such a typography.
Each type of data model should support a class of queries the model
embodies and should have its own standard of completeness.  We believe
that this standard should be developed in the terms of an appropriate
logic (as in the classical relational case) rather than trying to
determine expressive power "by consensus" (we would not want to say
that one language is more expressive than another if it can express
95% of the benchmark queries and the other one only 87%).

We addressed this issue in our paper "On Completeness of Historical
Relational Query Languages" (Working Paper IS-91-41 from Stern School
of Business, NYU; also to appear in TODS) where we proposed a measure
of completeness of various query languages.  We introduced and
disussed the semantic difference between grouped and ungrouped data
models and explained the difference between queries on grouped and
ungrouped temporal data models. For the ungrouped temporal data
models (e.g. TQuel), we proposed to use either temporal logic, or
first-order logic with explicit references to time, or the temporal
algebra TA (proposed in the paper "A Temporal Relational Algebra as a
Basis for Temporal Relational Completeness" (Tuzhilin & Clifford,
VLDB'90)), all of which have the same expressive power for the
discrete linear models of time, as a basis for the ungrouped temporal
completeness.  For the grouped models (e.g. Gadia, Tansel, HRDM), we
proposed to use the calculus L_h that we defined in that paper.  We
also examined completeness of various temporal query languages and
algebras proposed in the literature.

We invite comments and discussion of these issues from the temporal
database community.

Jim Clifford
Al Croker
Alex Tuzhilin

---

From: "Christian S. Jensen" <[email-masked]>
Date: Tue, 16 Mar 1993 23:39:48 +0100

Jim, Al, and Alex,

I hope you all survived the worst snow storm in 100 years :-)

Thanks for your interest in the TSQL Benchmark. I have read your
posting to the tsql list with great interest. I agree with your
observations, and I thank you for taking the time to communicate them.

Let me now attempt to address your concerns within the context of the
benchmark effort. Some of your concerns can be met now, and the rest
may need to await a later edition of the benchmark.

>From [email-masked] Tue Mar 16 20:42:45 1993
>

In the initial proposal for a database schema for the benchmark (sent
to tsql a few days ago), I included this characterization (based on
Rick's postings to the tsql list).

"The central goal of this document is to provide the temporal database
community with a {\em comprehensive consensus benchmark} for temporal
query languages which is {\em independent} of any existing language
proposal.

This is not a performance benchmark, but a {\em semantic} benchmark
which is intended to be an aid in evaluating the user-friendliness of
proposals for temporal query languages. Thus, temporal query languages
should ideally be able to express the benchmark queries both
conveniently and naturally."

To me, the key word is user-friendliness. The benchmark is intended to
be a valuable tool for designers of user-level query languages in
general and of a TSQL language, in particular. The benchmark is not
intended to cover algebras which are not user-level languages. Using
the benchmark, a designer may become aware of boolean seams (Shashi
has shown the importance of avoiding these), of violations of the
0-1-infinity principle, of lack of orthogonality, of other types of
inconsistencies (see the PL literature), etc.

>		 | HISTORICAL 	| ROLLBACK  | BITEMPORAL

I think you are exactly right that a classification (or taxonomy) is
needed before queries should be proposed. That was what I tried to
indicate in the introductory statement of the schema proposal and in
the plan that accompanied the schema proposal.

"% The purpose of the following draft is then to define a taxonomy to
% be used for categorizing the benchmark queries that will follow."

"Three tasks must be accomplished initially.

Task 1: Agree on a database schema.
Task 2: Agree on an instance of the schema.
Task 3: Agree on a suitable taxonomy for the benchmark queries.

These tasks will be addressed sequentially during the next weeks. When
they are completed, the benchmark will be populated with queries."

I think your taxonomy is very helpful. It is very much a top-down
taxonomy that makes it possible to classify a very wide variety of
queries.

In order for the current version of the benchmark to not become too
big (I would not like it to exceed, say, 100 queries), Rick suggested
a restricted scope. Thus, only valid time is addressed, and aggregates
as well as schema versioning are presently not addressed. As a
result, most queries in the initial benchmark will fall into only a
couple of categories, making additional refinement desirable.

I will request the help of you, Shashi, Ed, Patrick, Fabio, Maria,
Paolo, and Abdullah (among others) when Task 3 is addressed. Grouping
will certainly be an important aspect of this taxonomy and of the
queries themselves, and I hope that you will be able to help ensure
that it is present.

>grouped bitemporal, another be ungrouped historical with aggregates.

I will emphasize in the introduction of the schema proposal document
that the benchmark is not intended to be such a substitute. 

The current formulation is:

"While the benchmark is not intended to constitute a metric for query
language completeness, ..."

I will change the formulation to this:

"The benchmark is {\em not} intended to constitute a metric for query
language completeness, and as such it is not a substitute for a
rigorous {\em theoretical} study of expressive powers of various
temporal query languages."

Making a stronger and more explicit point out of this is very
appropriate. I hoped that the introduction would have explained what
was the goal of the benchmark. I will gratefully accept additional
clarifications, to be added to the document.

>95% of the benchmark queries and the other one only 87%).

This is again an important point! I have seen papers argue that one
algebra is better than another algebra because the former satisfies
more criteria (from the Comp Surveys paper by Rick and Ed M) than the
latter. That is very unfortunate. Similarly, we must try to avoid this
use of the benchmark. For now, I'll add the following text to the
introduction. This text may have to be refined later on.

"It it emphasized that using the benchmark as an advanced,
quantitative scoring system for comparing languages makes little
sense. Thus, one language is not necesarily superior to another just
because one is capable of expressing more benchmark queries than the
other. Rather, the focus is on user-friendliness."

Best regards,
Christian