

Zorba XQueryP Design Specification
----------------------------------

Version 0.1
Paul Pedersen
Dec. 15, 2006



This is a very early first-cut document intended to initiate
the process of establishing exact requirements.



1. Query Engine

The Query Engine receives XQueryP requests, parses them, optimizes 
them, prepares a plan of execution, executes the plan, and replies to 
the query request with the result sequence.  This subsystem in turn 
consists of three different components: Parser, Optimizer and 
Executor. 

	1.1 Parser
		- a flex/bison/symtab triple creates and manipulates
			a parse tree consisting of parsenodes

	1.2 Normalizer
		- maps XQueryP parse tree, which represents surface syntax,
			into the expression tree, which represents the XQuery
			semantic model [http://www.w3.org/TR/xquery-semantics/]

	[1.3 Optimizer
		- rewrite optimizer, includes rules for:
			1.2.1	common/superfluous subexpression elimination
			1.2.2	constant folding
			1.2.3 index optimizations
			1.2.4	join optimizations
			1.2.5 expression substitutions
			1.2.6 expression annotations]

	1.5 Types and Values
		- the subsystem for managing XQuery types and values, excluding the
			full schema type definition system, but including all the XSD
			primitive and derived types as specified in the XQuery 1.0 
			Data Model document [http://www.w3.org/TR/xpath-datamodel/].

				AnyURI, Base64Binary, Boolean, Byte, Date, DateTime, Decimal, 
				Double, Duration, ENTITIES, ENTITY, Float, GDay, GMonth, GMonthDay, 
				GYear, GYearMonth, HexBinary, IAnySimpleType, ID, IDREF, IDREFS, 
				Int, Integer, Language, Long, NCName, NMTOKEN, NMTOKENS, NOTATION, 
				Name, NegativeInteger, NonNegativeInteger, NonPositiveInteger, 
				NormalizedString, PositiveInteger, Short, String, Time, Token, 
				UnsignedByte, UnsignedInt, UnsignedLong, UnsignedShort, QName

		- use Apache Axis-derived code

	1.6 Context API
		- a hierarchy of runtime context objects containing the union
			XQuery 1.0 static and dynamic contexts, diagnostic context,
			and implementation-specific configuration.

	1.7 Function Library
	  - minimal subset
		- as specified in the XQuery 1.0 Functions and Operators
			document [http://www.w3.org/TR/xpath-functions/].
		- includes a function library API for adding functions
		- try to use sleepycat-derived code here




2. Storage Manager Interface

The Storage Manager is the backend of the system. This subsystem deals 
with persistent and efficient storage and retrieval of data.  The types 
of data handled by storage manager include: XML fragments, text nodes,
indexes, logs, and dictionaries.

	2.1 Data API interface
		- pure 'item' iterator interface
		- item iterator composition algebra
		- compliant with the XQuery 1.0 Data Model document (XDM)
			[http://www.w3.org/TR/xpath-datamodel/]

	2.2 Index API interface
		- all indexes are specified as XQueryP functional indexes, (i.e.)
			as stored views of some pre-configured XQueryP query, including
			full-text queries describing ordered or unordred token n-grams
			[http://www.w3.org/TR/xquery-full-text/].




3. Basic Buffer Manager

The Buffer Manager lies in between the query engine and storage 
manager.  This subsystem is responsible for memory management.
It performs caching of data in the Buffer Cache for fast retrieval.
To supply the requested data to the query engine, it caches the active 
part of the data from the data files in main memory and performs the 
necessary replacement of data to and from the storage manager. 
The Buffer Manager schedules block writes to optimizes I/O performance.
We model this system on the MySQL Buffer Manager.

	3.1 BufferPool 

	3.2 BufferCache




4. Basic Process Manager

The Process Manager performs two functions:

	4.1 managing external user connections:  this involves modules for
			network connection management with clients and dispatching user
			connections;

	4.2 synchronization among competing tasks and processes:  this
			involves modules for multi-threading, thread locking and
			performing thread safe operation. 




[5. Recovery Manager

The Recovery Manager keeps copies of data for retrieval later, in case
of system failures.  It also performs logging of commands that modify
the data and other significant events inside the database.  The
Recovery Manager contains subsystems:

	5.1 Logger
		- system and application event logs

	5.2 Backup
		- data/index block copying

	5.3 Recovery
		- redo/undo logs]




[6. Transaction Control]

The function of the Transaction Control subsystem is to facilitate 
concurrency in data access. This subsystem provides a locking facility 
to ensure that multiple concurrent users access the data in a 
consistent way. The transaction control consists of the Lock Manager 
component. 




[7. External service API
	7.1 Web Services API
	7.2 Java and C++ connectors]




8. Data source API
	8.1 XML data source
		- non-validating XML parser
		- use Xerces, Lark (Jim Bray), or tagsoup-derived code

	8.1 HTML data source
		- robust, repairing parser
		- use tagsoup-derived code

	8.1 RSS data source
		- robust, repairing parser
		- use tagsoup-derived code



9. Utilities

This subsystem includes OS abstract routines for:
	9.1  file and socket I/O
	9.2  memory allocation/de-allocation
	9.3  memory mapping
	9.4  threads
	9.5  readers-writers locks
	9.6  codec routines
	9.7  generic caches
	9.8  hash functions
	9.9  string manipulation
	9.10 generic quicksort/heapsort
	9.11 (persistent) hashmap
	9.12 (persistent) heap
	9.13 (persistent) queue
	9.14 (persistent) vector


10. Apache module
