March 11, 2002 -  Jerome & Mary 

      Disclaimer: This document is out of date. 

               ****************************************************
               * Galax Version 0.1alpha Developer's Documentation *
               ****************************************************

CONTENT
=======

   - OVERVIEW
   - TERMINOLOGY
   - SYSTEM ARCHITECTURE
   - COMPONENTS AND FILES

OVERVIEW
========

The Galax Developer's Documentation provides a high-level overview on
Galax System. The purpose of this document is to: 

  (1) quickly locate particular modules (eg. evaluation engine and
  schema import) and the sections of the XQuery working drafts that
  define their functionality; and

  (2) understand the architecture of an XQuery system, which
  implements the relevant standards proposed by W3C Query Working
  Group.

TERMINOLOGY
===========

AST:           Abstract Syntax Tree

WG:            Working group

Full XQuery:   Refers to the language generated by the XQuery Grammar
               in the XQuery 1.0 standard, provided by the W3C XML
               Query WG.
               (http://www.w3.org/TR/xquery/#section-XQuery-Grammar)

Core XQuery:   Refers to the language generated by XQuery Core Syntax in
               the Formal Semantics document, provided by the W3C XML
               Query WG.
               (http://www.w3.org/TR/query-semantics/#sec_grammar)

Datamodel:     Refers to the XML Query Data Model (Feb-15-2001), provided
               by the W3C XML Query WG.
               (http://www.w3.org/TR/2001/WD-query-datamodel-20010215/)

Formal Semantics:
               XQuery 1.0 Formal Semantics provided by the W3C XML
               Query WG. (http://www.w3.org/TR/query-semantics/) The
               formal semantics is defined on the datamodel and the
               Core XQuery.


SYSTEM ARCHITECTURE
===================

System Design:

              Full XQuery          XQuery Build-in functions
                  |                           |
                  V                           V
                 +-----------------------------+
        *********|    Full XQuery Parser       |
        *        +-----------------------------+
        *         *              |       
        *         *              V       
        *         *       Full XQuery AST
        *         *              |    
        *  1.Import schema       |   
        *  2.Open documents      V
        *         *         +--------+
        *         **********|        |------------------+
        *                   | Mapper |                  |
        ******** 1.********>|        |------+           |
        *                   +--------+      |           | 
        *                                   |           V
        *                   +--------+      |       Core XQuery AST    
        ******** 2.********>| Loader |      |   (includes inline types)
                            +--------+      |                     |
                                 |          V                     |
                                 |         Imported types         |
                                 |                     |          |
                             Datamodel                 V          V
                                of                  +-----------------+
                             documents              |   Type System   |
                                 |                  +-----------------+  
            Datamodel            |                          |
               of                |                   Type checked Core
             result              V                      XQuery AST
+----------+       +-------------------+                    |
|Serialize |<------| Evaluation Engine |<-------------------+ 
+----------+       +-------------------+

OVERVIEW:

Galax takes a Full XQuery as input. Full XQuery can contains statement
on opening a document and importing a XML Schema. Galax has a parser
for parsing the Full XQuery and XML document, and therefore XML
Schema. For Full XQuery, the parser returns its Full XQuery AST.

XML document is parsed into Full XQuery AST and then mapped to the
Datamodel. The Datamodel representation of the document is loaded onto
the main memory during evaluation. This is the method for the current
Galax system to load a document. The DOM interface, or interface to
exisiting parsers, are not supported yet.

Full XQuery syntax is rather complex so that the W3C proposed the Core
XQuery and the Datamodel. The Core XQuery is the subset of Full XQuery
yet has the same expressive power. The evaluation semantics and the
typing system are defined on the Core XQuery and the Datamodel.

Galax has a mapper which performs two tasks. (1) it takes a Full
XQuery AST from the parser and returns the corresponding Core XQuery
AST. This mapping can be found in the Formal Semantic document.
(http://www.w3.org/TR/query-semantics/#sec_core_mapping_declarations)
(2) it takes an XML Schema, represented in Full XQuery AST and returns
the corresponding type declarations.

So much for parsing and mapping.

Typing is done on Core XQuery AST. The static semanticsis/typing
inference rules defined in Static Semantics in the Formal Semantic
document
(http://www.w3.org/TR/query-semantics/#sec_typerules).

Galax has an evaluation engine on Core XQuery AST. This implements the
dynamic semantics in the Formal Semantic document
(http://www.w3.org/TR/query-semantics/#sec_dynamic).

The evaluation result is represented by the Datamodel. A print module
is designed for print the Datamodel. This is also a logical place to
put all the printing functions for AST (for debugging and analysis
purposes) and the typing input and result.

Remarks: Galax has a few modules, not included in the W3C proposals,
for practical reasons. For instance, it has a C API which allows C
programs to call the Galax system. It also has a web interface. Not
required, but it's just cool. ;)

COMPONENTS AND FILES
====================

In the previous section, we presented the system architecture of the
Galax system. We list the (important) source files grouped by the
components. Some components only appears in this section because they
are rather low level.

+==========================================================================+
|COMPONENTS        | FILES                                                 |
+==================+=======================================================+
|Full XQuery Parser| parsing/xquery_parser.mly (Full XQuery Grammar)       |
|                  | parsing/xquery_lexer.mll  (Lexer)                     |
|                  | parsing/parseutil.ml(i)   (Utilities functions for    |
|                  |                            parsing)                   |
+==================+=======================================================+
|Mapper            | schema/schemamapping.ml(i) (Mapping function for XML  |
|                  |                             Schema)                   |
+==================+=======================================================+
|Loader            | datamodel/load.ml(i)                                  |
+==================+=======================================================+
|Type System       | schema/schema.ml(i) (Internal representation of XML   |
|                  |                      Schema)                          |
|                  | schema/subsumption.ml(i)  (Subsumption algorithm *)   |
|                  | fsa/glushkov.ml(i)        (Inclusion of regular       |
|                  |                            expression   )             |
+==================+=======================================================+
|Datamodel         | datamodel/datamodel.ml(i)                             |
+==================+=======================================================+
|Print             | parsing/print.ml(i)                                   |
+==================+=======================================================+
|AST               | parsing/xasyn.ml(i) (AST for Full XQuery, Core XQuery |
|                  |                      and XQuery Types)                |
|                  | parsing/astutil.ml(i)(Constructors, accessors for AST)|
+==================+=======================================================+
|Build-in Functions| stdlib/bltin.ml(i)                                    |
+==================+=======================================================+

*  Gabriel M. Kuper and Jerome Simeon. Subsumption for XML Types. In 
   Proceedings of International Conference on Database Theory (ICDT) 2001

Feedback and comment please email to:
                     simeon@research.bell-labs.com

Byron
Oct-26-01.


About memory management
=======================


Currently:

  XML Documents   ---> 'standard' parser   ---> XML AST
   XML AST        ---> Well-formed loader  ---> XQuery data model  ~~  DOM representation
   XML AST        ---> Validating loader   ---> XQuery data model
XQuery data model ---> Evaluation          ---> Result data model

                          ^
                          |

  XML Schema            Query --> Typing -->

-----------------------------------------------------------------------------------

  XML Documents    ---> SAX parser              ---> XML-event stream
  XML-event stream ---> SAX Well-formed loader  ---> XQuery data model  ~~  DOM representation
  XML-event stream ---> SAX Validating loader   ---> XQuery data model

-----------------------------------------------------------------------------------


  XQuery file     	  ---> Parsing        ---> XQuery AST
  XQuery AST      	  ---> Normalization  ---> XQuery core AST
  XQuery core AST 	  ---> Typing         ---> 'Typed' XQuery core AST
  'Typed' XQuery core AST ---> Simplification ---> 'optimized' 'typed' XQuery core AST
  'optimized' 'typed' XQuery core AST ---> Evaluation ---> result 

					       ^
					       |

                                           Document



Rewriting rules
================

    let $x := E1 return E2
    used_count($x,E2) = 0
    E1 cannot fail
  --------------------------
    E2

    let $x := E1 return E2
    used_count($x,E2) = 1
  ----------------------------
    E2[$x / E1]

    typeswitch E0 
      case T1 return E1
      case T2 return E2
      ....
      default return En

    E0 : T0
    T0 <: T1 
  ----------------------------     
    E1    

    typeswitch E0 
      case T1 return E1
      case T2 return E2
      ....
      default return En

    E0 : T0
    T0 <: (T1 |... | Tk ) 
  ----------------------------     
    typeswitch E0 
      case T1 return E1
      case T2 return E2
      ....
      case Tk-1 return Ek-1
      default return Ek

