![](media/image1.png){width="1.1791666666666667in"
height="0.9131944444444444in"}Technical Report GriPhyN-2002-02

www.griphyn.org

**DRAFT: *COMMENTS SOLICITED***

***Version V8 - January 20, 2002***

***This version of the VDL specification is a preliminary GriPhyN
project draft, intended solely to gather comments from the GriPhyN
project community. It reflects ideas for refinement of the VDL-0
prototype that was used at SC2001. Based on your feedback on* this
*draft, we intend to finalize version 1 of the VDL language and revise
and clarify this document accordingly. Note that VDL-1 is not yet
implemented.***

***This is based on the original GriPhyN virtual data work describe by
Deelman et al in \[3\] and on further discussions with a great many
people, notably Ewa Deelman and David Malon. Thanks to all of you. Rick
Cavanaugh and Jim Annis deserve special mention for struggling with
VDL-0 and providing valuable feedback on what's needed in VDL-1.***

**The GriPhyN Virtual Data System**

Jens-S. Vöckler Mike Wilde Ian Foster

(voeckler@cs.uchicago.edu, wilde@mcs.anl.gov, foster@mcs.anl.gov)

Abstract

In large-scale scientific experiments, huge amounts of data are
collected from simulations and scientific instruments (telescopes,
colliders, climate sensors, etc). Viewed as a whole, the dataset
collections of these experiments can be seen as a large database stored
in a combination of flat files, relational tables, and persistent object
structures. Over time, as the experiments proceed across many years,
complex relationships between data objects evolve. Two capabilities that
are of interest and value to such experiments are: the ability to track
how every data product was derived, and the ability to create and/or
re-create data products from this knowledge. Such re-creation could be
used either to replace ("re-materialize") data products that were
deleted, to produce new data products which were defined but which were
never created, or to create exact or equivalent replicas of data
products at remote locations when the re-creation process is more
efficient than the data transfer process.

We describe the architecture and schema of a virtual data system that
allows us to both represent and query information about the
computational procedures used to materialize data products. A prototype
has been constructed, comprising a relational database schema, a virtual
data access language for specifying and querying the database, and a
runtime system that can execute computation schedules constructed from
database queries. This prototype was successfully used to demonstrate
that a complex derivation of simulated high-energy physics collision
event data from the CERN CMS experiment could be described and executed
using the proposed approach.

TABLE of CONTENTS

[1 Overview 3](#overview)

[2 Transformations and Derivations 3](#transformations-and-derivations)

[3 The Virtual Data Language 4](#the-virtual-data-language)

[3.1 Defining Basic Transformations 4](#defining-basic-transformations)

[3.2 Defining Basic Derivations 5](#defining-basic-derivations)

[3.3 Derivation Dependencies 6](#derivation-dependencies)

[3.4 The Diamond DAG Example 7](#the-diamond-dag-example)

[3.5 Querying the Virtual Data Catalog
8](#querying-the-virtual-data-catalog)

[3.6 Deriving Files 9](#deriving-files)

[3.7 Defining Compound Transformations
9](#defining-compound-transformations)

[4 Virtual Data Catalog Services in the Data Grid Architecture
12](#__RefHeading___Toc536102310)

[5 The VDC Schema 13](#the-vdc-schema)

[6 Advanced VDL Features 15](#advanced-vdl-features)

[6.1 Execution Environments and Transformation Signatures
15](#execution-environments-and-transformation-signatures)

[6.2 Augmenting the Model with Job Execution Information
16](#augmenting-the-model-with-job-execution-information)

[6.3 Tracking the Creation of Physical Files; File Equivalence
17](#tracking-the-creation-of-physical-files-file-equivalence)

[6.4 Transformations to Represent Data Capture
17](#transformations-to-represent-data-capture)

[6.5 Augmenting the Model with Resource Cost Information
17](#augmenting-the-model-with-resource-cost-information)

[6.6 Adding Authentication and Authorization
18](#adding-authentication-and-authorization)

[6.7 Generating Virtual Data Derivation Specifications from Templates
and Functions
18](#generating-virtual-data-derivation-specifications-from-templates-and-functions)

[6.8 Variable Length Parameter Lists, and Flexible Sequences
19](#variable-length-parameter-lists-and-flexible-sequences)

[6.9 Data-type Based Transformation Templates
20](#data-type-based-transformation-templates)

[6.10 Handling Tri-Modal Data Representation
20](#handling-tri-modal-data-representation)

[6.11 Linking Knowledge and Metadata Searches into the Model
20](#linking-knowledge-and-metadata-searches-into-the-model)

[7 Open Issues 21](#open-issues)

[APPENDIX: VDL-1 LANGUAGE DEFINITION
22](#appendix-vdl-1-language-definition)

[Bibliography 23](#bibliography)

# Overview

We provide an overview and programmer's guide for Version 1 of the
*GriPhyN Virtual Data System* (GVDS). The purpose of this system is to
allow for the capture and use of information concerning how data was, or
can be, generated by computations. We describe, in particular:

-   The GVDS *virtual data catalog* (VDC): a relational schema that
    describes entities and relationships involved in tracking the
    derivation of data objects.

-   The GVDS *virtual data language* (VDL): a textual language that is
    used to (a) define how data objects are derived and (b) request the
    execution of those derivations. Thus, VDL serves as both a data
    definition language and data manipulation language for the VDC.

-   A GVDS *virtual data language interpreter* (VDI): the mechanism that
    executes the VDL.

-   VDC and VDI together comprise the GriPhyN Virtual Data System.

# Transformations and Derivations

VDL captures and formalizes descriptions of a how a program can be
invoked, and records its potential and/or actual invocations. The
abstract description of how a program is to be invoked, which parameters
it needs, which files it reads as input, what environment is required,
etc., is called a *transformation*. A transformation can be invoked
multiple times with specific, unique parameter values. Each invocation
of a transformation with a specific set of input values and/or files is
called a *derivation*.

Figure 1 below shows the simple relationship between transformations and
derivations: each transformation can have multiple derivations
associated with it; each derivation is based on a single transformation.
(As we describe below, this single transformation can itself be a
compound transformation that is based on other sub-transformations, much
as functions can be composed of other functions.)

Figure 1: Relationship between transformations and derivations.

A derivation, which deals solely with logical file names (as defined in
\[2\]), represents either:

1)  a recipe for how to create specific logical files by invoking a
    transformation in the future,

2)  a record of how specific logical files were produced by invoking a
    transformation, or

3)  a recipe for how to re-create specific logical files that existed
    but were deleted.

In case 1, numerous derivations can be described for invocation at a
later time. Such derivations can be thought of as defining "virtual
data". In case 2, derivations serve as a historical log or trace of
transformations that were invoked. Case 3 is a variation of case 1.
These cases are all related, as a derivation may often go through all of
these states in succession.

Using terminology from programming languages, we say that a
transformation defines formal arguments (i.e., "placeholders"), for
which a derivation supplies actual arguments \[10 -- [add to
endnote]{.mark}\]. A derivation describes a single invocation of a
specific transformation, supplying actual arguments (strings or logical
file names) for the formal arguments defined in the transformation.

Transformations and derivations can be compared and contrasted as
follows:

-   A transformation is like a procedure definition. A derivation is
    like the trace record of a procedure invocation.

-   Transformations contain placeholders for logical file names.
    Derivations contain the actual logical file names that are required
    to invoke the transformation, and the actual logical file names
    produced by the invocation.

-   Transformations can specify functions to estimate their cost of
    execution. Derivations contain an actual cost estimate (and, if the
    derivation has been already invoked, an actual cost value).

-   Transformations can be composed into "compound" transformations
    using semantics similar to the definition of functions in a
    programming language. The limited composition allowed in this
    current version, VDL-1, permits compound transformations to be
    described as a directed acyclic graph of other transformations.
    Derivations, however, cannot be nested or composed into compound
    definitions.

# The Virtual Data Language

In this section we introduce VDL syntax by showing how it is used to
represent both (a) simple transformations involving a single executable
application and (b) compound transformations that are composed of
multiple internal transformations.

VDL statements are interpreted by the VDL interpreter, and cause the
virtual data catalog to be updated, queried, or used to perform data
derivations. These updates, queries, and actions are illustrated through
examples below, and will (in a future version) be described using XML.

## Defining Basic Transformations

Consider the following definition of the transformation t1:

TR t1 (IN a1; OUT a2)

{

APP /usr/bin/app3;

CARG parg -p 500;

CARG farg -f \$a1;

CARG xarg -x --y;

CARG stdout \$a2;

ENV MAXMEM=100000;

}

This declaration defines the information necessary to execute a simple
UNIX executable program, "app3". Line by line, this transformation
definition reads as follows:

-   The TR statement assigns the transformation a name ("t1") that
    derivation definitions can use to refer to it, and declares that t1
    reads one input file (given the formal parameter name a1) and
    produces one output file (formal parameter name a2). The parameters
    declared in the TR header line are *transformation arguments,* which
    are (currently) restricted to be only file names. (Note that we use
    the terms "parameter" and "argument" interchangeably in this
    document.)

-   The APP statement defines the absolute path name of the executable
    application file.

-   The first three CARG statements describe how the *command line
    arguments* to app3 (as opposed to the *transformation arguments* to
    t1) are constructed. The name of each command line argument (in this
    case, parg, farg, and xarg) are used within the VDL to match actual
    command line parameter values supplied in derivation declarations to
    their place in the command line. The string to be placed in the
    command line occurs after the parameter name. For the parameter name
    "farg", the sub-string "\$a1" would be replaced at invocation time
    by the value of the actual logical file argument supplied as the
    first parameter by a derivation definition that invokes t1.

-   The fourth CARG statement has the special name "stdout"to denoteb
    that the actual value of a2 would be used as the filename into which
    the standard output of app3 would be redirected.

-   CARG values are inserted into the command line in the order in which
    they appear in the TR definition (except that stdin and stdout
    declarations are always placed at the end of the command line). Note
    that the command line parameter names (such as parg, etc. in the
    above example) are used solely within the VDL to match and process
    command line arguments. These names do not show up in the
    construction of the actual command line.

-   Finally, the ENV statement adds one variable (MAXMEM) to the
    environment for the execution of app3. Transformation arguments
    (like \$a1, \$a2) can be substituted into environment variable
    values in the same way as they can be inserted into command line
    argument strings.

To summarize and clarify the two types of parameters described above:

-   Transformation arguments ("IN" and "OUT" lists) are the names of
    input files read by and output files produced by a transformation.

-   Command line arguments ("CARGS") are strings that are concatenated
    to form the command line of the executable described by the
    transformation.

-   Transformation argument values can be inserted into command line
    arguments using the familiar shell substitution convention "\$name"
    (formally called "interpolation" in shell language).

## Defining Basic Derivations

A DV or derivation definition adds the record of one invocation of a
transformation to the virtual data catalog. The DV definition specifies
the *actual* logical files read by and produced by that invocation, by
supplying logical file names for the formal filename parameters declared
in the transformation. For example, to record an invocation of
transformation t1 defined above, we might use:

DV t1 (run1.exp15.T1932.raw, run1.exp15.T1932.summary) {

CARG parg --p 600;

ENV MAXMEM=20000;

}

The name specified immediately after the DV keyword is the name of the
transformation that the derivation invokes. Unlike transformations the
names of derivations are not defined by a VDL statement, but rather are
assigned internally by the catalog. Derivations can be located in the
catalog by searching for them via their logical filenames (from their IN
and OUT declarations) as well as other attributes (see Section Error:
Reference source not found).

The association between an actual parameter in the derivation and a
formal parameter in the transformation specification is done by
position. For example, in the DV statement above, parameter a1 of
transformation t1 will receive the value run1.exp15.T1932.raw and a2 the
value run1.exp15.T1932.summary. This derivation also overrides the
default value for command line argument "parg", using "-p 600" instead
of "--p 500," and overrides the value of the environment variable MAXMEM
with 20000 instead of 100000.

Thus, the DV definition above would invoke the app3 command as:

export MAXMEM=20000\
/usr/bin/app3 --p 600 --f run1.exp15.T1932.raw --x --y \>
run1.exp15.T1932.summary

Filenames listed as IN and OUT files need not necessarily be translated
into parameters. For example, if the filename was determined directly by
the executable through an internal definition or is dynamically
determined, it might not appear on the command line even though the file
is read or written by the application. (In such cases, applications that
know or can detect what filenames were read and written by an
application could, after the fact, create a derivation record to
describe what, in fact, the application did with respect to data
dependencies).

The filename insertion semantics can handle a wide variety of argument
passing conventions. However, executables with argument passing
conventions which are more complex than this model can describe must be
executed by producing "wrapper" scripts or executables that adapt the
VDL conventions to those expected by the executable. For example,
applications that read the names of further input files from a "control"
file can often be handled with a wrapper that accepts the filenames as
command line arguments and places them in the control file before
calling the actual application. In some cases, the creation of the
control file itself could be described as a transformation that reads
several files and produces the control file as its output. Then the real
transformation can be described as having the control file as an input.

Note that VDL deals solely with logical file names. The mapping between
a logical filename and physical filename(s) is the task of the replica
catalog, and is handled by Grid components such as the request planner,
which combine information from both the replica catalog and the virtual
data catalog in order to determine the real physical file names to use
when the application programs described by transformations are actually
executed.

## Derivation Dependencies

The power of derivation tracking is seen most clearly in the ability to
track chains of data dependencies between derivations. Consider the
following two transformations, along with a derivation description based
on each:

![](media/image2.wmf){width="0.7020833333333333in"
height="2.004166666666667in"}

TR trans1 (IN a1; OUT a2)

{

APP /usr/bin/app1;

CARG stdin \$a1;

CARG stdout \$a2;

}

TR trans2 (IN a1; OUT a2)

{

APP /usr/bin/app2;

CARG stdin \$a1;

CARG stdout \$a2;

}

DR trans1 (file1, file2);

DR trans2 (file2, file3);

These definitions state that the output of the first derivation is the
input to the second derivation. Thus, if neither of the two output files
file2 or file3 exist, and a request is made to deliver the output file
of the trans2 derivation (file3), the data dependencies recorded in the
catalog inform the system that trans1 must be run before trans2, and
that its output file (file2) be used as the input file for trans2. In
this manner, arbitrarily complex directed acyclic execution graphs
("DAGs") may be automatically constructed and executed in response to
requests for one or more files.

## The Diamond DAG Example

![](media/image3.wmf){width="5.040277777777778in"
height="1.9520833333333334in"}

Figure 2 Yourdon dataflow chart of the diamond DAG example

We illustrate the use of VDS-1 by using it to express the
transformations illustrated in Figure 2 above. A number of logical files
are produced as a result of this computation. These files are named f.a,
f.b, f.c, and f.d in the figure. In this example DAG, a top node
generate generates creates some data set to be store into file f.a. Two
processes findrange each operate on disjoint subsets of the input data
file f.a, publishing their results in f.b and f.c respectively. A final
node analyze combines the two halves.

We use the VDL-1 statements below to populate the database by defining
the three transformations generate, findrange, and analyze; and the
derivations used to produce logical files f.a, f.b, f.c, and f.d.

> TR generate (OUT a) {
>
> APP generator.exe;
>
> CARG stdout \$a;
>
> }

TR findrange (IN a; OUT b) {

> APP ranger.exe;
>
> CARG arg --i 0.0;
>
> CARG stdin \$a;
>
> CARG stdout \$b;
>
> }

TR analyze (IN a, b; OUT c) {

> APP analyze.exe;
>
> CARG file \$a \$b;
>
> CARG stdout \$c;
>
> }
>
> DV generate(f.a);
>
> DV findrange(f.a,f.b) { CARG arg --i 0.5 }
>
> DV findrange(f.a,f.c) { CARG arg --i 1.0 }
>
> DV analyze(f.b,f.c,f.d);

Notice that the second transformation is being used twice. In order to
parameterize a transformation, a derivation can override the default
values of a command line argument, in this case the --i argument to
findrange.

## Querying the Virtual Data Catalog

A large (and readily extensible) set of search commands is provided in
VDL to extract a list of derivation or transformation definitions. The
search output can (optionally) be returned in the same format as the
commands that could be used to re-create the matching entries (note that
this will eventually be XML). A summary of VDL query commands (to be
defined in more detail in a later draft) is provided here:

Search for derivations by:

-   One or more input logical file name

-   One or more output logical file name

-   A set of input and/or output logical file names

-   An exact match on input and/or output files

-   A match on associated transformation name, application name, and/or
    input and/or output files

The output options for a search are:

-   Show just the derivations matching

-   For each matching derivations show all the dependent derivations
    necessary to provide input files (assuming no files exist).

-   Show one (or more) ways to derive a specific file

-   Show output as choice of: columnar summary; VDL-1 format (for
    re-execution); XML

Search for transformations by:

-   File name matches (as for derivations)

-   Transformation and Application name matches

-   CARG or ENV argument matches

## Deriving Files

A set of VDL functions are provided to either request that the
derivations necessary to produce a set of files are executed, or, to
execute a specific derivation. These primitives are defined as follows:

-   get -- return a file if it exists else recursively execute the
    derivations needed to produce the file

-   derive -- execute a specific derivation

Get a result, (e.g. sqrt(3)) from a file if you have it, and create and
execute a derivation if you do not.

Note that these commands need to interact with, and make certain
assumptions about, the replica catalog and the location of existing
replicas of logical filenames.

This section must be expanded and illustrated with examples in a future
revision.

## Defining Compound Transformations

In the same manner as we observed in section 3.3 above, transformations
can also be specified in the form of dags that describe the coordinated
execution of multiple programs and the passing of data files between
them. These are called "compound" transformations.

A compound transformation can be invoked in exactly the same manner as a
simple transformation, with a single derivation statement. All of the
internal transformation invocations within a compound transformation are
tracked in the catalog, along with all of the files read by and produced
by the internal transformation steps. In this manner, the system remains
fully cognizant of all of the data dependencies, and arbitrary files
within those dependency chains can be deleted and re-derived at a later
time based on this stored knowledge.

Figure 3: Hierarchy of simple and compound transformations.

The diagram in Figure 3 shows the class hierarchy of
transformations[^1]. In words, this diagram states the following: a
transformation can either be a simple transformation, or a compound
transformation. A compound transformation is itself composed of
*references* (expressed via the "use" declaration) to one or more
transformations, each of which in turn are either simple or compound.
Any transformation can be referred to by a compound transformation.

Consider the following example:

TR trans1 (IN a1; OUT a2)

{

APP /usr/bin/app1;

CARG *etc;*

ENV *etc;*

CARG stdin \$a1;

CARG stdout \$a2;

}

TR trans2 (IN a1; OUT a2)

{

APP /usr/bin/app2;

CARG *etc;*

ENV *etc;*

CARG stdin \$a1;

CARG stdout \$a2;

}

TR trans3 (IN a1, a2; OUT a3)

{

APP /usr/bin/app3;

CARG parg -p foo;

CARG farg -f \$a1;

CARG xarg -x --y --o \$a3;

CARG stdout \$a2;

ENV MAXMEM=100000;

}

TR trans4 (IN a1, a2; OUT a3)

{

COMPOUND;

CARG *etc;*

ENV *etc;*

TEMP file a4 ...;

TEMP file a5 ...;

USE trans1 (\$a1, \$a4) {

CARG *etc;*

ENV *etc;*

}

USE trans2 (\$a2, \$a5) {

CARG *etc;*

ENV *etc;*

}

USE trans3 (\$a4, \$a5, \$a3) {

CARG *etc;*

ENV *etc;*

}

}

Here, trans1, trans2, and trans3 are all simple transformations that
each involves the invocation of a single application program.
Transformation trans4, however, is a "compound" transformation, as seen
by the substitution of the keyword "compound" for the name of an
application to execute. There are some artificial parameters introduced
by the "temp" keyword in the compound transformation to glue
transformations together via temporary filenames (which could be
discarded after their last usage).

The "use" keyword refers to a known (previously defined) transformation.
Transformations referred to within a compound transformation via use
keywords form a directed acyclic graph (DAG) of transformations, as
indicated by the input-to-output dependencies of the logical filenames
named in their parameter lists. These graphs can specify parallel
execution of nested transformations to the extent permitted by data
dependencies.

In all other respects, and in particular, from the point of view of its
external interface, trans4 looks just like any other transformation.
These semantics encapsulate the definition of transformations in a
uniform way, regardless of whether the transformation is simple or
compound.

We can thus define a compound transform that in turn uses a combination
of simple and compound transformations:

TR trans5 (IN a1, a2; OUT a3)

{

COMPOUND;

TEMP a4 \<TBD\>;

USE trans1 (\$a1, \$a4) {

CARG *etc;*

ENV *etc;*

}

USE trans4 (\$a2, \$a4, \$a3) {

CARG *etc;*

ENV *etc;*

}

}

Note that:

-   Each transformation must be defined before it can be used as nested
    component in a compound transformation (i.e., before it can appear
    in a USE declaration).

-   Each transformation declaration *and* USE declaration defines the
    full interface (command line arguments, environment variables, etc)
    of the transformation.

-   Compound transformations define a "DAG template".

-   Simple and compound transformations are invoked in exactly the same
    manner by derivations.

The above example contains the "temp" phrase to declare a local
temporary filename identifier. Such files are solely used for the
purpose of gluing transformations by accepting the result from one
transformation and providing input for another transformation.

*Open Issues: Discuss this feature, the scope of the filename, clean-up
mechanism and name clash avoidance
strategies.*[]{#__RefHeading___Toc536102310 .anchor}

# Virtual Data Catalog Services in the Data Grid Architecture

As Grid jobs are created and executed, their *data dependencies* are
determined through various proposed mechanisms, most of which are
themselves open research problems. These mechanisms include: explicit
declaration via a VDL; transparent extraction from job control language;
generation by higher level job creation interfaces such as Grid portals;
or creation by monitoring and logging job execution facilities and file
accesses.Regardless of the manner in which they were determined,
dependencies for derived files (of interest) are entered into the
virtual data catalog. These entries can be made *before* the job is
executed, in which case they serve as links to the information needed to
generate a file, or *after* a job is executed, in which case they serve
as a record of how to *re*generate a file.

A **metadata catalog** (MC) describes application-level information
*about* logical files that no general Grid execution mechanism could
know or detect. This is stored in a metadata catalog, which we provide a
simplified abstraction of by describing it as a table of triads: \[
attribute, value, lfn \]. Each LFN (logical file name) can have zero or
more entries in this table. Metadata is typically produced by the
application itself, or by the users of the application who can, from the
parameters by which a file was produced, *deduce* the application-level
attributes of the file, or by scanning the contents of the file with
various filters that can determine attributes after the fact from raw
data.

A **virtual data catalog** (VDC) describes how to derive a specific
file. This knowledge is embodied in the form of tables that describes
the transformations that were executed to produce files and the
parameters that were (or are to be) passed to a specific invocation of
the transformation. (To this, we will likely add, as the architecture
evolves, a knowledge catalog that knows how to derive---or locate---a
class of files based on higher layer descriptions of the application
knowledge domain, sometimes called "ontologies.")

A **replica catalog** (RC) (or, equivalently from our perspective, a
distributed replica location service) keeps track of all logical files
of interest to Data Grid users. A replica catalog entry for a logical
file may point to zero or more physical instances of the logical file.

The key architecture issues here are the linkages between these three
"logical" catalog structures:

-   Each logical file in the RC can be linked with zero or more
    attribute-value pairs in the MC.

-   Each logical file in the RC can be linked with zero or one
    derivations.

-   Each derivation in the VDC can be linked with zero or more logical
    files required for its derivation.

-   Each derivation in the VDC can be linked with zero or more logical
    files that it derives.

These linkages are indicated by the 4 arrows in in Error: Reference
source not found. Note that each linkage is based on logical file
names---or, in the case of a transformation, identifiers that represent
logical file names.

![](media/image4.wmf)

*Figure 4: Architectural view of catalog relationships*

As jobs are prepared for execution (in part by the planner), all logical
files needed for a job are determined. For each logical file, zero or
more physical copies may exist. The task of the planner is to determine
a site at which to execute the job, and then determine how to make all
the required logical files accessible to the job. For logical files of
which no physical copy is currently accessible, the planner can decide
to either copy a replica of the file to a place where the job can access
it, or can decide to materialize a file, possible followed by a move or
copy operation to make the file accessible to the job. Such decisions
would be based on cost estimates of copying vs. recreating. (*show
pseudo-code for the overall decision-making algorithm here...)*

The planner must also determine how to deal with the possible relocation
of the physical files derived by a job. These derived files may need to
be relocated to specific physical file storage servers, based on various
policy issues.

At later points in time, storage management functions may seek to
reclaim space on storage servers by removing physical copies of logical
files tracked by the replica catalog. When such needs arise, the storage
manager has the freedom to delete files for which other copies exists,
or for which derivations are known.

*Open Issues: Discuss file storage pools and rules for pool use -
transient vs permanent. Discuss tempnames here -- use Jens' diagram. Do
we need a micro-planner? Discuss file name choice issues -- actual vs
anonymous (randomly chosen) logical and physical file names.*

# The VDC Schema

This section presents a more detailed view of the VDC-design and
internal representation. It may be skipped on first reading.

Figure 5, which describes the VDS-1 schema as a UML "class diagram"
\[[ref]{.mark}\], is a more detailed view of Figure 3. The
transformation class is split into its components XFORMATION and
FORMALPARAMETER. The derivation class is created from the combination of
XFORMATION, FORMALPARAM and ACTUALPARAM.

Figure 5: UML representation of the VDS-1 schema

An ACTUALPARAM can be either a logical file name or some other value,
such as a numerical or string value. The ACTUALPARAM value attribute
captures either the logical filename or the value of a non-file
parameter. Thus the LFN does not contain any attributes, as it is just a
specialization of a parameter.

The METADATA table maps from (key, value) attribute pairs to LFNs. This
is a many-to-many relation: each LFN can have many attributes, and
multiple LFNs can have the same attribute.

Any TRANSFORMATION can be described by the executable and any number of
related FORMALPARAM. A database implementation also needs to model a
transformation ID.

The interrelationships among TRANSFORMATION, ACTUALPARAM, and
FORMALPARAM are the most complex, and are expressed in three bilateral
relationships:

-   A transformation is characterized by its parameters. The signature
    of the transformation includes input and output parameters, which
    need not be files. A transformation may have an arbitrary number of
    formal parameters and thus the relationship between TRANSFORMATION
    and FORMALPARAM is 1:N.

-   A transformation may have more than one derivation, using different
    values for the parameters, and as a set identified by their
    set-identifier, usually a number that is constant for the same
    related actual arguments.

-   The relationships from a transformation to its formal and actual
    parameters are not independent of each other. Each instantiation of
    an actual parameter maps to exactly one formal parameter describing
    the entry, as shown by the dashed line. On the other hand, there may
    exist more than one instantiation of a formal parameter for the same
    function in different actual parameter sets, as shown by the N:1
    relationship between the two parameter classes.

An alternative and perhaps better representation of the
interrelationships among the three classes would be as a single ternary
association. The transformation end would have a multiplicity of one,
the formal argument a multiplicity of N, and the actual argument a
multiplicity of M\*N. We could then view the transformation and formal
arguments as one block (called, for example, "process") to which one or
more actual parameter implementations may exist.

Regarding the notion of tracking transformation and derivation
[cost]{.mark}*:* We propose this as a means of grouping multiple sets of
actual parameters that reuse the same transformation template. The
thought is that for similar transformations, the machine type or some
kind of cost could be modeled, e.g. as additional relationship between
TRANFORMATION and DERIVED.

*Open Issue: reduce the confusion between LFN and parameter strings.*

# Advanced VDL Features

The features proposed in this section are ideas being considered for VDL
versions 2 and beyond. We describe them here as a record of proposals
for extending the power of VDL-1 that we have already developed
ourselves or in discussions with GriPhyN project members and other
colleagues, but that we do not feel are sufficiently mature for
inclusion in the current prototype.

## Execution Environments and Transformation Signatures

The transformation description needs to be augmented with as much
information as is practical to capture and store concerning the nature
and state of the environment in which a transformation was (or will be)
executed. This information has many layers of complexity below it,
extending deep into the realm of configuration management systems. A
proposal for the contents of a transformation description is \[[ref:
Deelman, Mehta]{.mark}\].

We propose to include into the transformation description a reference to
a "software execution environment" definition. This definition would
enrich the description of a transformation's signature with a
description of run-time attributes such as standard environment variable
settings for all applications within a project, the dynamic library
environment, and the standard files and directories that are expected to
be available within the environment. For example:

-   All the information about how the application was built.

-   All the information about what dynamic libraries were in the library
    search path for the executing application.

-   How each of those libraries was built.

-   All environment variable settings, and the names of all files
    directly or indirectly referenced by those environment variables.

-   Hardware node descriptions and change records.

Some of this information can be represented in a relatively standard
manner -- for example, information about the dynamic library state seen
by an executing application. The structure of deeper knowledge, however,
about versions of applications and the configuration management
mechanisms behind those applications, is by nature environment-specific,
whereas we seek to keep the VDS as general as possible. To strike the
right balance here, we expect to only embed support for, initially, the
POSIX execution model, then extend it to the Windows execution model,
and to provide generic linkages (for example, using environment-specific
opaque name-value pairs to allow environments to associate arbitrary
environment-specific data with transformations).

A similar approach to the one described above is also required to
capture information about the hardware execution environment that is
germane to the reproducibility of data. Such an environment is beyond
our scope to describe here, but is typified by the mechanisms that are
currently deployed in commercial network and systems management
frameworks, which record innumerable hardware attributes of large
networks, down to the levels of component types and serial numbers.

## Augmenting the Model with Job Execution Information

We propose to augment the descriptions of transformations and
derivations with information needed to execute programs within current
Grid frameworks.

The JOB clause defines run-time specifications for jobs to be executed,
for example, DAGman parameters, ClassAd specifications to the Condor
scheduling system, or RSL (resource specification language)
specifications to the GRAM component of Globus. Job execution
information can be supplied on the TR statement, the DV statement, or on
any statement that causes derivations to execute (such as get and
derive). This permits a wide range of specification power and
information abstraction.

For example, specifying job parameters on the TR statement would
encapsulate the knowledge of how a transformation *must* be executed
tightly with that transformation, hiding the knowledge so that
derivation specifications and derivation execution requests do not need
to know or supply this level of detail. But we also may want to explore
or permit the opposite direction: by deferring job specifications until
the time that a derivation is executed, (and supplying the JOB clause on
a get or derive statement) we make the data definitions independent of
the job execution environment -- a sort of deferred binding of this
information. Both approaches may have a place in a virtual data Grid,
depending on the diversity of execution environments present.

Job clauses could conceivably be coded in the form of nested name value
pair lists (much like a ClassAds \[[ref: Condor; Sudharshan]{.mark}\] or
RSL \[[Ref: GRAM]{.mark}\]

[]{.mark}

Site

-   how it should execute

-   where it should execute

-   where it did execute

## Tracking the Creation of Physical Files; File Equivalence

Every time a derivation is executed, actual physical files are produced
(even though the derivation record itself just tracks logical file
names). There may in many cases exist differences (sometimes acceptable,
other times not) between different physical copies of the same logical
file.

We seek a way to store and associate with every physical copy of a
logical file a full record of how that copy was produced: the
transformation, the job parameters used, the resources consumed, and a
digest of the contents of the file (in the form of a message digest such
as MD5.) This will require that we integrate with or provide linkages
between the schemas of the replica catalog and the virtual data catalog.

Closely related to this concept, we further propose to develop the
notion of *file equivalences*. For some transformations, we would
provide the following optional and mutually exclusive attributes:

-   each copy of a specific derived logical output file must be
    identical (verified or not is an option)

-   derived copies need not be identical (no verification)

-   derived copies need not be identical but must pass an equivalence
    validation test that is itself a transformation which produces no
    output or only logging output. This notion may be generalizable into
    a built-in, extensible paradigm for data product validity testing.

*Open issue: store a pointer to the actual derivation used to produce a
physical file name, with the physical file name record in the replica
catalog? Keep the derivation immutable once its associated with any
actual pfns? Can pfns be re-associated with a derivation? I think that
this section proposes a high-level solution to this open issue... (mw)*

*Open Issue: Suggest we consider creating a derivation-execution record
which describes each execution of a derivation: resources used; physical
copy created. So each PFN can be traced back to the derivation that
produced it. (ditto -- mw)*

## Transformations to Represent Data Capture

Transformation descriptions can also describe raw data capture
processes, which, while they are not produced by executing an
application, do in fact often have associated input data files on which
the raw capture was based. For example, data streaming out of a detector
in high energy physics colliders is typically dependent (for
interpretation and further processing) on files that describe the static
geometry, the measured calibrations, and the real time conditions and
settings of the detector. These files can be associated with raw data
files by describing them as input files to (i.e., data dependencies of)
a raw data capture "transformation".

## Augmenting the Model with Resource Cost Information

We propose to implement the following model for representing and
tracking execution cost:

-   Each TR will have a cost projection expression, which can be based
    on the values of CARGs and the sizes of dependent input files.

-   Each DV can contain a cost projection

-   Each DV execution record will contain an actual cost measurement for
    each invocation of the derivation.

The variables that will be cost-tracked could be:

resources {

start timestamp

end timestamp

cpu, io, netwk resources used

}

For resource records that represent projections, the start time will be
zero, hence the end timestamp will represent the expected duration of
the transformation's execution.

The cost is currently in terms of CPU seconds, but can, in the future,
be extended to cover data transfer and network I/O costs.

It is recognized as an open research problem that attributing network
utilization to a specific derivation is, while potentially of great
value to a Grid request planner, also a very complex problem.

## Adding Authentication and Authorization

We propose to augment the virtual data model with Globus Grid Security
Infrastructure (GSI) mechanisms that identify the Grid identity of
entities that make requests to the virtual data system, and Community
Authorization Service mechanisms that permit fine-grained policy-based
control over authority to use resources to make virtual data catalog and
manipulation requests.

We propose to handle issues of:

-   Who is requesting catalog access or derivation execution?

-   Who used what resources to do what? (logging)

-   What authorization checking needs to be done?

-   How does this relate to access to other catalogs and/or storage
    servers?

-   How does resource predictions or utilization relate to policies?

## Generating Virtual Data Derivation Specifications from Templates and Functions

Generators are scripting functions that can create a large number of
derivations from a parametric specification (i.e., directly from the
Transformation definition).

Templates could also be defined in the VDC which look like multi-stage
(multi-transformation) derivations but that can be used to more easily
create or specify other derivations. The introduction of templates and
compound transformations calls for the introduction of the *scope* of
connected identifiers, not just variables.

With a generator, we need to consider nested and named generation: A
generator t~7~ calls a generator t~6~ in its internal loop. Thus,
generators cannot be just simple macro expansions. Generators can
sometimes be viewed as special cases of compound transformations,
introducing the notion of *nesting* and *lambda functions.*

If we assume that each transformation, or essentially VDL itself, can be
expressed as a script, then a generator can either create new
derivations and/or new transformations from any scripting language.
Ultimately, it must be possible to integrate scripting with VDL in such
a way that they work in a mutually recursive fashion: a scripting
language could invoke a VDL API that might in turn contain scripting
language pieces etc.

Ideally, we seek a generator mechanism that is independent of scripting
language, but which could work with today's popular implementations:
Perl, Python, TCL, and various shells.

## Variable Length Parameter Lists, and Flexible Sequences

Many scientific application domains deal with data in sequences or
ranges that are inherent in the nature of the domain. Two notable
examples of this are data that is organized by time or by space. For
example, in the LIGO experiment, all raw data is collected in "frame"
files that are identified with a UTC timestamp denoting the start time
and end time of the particular observation. Climate data on the other
hand might be organized into volume units in the spherical coordinate
system of the earth's atmosphere, while data from an EOS system might be
gathered in segments that tile regions of the earths surface.

Transformations will often be designed to process a sequence of all
input files from a much larger collection that represent a specific time
period, a specific 3D conic section of the atmosphere or an ocean, or a
specific spherical region of the earth's surface. Geological data might
be similarly organized; bio-informatics data undoubtedly has numerous
inherent notions of sequence and subsequence.

To handle such data requests, we propose to augment the model with the
concept of a varying-length sequence of file names, chosen by an
application-specific name generating function or meta-database lookup.
The actual filenames that are part of such a sequence always need to be
determined by information from either metadata databases or from the
replica catalog. In most real-life applications, large data collections
are often incomplete, in that a few files from any sequence can often be
missing with no ill effects on large statistically based analyses.

This concept will enter into our model as follows:

-   Transformations can be coded which specify a sequence of files as a
    single unit in their file input-output parameter lists. (This will
    be similar to the "var args" notion of C, but with additional
    flexibility in that a sequence can appear anywhere in the list).

-   The sequence will be specified as a function with an
    application-specific string to denote the range of the sequence.
    This range can have an arbitrary number of parameters (for example,
    two to specify a time range, or six to represent a conic of the
    atmosphere -- min and max latitude/longitude, and min and max
    altitude.)

-   Applications will invoke an application-specific function to convert
    a data range into a sequence of possible file names.

-   The sequence will be processed to find the exact list of filenames,
    removing missing data sets.

-   The application will then process the filenames using generalized
    iterators that know how to deal with such a file list.

Sometime filenames will give ranges, sometimes not; either way its a
metadata function to map a range request onto a list of files. For
example, while in LIGO the filenames themselves indicate the time range
of the file, in general we can't count on this. Therefore, we propose
that the mapping from range to list of files be generalized into an
application-specific function.

We expect that such a model would incorporate:

-   Queries that match subranges

-   Argument types as both subrange specifications and expanded
    subranges

-   A notion of data types

## Data-type Based Transformation Templates

A new idea that was recently proposed and needs further examination is
that of providing datatype-based transformation templates based on the
paradigm of the "Make" command -- for example, to be able to specify a
transformation that knows how to transform a file of type "raw event
data" to type "reconstructed event data", much like a makefile specifies
a rule for translating a ".c" file into a ".o" file.

## Handling Tri-Modal Data Representation

Among the GriPhyN experiments, three data representation modes are
dominant: files, relational tables (in RDBMS's) and persistent object
structure (in OODBMS's). Universal underlying data representations such
as XML, which we think of as different from these three modes, and
potentially as unifying them, are also being deployed.

We feel that the mechanism we have described in this document to handle
file-based transformations and derivations extends quite naturally to
encompass all of these modes.

For example, lets posit that in a HEP experiment, summary "TAG"

## Linking Knowledge and Metadata Searches into the Model

As a final and most advanced stage of our anticipated virtual data
research, we propose to develop and test higher-level knowledge-based
representations of domain-specific knowledge, and create databases to
represent this knowledge and provide queries based on it.

This work will be done in stages, starting with simple queries on the
parameters of a collection of derivations. For example, the queries that
we have proposed in the base implementation of VDL-1 provide for
handling situations such as in this (greatly oversimplified) example:

> *Suppose a data generation process is generating a huge number of
> files, at very high resolution using a transformation called SQRT(x),
> which places a single result number into each file. Assume the process
> is being done for the range 1.0 to 10.0 in increments of 10\^-9.*
>
> *Now suppose a researcher wants to retrieve a file containing
> SQRT(3.0). The researcher would first query the VDC to see if a
> derivation-produced file containing SQRT(3) is available (app=SQRT,
> parameter-1=3.0). If so, the logical file name would be returned; if
> not, the researcher would then request that SQRT(3) be derived, and
> then returned.*

The ultimate generalization of this trivial case is to permit the
researcher to frame a query based on the attributes of the information
contained in derived files. A highly sophisticated knowledge-based
system would convert a query based on derived file attributes,
equivalences, derivabilities, and composabilities, into a set of
derivations based on cataloged transformations, and with knowledge of
data that had already been produced and that which could be produced.

Create some illustrative examples of this concept. Descibe it in
increasing layers of sophistication. Include some simple examples of
LIGO-like slice-dice-cut-join of frame files, where the "knowledge" is
mostly that of time range overlaps, and move on to several more
complicated examples.

Create a clean layer separation between knowledge, metatdata, virtual
catalog data, replication, and data.

Q(mdc) -\> list of files

# Open Issues

1.  The virtual data access language (search, get, derive, etc) needs to
    be specified in much more detail.

2.  A "materialization" needs to be explored, possibly with different
    flavors (all local, pool, etc.), that contains the job execution
    parameters.

3.  There exist no adaptor yet for non-file objects. Possibly we can
    describe access to such objects with the help of URI syntax.

4.  There is no good way yet to define that one file of a collection of
    files will be the input. Which file will be determined at run-time.

5.  There is no explicit support for filenames within a file. This could
    readily be added. Filename patterns as arguments are much more
    tricky.

6.  At some point soon we will need to re-assess the terminology here so
    that we can deal with tracking the derivation and replication of
    object-{sets, containers, collections, whatever}.

7.  Eventually the language will be spoken between components, and thus
    will use XML.

8.  Additional value proposition: recording IP and formulas

9.  Don't update transformations once a dependency was derived from it
    -- it must then remain immutable. Do we want to snapshot a
    transformation?

10. Distribution of the catalog architecture for speed and robustness.

11. Add in a permission model -- GSI etc. plus CAS -- who can run what,
    when.

12. Derivation record should contain an execution signature.

13. Explore whether there are multiple levels of dependencies -- for
    example, soft and hard. Hard is where data was actually read and
    processed to derived new data; soft if where a search was made over
    set X to select subset Y to process to produce Z. Z then has a hard
    dependencies on the files in Y but a soft dependeny on the file in
    X.

14. Search options that recurse down derivations are complex: its
    straightforward if we assume that no files exist, and show pure
    dependencies; its harder if we want to show what derivations need to
    be re-executed if we assume that some subset of the require input
    files exist at various sites in the Grid)

15. Deal with the issue of whether the 3 major catalogs (RC, MC, VDC)
    are (possibly separate) services here, and how they physically
    implement their logical linkages and maintain relational integrity
    between them.

# APPENDIX: VDL-1 LANGUAGE DEFINITION {#appendix-vdl-1-language-definition .unnumbered}

*To be developed for the next revision of this document.*

# Bibliography {#bibliography .unnumbered}

EN.REFLISTAcademic Press Dictionary of Science and Technology,
<http://www.harcourt.com/dictionary/browse/math.html>

[???What is reference 7 for?]{.mark}

[^1]: Throughout this document we evolve a formal description of the
    entity relationships within the virtual data catalog model in an
    object-oriented diagramming language taken from UML. This is an
    abstract view of the actual implementation, which is in fact
    implemented in an object-relational database, but which uses only
    traditional relational constructs for portability.