\documentclass{CHEP2006}
\setlength{\paperheight}{297mm}
\setlength{\paperwidth}{210mm}

%%
%%  Use \documentclass[boxit]{JAC2003}
%%  to draw a frame with the correct margins on the output.
%%
%%  Use \documentclass[acus]{JAC2003}
%%  for US letter paper layout
%%

\usepackage{graphicx}

%%
%%   VARIABLE HEIGHT FOR THE TITLE BOX (default 35mm)
%%

\setlength{\titleblockheight}{35mm}

\begin{document}
\title{SQLBuilder: a replacement metadata language to SQL translator for SAM}

\author{%
Randolph J. Herber\thanks{herber@fnal.gov, +1.630.840.2966, Mail Stop 318},
FNAL, Batavia, IL 60510, USA}

\maketitle

\begin{abstract}
SQLBuilder is a replacement metadata language to SQL translator for SAM.
The exsting translator has been in use for five years and needs replacement
because of systemic problems, including desired enhacements.
\end{abstract}

\section{OVERVIEW}

{\em SAM}~\cite{SAM} is in use at CDF, D{\O} and MINOS.
It uses a metadata language to write {\em dataset
definitions} (rules) to select files for {\em snapshots} (lists of files
which meet a dataset definition at the time the snapshot was created,
are stored in the data base and normally are not changed afterward).
The reasons for this metadata language are: the users want to avoid
the complexities of SQL and they have demonstrated that they can easily
overload a data base system with improperly written SQL.
The present metadata language to SQL translator suffers from an ad-hoc
tokenizer, an ad-hoc parser and internal data structures that do not lend
themselves to easy processing, easy maintenance or effective storage of
control data.  
SQLBuilder is intended to be a replacement metadata language to SQL
translator for SAM.

SQLBuilder's purpose is to address the aforementioned problems in the
present metadata language translator.
The target language will be Oracle 9i or 10g SQL~\cite{Oracle9i}.
The generated queries will return sets of file identifiers.
CORBA~\cite{CORBA} will be used to communicate with the remainder of the
SAM system.

The selection criteria are named, parameterized tests on the SAM metadata
combined by boolean operators.  Intermediate result sets may be combined
by set operators.
There will be a capacity to include previous SAM dataset definitions (with
a check for infinite inclusion recursion) via the metadata language
operator {\tt \_\_SET\_\_}.

\section{LESSONS LEARNED}

Bad ideas:
\begin{Itemize}
\item Using hyphen both for negative signs for numbers and for a range
      separator.  
      This requires parser-generators with two token look-ahead or
      very specialized handling in the tokenizer.
\item Implicit `and' or `='.
      Optional elements in a grammar are hard to handle and can cause
      ambiguities.
\item Unquoted string values complicate recognization of keywords.
\item Parameters with only string values that only can be compared for equality.

      Parameters should be data typed for strings, numerics and times
      and be comparable for all the relational operators.
\item Parameters should be usable with data definitions and other entities.

      In SAM, parameters are associated only with files and processing
      requests.
\item File names are not versioned, time stamped or otherwise marked.
      This is needed so that bad files can be replaced without destroying
      the historical value of the data base by removing metadata from
      the data base.
      It would allow snapshots to show where the old file versions were used.
      This versioning may cause changes in the metadata language.
File name alone is not sufficient to identify a file.
\item Storing the data definition statement in an intermediate form.

      The original data definition string needs to be stored in the data base
      to document what the user originally specified and to support
      {\tt \_\_SET\_\_}.
\item The use of multiple {\tt OR} operators very rapidly results in poor
      data base performance.
\item The use of the {\tt MINUS} operator, in our experience, on Oracle
      data bases at least, has very poor performance.
\end{Itemize}

Good ideas:
\begin{Itemize}
\item Using a parser-generator is a good idea as it is extremely
      difficult to write or maintain one correctly by hand.
      LL~\cite{LL} parsers are somewhat easier than LR~\cite{LR} parsers
      to write by hand; but, they are somewhat less efficient and
      good error message generation is somewhat more difficult.
\item Using UNIX style wild cards instead of Oracle style wild cards
      in string values.
      Users do expect to use `?' and `*' and  do not expect to use `\_' and
      `\%' as wildcards.
\item Using multiple valued tests instead of multiple single valued tests
      is a good idea.
      Consider, e.g., a typed run number which occurs both in MINOS and
      at D{\O}: {\tt run(200000 'monte\_carlo')} vs. {\tt run\_number = 200000
      and runtype = 'monte\_carlo'}.  The first form clearly indicates that
      both conditions on one chain of data base tables.
      This eases implementation significantly~\cite{IndependenceDependence}.
\item Parameters to associate arbitary attributes to entities such as
      files and requests.
\item The program's services also should be available via Web services
      as well as CORBA.
\end{Itemize}

\section{DIMENSIONS}

There are several classes of {\em dimensions} (tests on the data base that
can be used construct data definitions):
\begin{Itemize}
\item Tests on single columns within the database.
      E.g., {\tt file\_name = 'fred'} or {\tt snapshot\_id = 83467}.
\item Tests on multiple columns in one or more tables along a
      joined chain of tables within the database.
      E.g., {\tt run(200000 'monte\_carlo')}.
\item Tests on parameters.
      E.g., {\tt pythia.topmass='137'}.
\item Tests specified by SQL functions or code on multiple
      columns in one or more tables along a joined chain of tables
      within the database.
\item Test data sources should be specified by data base table and column
      pairs and {\em Chains and Links}, which are  {\em links} (description
      of the join conditions between two tables) and {\em chains} (list of
      links needed to connect from the search target data base table
      (in the SAM implementation, that is the table {\tt DATA\_FILES})
      to the furthest table needed for the test.
\end{Itemize}

\section{IMPLEMENTATION PLAN}

SQLBuilder is to be written in Java~5~\cite{Java}.
Parser-generators, such as Antlr or JavaCC and JJTree will used to write
the ``front-end''.
After the {\em AST}~\cite{AST} ({\bf A}bstract {\bf S}yntax {\bf T}ree)
has been built with appropriate attributes given to the nodes of the tree,
the tree will be processed, possibly several times, to rewrite the expression
as needed and to gather information on what dimensions are used.

It will be necessary to analyze the present usage of the data definition
language (35K at CDF, 326K at D{\O} and 1151 at MINOS) in terms of the
language elements and constructs used.
Test cases to test all language elements at least once will need to be
added to the test suite.

The location of the Chains and Links (defined above) data storage is not
yet decided.
There are both technical and management level issues here.
Proposed locations are:
\begin{Itemize}
\item program code resident.
      This is undesirable for maintenance reasons.
\item data base resident.
      This could be done with JDBC~\cite{JDBC} or Hibernate~\cite{Hibernate}
      and would permit reasonably easy maintenance.
\item Flat text file using a defined syntax.
      A separate tokenizer and parser pair would be written to read the file.
\item XML~\cite{XML} file or web page.
      In this case, the tokenizer and parser would be available in Java.
      A DOM~\cite{DOM} or XML editor would be needed to ease maintenance.
\end{Itemize}

The back-end will consist of an AST to an abstract SQL translator followed
by an abstract SQL translator to Oracle specific SQL translator.
The AST to abstract SQL translator basically generates the joins
(tables and where conditions) and values tests (where conditions)
in a data base neutral form.  The abstract SQL translator to
Oracle specific SQL translator generates the SQL to be returned
to the SAM DB Server.

Extensive testing will be necessary based on the use cases mentioned above.

User, system and administration level documentation are planned to be written.

The references contain the details of the proposed grammar~\cite{grammar},
written in a EBNF~\cite{EBNF} style and being essentially
context-free~\cite{CFG} and the tokens~\cite{tokens}.

\section{ACKNOWLEDGEMENTS}

\begin{Itemize}
\item This project is sponsored by DOE contract DE-AC02-76CH03000.
\item The Fermilab and the participating institutions staffs for their
      part in creating SAM.
\item Adam L. Lyon, Krzysztof Genser, Doug Benjamin,
      Lauri L. Loebel-Carpenter, Sinisa Veseli and Stephen P. White
      assisted with this paper.
\end{Itemize}

%\begin{thebibliography}{9}   % Use for  1-9  references
\begin{thebibliography}{99} % Use for 10-99 references

\bibitem{SAM} SAM:
http://d0db-dev.fnal.gov/sam/

\bibitem{Oracle9i} Oracle\(^{tm}\) 9i:\\
https://misdev1.fnal.gov/oracledoc/9iv2/DOC/index.htm

\bibitem{CORBA} CORBA\(^{tm}\):\\
http://www.omg.org/gettingstarted/corbafaq.htm.

\bibitem{LL} LL parser:
http://en.wikipedia.org/wiki/LL\_parser

\bibitem{LR} LR parser:
http://en.wikipedia.org/wiki/LR\_parser

\bibitem{IndependenceDependence} Dependence --- Independence\\
https://plone3.fnal.gov/SAMGrid/Members/herber/\linebreak[0]%
Independence-Dependence/file\_view

\bibitem{Java} Java\(^{tm}\) computer language:
http://java.sun.com/

\bibitem{AST} Abstract Syntax Tree\\
http://en.wikipedia.org/wiki/Abstract\_syntax\_tree.

\bibitem{JDBC} JDBC\(^{tm}\):
http://java.sun.com/products/jdbc/.

\bibitem{Hibernate} Hibernate --- object persistence for Java\\
http://www.hibernate.org/.

\bibitem{XML} XML:
http://www.w3.org/XML/

\bibitem{DOM} DOM:
http://www.w3.org/DOM/

\bibitem{EBNF} Extended Backus-Norm Form:\\
http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf

\bibitem{CFG} Context-Free Grammars:\\
http://www.cs.utsa.edu/~qingyi/cs4713/handouts/CFG.pdf

\bibitem{grammar} Proposed metadata language grammar:\\
https://plone3.fnal.gov/SAMGrid/Members/herber\linebreak[0]%
/Grammar/file\_view.

\bibitem{tokens} Proposed metadata language tokens:\\
https://plone3.fnal.gov/SAMGrid/Members/herber/Tokens\linebreak[0]%
/file\_view.

\bibitem{manifesto} Design guidelines:\\
http://www.physics.gla.ac.uk/pipermail/metadata/\linebreak[0]%
2004-September/000069.html.

\end{thebibliography}

\end{document}
