Subject: TSQL Benchmark document (Latex).

From: "Christian S. Jensen" <[email-masked]>
Date: Tue, 11 May 1993 01:12:15 +0200

%\documentstyle[twocolumn]{article}
\documentstyle[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This paper is intended to evolve into the first version of the TSQL
% benchmark. For this version of the benchmark, this document contains
% the final database (schema and instance) and taxonomy of queries.
%
% To complete the benchmark, benchmark queries must be added (Task 4
% of the TSQL Benchmark Initiative).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% VARIOUS MACROS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\long\def\comment#1{}

\comment{For twocolumn style:
\setlength{\textheight}{8.85in}%8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.0in}%{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}}

\addtolength{\textwidth}{1.485in}%{1.2in}
\setlength{\oddsidemargin}{.1in}%{.3in}
\setlength{\evensidemargin}{.1in}%{.3in}
\addtolength{\topmargin}{-.85in} %{-1.35in}
\addtolength{\textheight}{1.8in} %{2.8in}

\newenvironment{BNF}{\vspace{-\partopsep}\addtolength{\baselineskip}{+4pt}
\samepage\begin{tabbing}
%\quad
\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=\ \ \ \ \=
\+\kill}{\end{tabbing}\vspace{-\partopsep}\vspace{-\topsep}\vspace{-\parsep}}

% => in roman
\def\arrow{\char'75\char'76\relax}
% ::= in roman
\def\is{{\rm \verb.:.\verb.:.\char'75\relax}}
% { in roman
\def\lbr{$\bigl\{$}
% } in roman
\def\rbr{$\bigr\}\;$}
% }* in roman
\def\starbr{$\bigl\}${\rm *}$\;$}
% }? in roman
\def\quesbr{$\bigr\}{}^?$}
% }+ in roman
\def\plusbr{$\bigr\}{}^+$}
% | in roman
\def\vbar{$\bigl|\;$}
% 'chars 
\def\qt#1{`{#1}'}
% nonterminals (arg is the name)
\def\nt#1{$<${\rm #1}$>$}
%typerwriter font
\def\ttt#1{{\tt #1}}
%comment
\def\com#1{{\tt /$\ast$} {\footnotesize #1}}

%double square brackets
\def\dsl{{\tt [\hspace{-4.5pt}[ \hspace{-1pt}}}
\def\dsr{{\tt ]\hspace{-4.5pt}]}}
\def\dsrs{{\tt ]\hspace{-4.5pt}]\hspace{4pt}}}

\newenvironment{prog} { \begin{center} \begin{minipage}{3in}
\begin{tabbing} nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=\kill
}{\end{tabbing} \end{minipage} \end{center}}

\newcommand{\mvd}{\mbox{$\rightarrow \!\!\! \rightarrow \;$}}
\newcommand{\autsp}{$\;\;\;$}

\long\def\query#1#2#3{\begin{verse} {\bf Query \no} {#1} \end{verse} \begin{verse} {\bf Answer:} {#2} \end{verse} \begin{verse} {\bf Category:} {#3} \end{verse}}

\newcounter{qnumber}
\newcounter{rnumber}[subsection]
\newcounter{gnumber}[subsubsection]
\newcommand{\no}{\setcounter{qnumber}{\value{subsection}} \setcounter{rnumber}{\value{subsubsection}}\protect\refstepcounter{gnumber} Q \protect\theqnumber.\protect\thernumber.\protect\thegnumber:}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PAPER START
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{\Large\bf The TSQL Benchmark \\ DRAFT}

\author{James Clifford \autsp Shashi K.~Gadia \autsp Fabio Grandi
  \autsp Christian S.~Jensen \\ Patrick Kalua \autsp Sunil Nair \autsp
  Edward Robertson \autsp John F.~Roddick \\ Maria Rita Scalas \autsp
  Richard T.~Snodgrass \autsp Abdullah Tansel \autsp Paolo Tiberio \\ 
  Alexander Tuzhilin \autsp Gene Wuu}

%Note that the list of authors is preliminary and may not be accurate!

\date{May 8, 1993} 
\maketitle

\section{Introduction}

\subsection{Goal}

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

This is not a performance benchmark, but is rather a {\em semantic}
benchmark 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 obtain a consensus benchmark, researchers in temporal databases
have been invited to participate in this initiative, and each researcher
that has contributed significantly will be a coauthor. The electronic
mail distribution {\tt [email-masked]} is used as the medium for
discussing the benchmark and related issues.

As a consequence of the central goal above, no existing temporal data
models are used or mentioned. The relation schemas of the benchmark
are expressed as sets of attributes, including one attribute
illustrating user-defined time. However, the underlying temporal
aspects are implicit (of course, specific temporal data models might
add explicit temporal attributes). The contents of the relations are
described in natural language. The benchmark queries are also given
only in natural language.

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. Comprehensiveness of the benchmark is
desirable only to ensure that all aspects of query language design are
covered.

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

\subsection{Scope}

Within certain boundaries, discussed next, the benchmark is intended
to contain all queries that appear reasonable and that are consistent
with the schema and data of the benchmark.

First, the benchmark is of a semantic nature---in its current form, it
is not aimed at performance comparisons. The intention is to provide a
foundation for comparing the descriptive and operational
characteristics and capabilities of temporal query languages, not
their performance characteristics. Properly extended with additional
relation schemas and a variety of large instances, the benchmark can
also be used for performance comparisons.

Second, a number of restrictions are imposed on which types of queries
are admissible in this version of the benchmark, including the
following.

\begin{itemize}
\item Queries are restricted to valid time only. Transaction-time
  related queries are not explored.

\item Schema evolution and versioning are not considered.

\item Incompleteness is not considered. 

\item Recursive queries are not included.

\item General temporal reasoning is beyond the scope of this version
  of the benchmark.

\item Queries involving aggregation facilities are not considered.

\item Only queries are included---updates are not considered.

\item Continuous attributes such as time are not included.

\item The querying of data valid in the future is not explored.

\comment{
\item Queries involving relations with multivalued dependencies (in
  the snapshot sense) are not explored.}

\comment{
\item User-defined time, including the interaction between
  user-defined time and valid time, is not considered.}

\comment{
\item Queries involving complex data retrieval are excluded.}

\comment{
\item Inheritance at both the schema and data levels is not
  considered.}

\comment{
\item Nested queries are not included.}

\comment{
\item For simplicity, each relation is used only once in each query.}

\end{itemize}

These advanced aspects are excluded solely for pragmatic reasons, and
the exclusion is not meant to imply in any way that the aspects are
not important. The restrictions simply represent an attempt to reduce
the size of the initial benchmark to manageable proportions.

It is emphasized that this benchmark is merely the first in a sequence
of ever-more comprehensive benchmarks. Later benchmarks will relax the
above restrictions on the scope of comprehensiveness imposed on this
benchmark. Specifically, the next version of the benchmark is intended
to include queries that involve aggregation.

\comment{
Specifically, the next version of the benchmark is intended to include
queries that use the same relation more than once, utilize
aggregation, and involve both valid time and user-defined time.}

\section{The Benchmark Database Schema}

\subsection{Criteria}

A suitable database schema for the benchmark should satisfy four
criteria.

\begin{itemize}
\item{} The schema should be natural. That is, it should correspond to
  a reasonable, though possibly greatly simplified, segment of the
  real world. This both reduces the need to explain the model and
  enhances the ability to recognize verball pitfalls in the path to
  the query instances.

\item{} The schema should be simple. This will aid in making the
  benchmark easy to understand. This criterion restricts the number of
  relation schemas and the number of attributes of the individual
  schemas. Additionally, the names of the relations and of the
  attributes should be short, as they will be referenced repeatedly.

  When an extension is proposed, the benefits should be carefully
  compared with the added complexity.

\item{} The schema should allow for comprehensiveness within the
  chosen scope. Using the schema, it should be possible formulate
  queries of all the types that appear reasonable.

  This indicates a need for at least two related relation schemas (for
  natural join queries).

\item{} A schema that has already been used frequently is preferred
  over a new schema. This guarantees that many existing queries can be
  adapted easily to the benchmark.

\item{} For clarity, schema and attribute names must start with
  capital letters.
\end{itemize}

\subsection{The Schema}

The database schema consists of three valid-time relation schemas,
{\tt Emp}, {\tt Skills}, and {\tt Dept}. They are defined as follows.

Relation {\tt Emp} uses the attributes {\tt Name}, {\tt Salary}, and
{\tt Dept} for recording the salaries of employees and the departments
where they work. In addition, it contains attributes {\tt Gender} and
{\tt D-birth} which indicate the gender and date of birth of an
employee. While the salary and department of an employee varies over
time, both {\tt Gender} and {\tt D-birth} are time-invariant.

Relation {\tt Skills} records the association of employees with skills
via the two attributes {\tt Name} and {\tt Skill}. The skills of an
employee may vary over time. For example, employees are considered to
have the skill ``driving'' only during those interval(s) when they
hold valid licenses.

Relation {\tt Dept} records the association of employees, as managers,
with departments, and it contains three attributes, {\tt Department},
recording a department name, {\tt Manager}, recording the manager of
the department, and {\tt Budget}, recording the budget of the
department.

Attributes {\tt Name}, {\tt Dept}, {\tt Department}, {\tt Skill}, and
{\tt Manager} are of type {\tt textString}; attribute {\tt Gender} is
one of {\tt F} (female) and {\tt M} (male); {\tt Salary} and {\tt
  Budget} are of type {\tt integer}; and {\tt D-birth} is a
user-defined time value which may be compared with valid times.

The relation schemas obey the following {\em snapshot} functional
and multivalued dependencies:

\begin{prog}
For {\tt Emp}: \\
\> {\tt Name} $\rightarrow$ {\tt Salary} \\
\> {\tt Name} $\rightarrow$ {\tt Dept} \\
\> {\tt Name} $\rightarrow$ {\tt Gender} \\
\> {\tt Name} $\rightarrow$ {\tt D-birth} \\
For {\tt Skills}: \\
\> {\tt Name} $\mvd$ {\tt Skill} (and {\tt Name} $\not\rightarrow$
{\tt Skills}) \\
For {\tt Dept}: \\
\> {\tt Department} $\rightarrow$ {\tt Manager} \\
\> {\tt Manager} $\rightarrow$ {\tt Department} \\
\> {\tt Department} $\rightarrow$ {\tt Budget}
\end{prog}

Note that {\tt Name} is the primary key of {\tt Emp} (it is the only
candidate key). For {\tt Skills}, there is no non-trivial key. For
{\tt Dept}, each of {\tt Department} and {\tt Manager} is a candidate
key, and {\tt Department} is selected as the primark key.

Each of the relation schemas are in snapshot Boyce-Codd normal form.

It is emphasized that the notion of key does not capture
correspondence between attribute values and the real-world objects
they represent. As one consequence, it is possible in this schema,
e.g., for a person to change {\tt Name} attribute value over time.

The attribute {\tt Manager} of {\tt Dept} is a foreign key for the
attribute {\tt Name} of {\tt Emp}. Thus, a tuple is allowed to exist
in the {\tt Dept} relation only if, for each non-empty snapshots of
this tuple, the {\tt Manager} attribute value exists as a {\tt Name}
value of some tuple in the simultaneous snapshot of the {\tt Emp}
relation.

\section{The Benchmark Data}

\subsection{Criteria}

\begin{itemize}
\item{} For clarity, the database instance should ideally accord with
  {\em all and only} those constraints which are explicitly stated in
  the definition of the database schema. 

\item{} For simplicity and ease of typing, attribute values should be
  short and salary values should be multiples of \$10,000.

\item{} Transitions (i.e., timestamp values) occur only at the
  beginning of the month, and all dates should be in the time interval
  from 1/1/81 to 12/31/88 (because the digits 8 and 9 are relatively
  hard to distinguish). Time intervals are all specified by the
  inclusive starting and ending events. Also for clarity, relation
  instance names should start with lowercase letters.

\item{} The data should include a ``hole in the history'' of some
  entity. For example, the database may be designed to contain a whole
  in the employment of some employee.

\item{} The data should include asynchronous behavior of attributes.
  For example, the department and salary of employees may change
  independently.
\end{itemize}

\subsection{The Proposed Data}

Three instances, {\tt emp}, {\tt skills}, and {\tt dept}, are defined
over the {\tt Emp}, {\tt Skills}, and {\tt Dept} relation schemas,
respectively. The contents of these instances is described below.

There are two employees, identified by {\em ED\/} and {\em DI\/} in
the following.

{\em ED\/} worked in the Toy department from 2/1/82 to 1/31/87, and in
the Book department from 4/1/87 to the present. His name was Ed from
2/1/82 to 12/31/87, and Edward from 1/1/88 to the present. His salary
was \$20K from 2/1/82 to 5/31/82, then \$30K from 6/1/82 to 1/31/85,
then \$40K from 2/1/85 to 1/31/87 and 4/1/87 to the present. {\em
  ED\/} is male and was born on 7/1/55. Several skills are recorded
for {\em ED\/}. He has been qualified for typing since 4/1/82 and
qualified for filing since 1/1/85. He was qualified for driving from
1/1/82 to 5/1/82 and from 6/1/84 to 5/31/88.

{\em DI\/} worked in and managed the Toy department from 1/1/82 to the
present. Her name is Di throughout her employment. The budget of the
Toy department was \$150K from 1/1/82 to 7/31/84, \$200K from 8/1/84
to 12/31/86, and \$100K from 1/1/87 to the present. Her salary was
\$30K from 1/1/82 to 7/31/84, \$40K from 8/1/84 to 8/31/86, then \$50K
from 9/1/86 to the present. {\em DI\/} is female and was born on
10/1/60. {\em DI\/} has been qualified for directing from 1/1/82 to
the present.

The present time (i.e., the value of {\tt now}) is 1/1/90.

\section{Classification of Benchmark Queries}

A classification of benchmark queries will be based on a comprehensive
taxonomy of queries. First, critria for such a taxonomy are outlined.
Next, the taxonomy itself is presented. As the taxonomy is too
fine-grained, categories are then merged into an adequate number of
groups which can subsequently be used for classification.

\subsection{Criteria}

Three criteria for an appropriate taxonomy of benchmark queries are
suggested.
\begin{itemize}
\item{} The taxonomy should be schema and instance independent. This
  criterion helps ensure that the taxonomy will persist when the
  benchmark database schema evolves as new versions appear. Ideally,
  this will allow for an incremental mode of work, where only new
  queries need to be categorized and existing queries do not need
  re-categorization.
\item{} The taxonomy should provide comprehensive coverage of
  benchmark queries. Comprehensiveness is desirable to avoid holes and
  point to many categories of queries.
\item{} The taxonomy should be useful when structuring the
  presentation of benchmark queries. Most importantly, it should
  provide sufficient structure. Thus, taxonomies that have only few
  categories and that map many queries to single categories are
  problematic. If the number of categories is excessive for
  presentation purposes, classes of categories may be identified with
  individual sections.
\end{itemize}

\subsection{The Taxonomy}

The taxonomy is characterized as having a projection (output) and a
selection component, much like SQL. Then each component is covered in
turn. Finally, the full taxonomy is summarized and a notation for
naming individual categories is defined.

\subsubsection{Top-level Taxonomy}

At the top level, the taxonomy is divided into two orthogonal parts,
namely a part where queries are categorized according to their {\em
  output component} and a part where the categorization is based on
the {\em selection component}. Thus, a category is described by two
components, as illustrated in Figure~\ref{fig:top}.

\begin{figure}[htbp] {\small
  \[
    \{ <\mbox{output component}> \}
    \times 
    \{ <\mbox{selection component}> \}
  \]}
  \caption{Top-level Description of Benchmark Taxonomy}
  \label{fig:top}
\end{figure}

This top-level design reflects the SQL template (i.e., {\tt SELECT}
\ldots {\tt FROM} \ldots {\tt WHERE} \ldots). The first component
categorizes the contents of the {\tt SELECT} clause, and the second
component categorizes the contents of the {\tt WHERE} clause. No
component is needed to reflect the {\tt FROM} clause where tuple
variables are defined. The two components are orthogonal only in the
same sense that the {\tt WHERE} and {\tt SELECT} clauses of a
particular query are orthogonal.

\subsubsection{Output-based Taxonomy}

The output-based taxonomy is intended to reflect the part of queries
where the format of the resulting tuples is specified. The taxonomy is
described in Figure~\ref{fig:pro1} and is explained in the following.

\begin{figure*}[htbp]
\begin{center}
  \leavevmode
    \[
      \left\{ \begin{array}{c}
        \mbox{\underline{explicit-attribute component}} \\
        \mbox{none} \\
        \mbox{projected} \\
        \mbox{complete}
      \end{array} \right\}
      \times
      \left\{ \begin{array}{c}
        \mbox{\underline{valid-time component}} \\
        \mbox{none} \\
        \left\{ \begin{array}{c}
          \mbox{\underline{type}} \\
          \mbox{event} \\
          \mbox{interval} \\
          \mbox{element}
        \end{array} \right\}
        \times
        \left\{ \begin{array}{c}
          \mbox{\underline{value}} \\
          \mbox{derived} \\
          \mbox{imposed}
        \end{array} \right\}
      \end{array} \right\}
    \]
\end{center}
\caption{Output-based Taxonomy}
\label{fig:pro1}
\end{figure*}                                                       

The idea is to distinguish between queries based on the format of the
result tuples. A tuple may include an explicit-attribute component and
a valid-time component, each of which are considered next.

If present, the explicit-attribute component, may contain all
attributes in the argument relation (multiple relations are discussed
below) or it may contain a subset of the attributes in the argument
relation. In the first case, the explicit attribute component is
``complete,'' and in the second, it is ``projected.''

To exemplify, consider a tuple telling that Ed is in the Book
department from 1/1/82 to 12/31/84. Here ``Ed'' and ``Book''
constitute the explicit-attribute component, and ``1/1/82'' and
``12/31/84'' is the valid-time component. If the argument relation
contained an attribute ``Salary'' in addition to the Name and
Department attributes, this result is projected.

If several relations are used in a query, the argument relation is the
Cartesian product of these, i.e., the schema is the concatenation of
the schemas of the relations used in the query.

The valid-time component of a tuple may be of three types. First, it
may be an event, i.e., a single time value (e.g., 3/1/83). Second, it
may be an interval, i.e., a sequence of consecutive time values (e.g.,
as above). Third, it may be an element, i.e., a set of time values
which may be described by a set of intervals (e.g., 1/1/82 to
12/31/84, 2/1/85 to 3/31/85, and 5/1/86 to 5/31/86).

Orthogonally, the value of a valid-time component may be derived or
imposed. A derived value is computed solely in terms of the valid-time
components of the tuples in the argument relation. An imposed value is
computed by explicit assignment in the query.

Note that at least one of the two components must be present in the
result of a query. This part of the taxonomy results in 20 mutually
exclusive categories.

The distinctions above are based on the schema of result relations. It
is possible also to distinguish between the cardinalities of result
relations, e.g., between set-valued and single-tuple valued results.

\subsubsection{Selection-based Taxonomy}

The selection component is divided into two parts, one for valid-time
selection and one for selection not involving valid time. See
Figure~\ref{fig:selt}.

\begin{figure}[htbp] {\small
  \[
    \{ <\mbox{valid-time selection}> \}^\ast
    \times 
    \{ <\mbox{non-temporal selection}> \}^\ast
  \]}
  \caption{Top-level Selection-based Taxonomy}
  \label{fig:selt}
\end{figure}

Both parts are based on the same observation. In general, a selection
predicate is built from atomic selection predicates using logical
operators (e.g., {\tt and}, {\tt or}, and {\tt implies}) and
parenthesis. Both parts categorize queries based on the atomic
predicates used in the queries. As several types of atomic predicates
may be used in the same query, queries generally fall into multiple
categories (as indicated in Figure~\ref{fig:selt} by the Kleene star,
``${}^\ast$''). We examine each part of the selection-based taxonomy
in turn.

Atomic valid-time selection predicates are assumed to be of the form
\[ arg_1 \mbox{\tt ~op~} arg_2 \hspace*{2mm},\]
where {\tt op} is a some comparison operator (e.g., {\tt precedes}, and
{\tt contains}). It is assumed that $arg_1$ is the valid time of the
data, and restrictions are imposed based on the type of the comparison
operator, on the origin of $arg_2$, and on the type of $arg_2$.
Figure~\ref{fig:sel2} outlines the categories.

\begin{figure*}[htbp]
  \begin{center}
    \leavevmode
      \[
        \left\{ \begin{array}{c}
          \mbox{\underline{type of comparison operator}} \\
          \mbox{duration-based} \\
          \mbox{ordering-based} \\
          \mbox{containment-based}
        \end{array} \right\}
        \times
        \left\{ \begin{array}{c}
          \mbox{\underline{type of $arg_2$}} \\
          \mbox{event} \\
          \mbox{interval} \\
          \mbox{element}
        \end{array} \right\}
        \times
        \left\{ \begin{array}{c}
          \mbox{\underline{origin of $arg_2$}} \\
          \mbox{explicitly supplied in query} \\
          \mbox{user-defined attribute value} \\
          \mbox{computed from other valid times}
        \end{array} \right\}
      \]
  \end{center}
  \caption{Valid-time Selection-based Taxonomy}
  \label{fig:sel2}
\end{figure*}

Three types of comparison operators are identified. First, a
comparison operator may be duration-based. For example the operator
{\tt spanExceeds} returns true if the duration of the first argument
is equal to or larger than the duration of the second argument.
Second, comparison operators may be based on ordering. Operators in
this category include {\tt precedes} and {\tt meets}. The first
applies to all timestamps and evalutes to true if the largest time in
the first argument is smaller than the smallest times in the second
argument. Operator {\tt meets} appears to be useful only for events
and intervals. Two timestamps meet if they are not separated by any
event (i.e., may be coalesced). Operators based on containment include
{\tt =} (identity), {\tt overlaps}, and {\tt contains}.

The second argument ($arg_2$) may be an event, an interval, or an
element. Also, it may come from three sources. First, it may be
supplied directly in the query, as a constant. Second, it may be the
value of a user-defined time attribute in an argument tuple. Note that
this is only possible for events if first normal form is required.
Third, like the first argument, the second argument may be computed
from valid times in the argument tuples.

If the three types of categories are completely orthogonal, this
part of the taxonomy will contribute with a total of 27 categories.
However, it may be debated whether intervals and elements may be used
as values of user-defined attributes (resulting in non-1NF relations).

The final part of the selection-based taxonomy categorizes queries
based solely on the part of the selection component that involves only
ordinary, non-temporal selection.

Many possibilities for categorization exist. Below, in
Figure~\ref{fig:sel1}, we distinguish between four significant types
of atomic selection predicates. First, an attribute may be compared
with a constant, supplied by the user. Second, attribute values, both
in the same relation, may be compared. Third, a primary key value may
be compared with a matching foreign key value. Fourth, arbitrary
attributes of possibly distinct relations may be compared. In the
figure, $\theta ::= \; < | > | \leq | \geq | = \;$, i.e., a
combination of equality and/or the one of the two inequality
operators. If we distinguish between situations where only equality is
involved and situations where inequality is involved, this give 8
categories.

\begin{figure*}[htbp]
  \begin{center}
    \leavevmode
      \[
        \left\{ \begin{array}{c}
          \mbox{\underline{non-temporal attribute value selection}} \\
          att~\theta~\mbox{\em Constant} \\
          att_1~\theta~att_2 \\
          att_k~\theta~att_{fk} \\
          att(rel_1)~\theta~att(rel_2)
        \end{array} \right\}
        \times
        \left\{ \begin{array}{c}
          \mbox{\underline{comparison operator, $\theta$}} \\
          \mbox{only equality } (=) \\
          \mbox{inequality } (<>)
        \end{array} \right\}
      \]
  \end{center}
  \caption{Non-temporal Selection-based Taxonomy}
  \label{fig:sel1}
\end{figure*}

\subsubsection{Additional Contributions---TEMPORARY}

The distinction between grouped and ungrouped queries has not been
integrated into the taxonomy. To do that, definitions of these
categories are needed.

\subsection{Overview and Naming of Categories}

Each query has a single output component, zero or more valid-time
selection components (one per such operator), and zero or more
non-temporal selection-based components (one per such operator). The
taxonomy is summarized in Figure~\ref{fig:tax}. There, the names
introduced in the taxonomy are used along with punctuation in order to
name a category.

\begin{figure*}[htbp]
\begin{BNF}
\nt{non-t selection} \=\is\ \= \kill
\nt{category} \> \is \> \nt{output} \qt{/} \lbr \nt{v-t selection}
\starbr \qt{/} \lbr \nt{non-t selection} \starbr \\
\nt{output} \> \is \> \qt{(} \= \lbr None \vbar Projected \vbar
Complete \rbr \qt{,} \` \com{explicit-attribute component} \\
\>\>\> \lbr \= None \vbar \` \com{no valid-time attribute} \\
\>\>\>\> \lbr Event \vbar Interval \vbar Element \rbr \qt{,} \`
\com{type of valid-time attribute} \\
\>\>\>\> \lbr Derived \vbar Imposed \rbr \rbr \qt{)} \` \com{value of
valid-time attribute} \\
\nt{v-t selection} \> \is \> \qt{(} \lbr Duration \vbar Ordering \vbar
Containment \rbr \qt{,} \` \com{operator type}\\
\>\>\> \lbr Event \vbar Interval \vbar Element \rbr \qt{,} \`
\com{argument type} \\
\>\>\> \lbr Explicit \vbar User-defined \vbar Computed \rbr \qt{)} \`
\com{argument origin} \\
\nt{non-t selection} \> \is \> \qt{(} \lbr \qt{=} \vbar \qt{$<>$} \rbr
\qt{,} \` \com{operator type} \\
\>\>\> \lbr Constant \vbar Single \vbar Foreign \vbar Arbitrary \rbr
\qt{)} \` \com{argument types} \\
\end{BNF}
  \caption{Overview of the Taxonomy used for Naming Categories}
  \label{fig:tax}
\end{figure*}

To exemplify the use of Figure~\ref{fig:tax} for naming categories,
consider the query ``When was Ed Manager of the Toy Department.''
This query is in the category shown next (with no valid-time
selection).

\begin{center}
  (None, Element, Derived) // (=, Constant)
\end{center}

It may be observed that the taxonomy gives rise to a large number of
categories. For example, assuming a single non-temporal operator and no
valid-time operators, there are $20 \times 8 = 160$ categories. Adding
a single valid-time operator while assuming orthogonality yields an
additional 4320 categories!

As a result, it becomes necessary to create classes of categories
which then may be used for clasifying the benchmark queries.

One approach would be to name a {\em class} of categories of queries,
by simply replacing one or more of the entries with the Kleene star
(``*''), e.g.,

\begin{center}
(None, Element, Derived) / (*,*,*) / (=, Constant)
\end{center}

The above query category would be in this class. In the next section,
we define the classes to be used in the benchmark.

\subsection{Forming Classes from Categories}

The idea is to remove distinctions from the comprehensive taxonomy
until a suitable number of classes is obtained. Figure~\ref{fig:tax2}
is thus a reduced version of Figure~\ref{fig:tax}.

\begin{figure*}[htbp]
\begin{BNF}
\nt{reduced v-t selection} \=\is\ \= \kill
\nt{class-name} \> \is \> \nt{reduced output} \qt{/} \lbr
\nt{reduced v-t selection} \starbr \\
\nt{reduced output} \> \is \> \qt{(} \= \lbr None \vbar Proj/Comp
\rbr \qt{,} \` \com{explicit-attribute component} \\
\>\>\> \lbr None \vbar Not empty \rbr \qt{)} \qt{/} \` \com{valid-time
  attribute component} \\
\nt{reduced v-t selection} \> \is \> \qt{(} \> \lbr Duration
\vbar Other \rbr \qt{,} \` \com{comparison operator type} \\
\>\>\> \lbr Event \vbar Interval \vbar Element \rbr \qt{,} \`
\com{argument type} \\
\>\>\> \lbr Computed \vbar Other \rbr \qt{)} \`
\com{argument origin} 
\end{BNF}
  \caption{Overview of the Classification of Queries}
  \label{fig:tax2}
\end{figure*}

The second and third lines concern output. Only the prescence or
absence of explicit attributes and timestamps are distinguished,
leading to three categories. The last three lines concern valid-time
selection (non-temporal selection is disregarded). Comparison
operators may be duration-based or not; arguments be of either event,
interval, or element type; and the arguments may or may not derive
from valid times of tuples.

\section{The Benchmark Queries}

\subsection{Overview}

The structure of this section is based on Figure~\ref{fig:tax2}. There
are three sections, each of which contains ten sections. The three
top-level sections classify queries according to the output. Thus,
the output from a query may have either only an explicit-attribute
value component (O1), only a valid-time component (O2), or it may have
both (O3).

Each top-level section contains the same ten sections. These divide
queries based on a single, distinguished valid-time selection
predicate\footnote{A query may contain several selection predicates,
  but it is classified according to a single predicate.}. The
predicate is of the format $arg_1$ {\tt op} $arg_2$ where {\tt op} is
a comparison operator which may (or may not) be duration-based. One
argument is the valid time of tuples in the argument relation. The
other argument may be of event, interval, or element type;
orthogonally, it may (or may not) be computed from existing valid
times in the argument relation. This results in a total of ten
classes (the combination of duration-based predicates and event
arguments is omitted).

\begin{BNF}
indentationindentat \= ionind \= \kill
\> (S1) \> (Duration, Interval, Computed) \\
\> (S2) \> (Duration, Interval, Other) \\
\> (S3) \> (Duration, Element, Computed) \\
\> (S4) \> (Duration, Element, Other) \\
\> (S5) \> (Other, Event, Computed) \\
\> (S6) \> (Other, Event, Other) \\
\> (S7) \> (Other, Interval, Computed) \\
\> (S8) \> (Other, Interval, Other) \\
\> (S9) \> (Other, Element, Computed) \\
\> (S10) \> (Other, Element, Other)
\end{BNF}

\subsection{Explicit-attribute Output}

This section involves queries which return only explicit-attribute
values---no valid-time values are present in the result.

\subsubsection{Class O1.S3 (Duration, Element, Computed)}

\query{Find the names of employees that have been in a department
  named Toy for a shorter period than has DI.} 
  {``Ed'' and ``Edward.''}
  {(Projected, None) / (Duration, Element, Computed) / (=, Constant)
    (=, Constant)}

  \noindent {\it The employee ED has been in a department named Toy
    for a period which is shorter than that of DI. The categorization
    is with respect to Figure 6. ``(Projected, None)'' indicates that
    only part of the attributes of the argument relation are present
    in the result and that there is no valid-time component. Next,
    ``(Duration, Element, Computed)'' indicates that a duration based
    predicates is used on element-valued arguments which are both
    derived from the valid-times of stored facts.  Finally, ``(=,
    Constant) (=, Constant)'' indicates that there are two
    non-temporal selection predicates that test for equality of an
    attribute value with a constant (i.e., the person must be DI and
    the department must have name Toy).}

\query{Find the current name and department name for the persons which
  made \$40K for a longer period than DI did.}
  {``(Edward, Book).''}
  {(Projected, None) / (Duration, Element, Computed) (Containment,
    Event, Explicit) / (=, Constant)}

  \noindent {\it In this query, there are two valid-time selection
    based predicates.  The one used for categorization compares the
    duration of time when a person makes \$40K with the period of time
    that DI makes \$40K. The other selects the name and department
    that overlap with the current time of qualifying persons.}

\subsection{Valid-time Output}

This section involves queries which return only valid-time
values---no explicit-attribute values are present in the result.

\subsection{Explicit-attribute and Valid-time Output}

The output from queries in this section contains explicit attribute
values with associated valid times.

\end{document}