tauXSchema | Internal / TemporalValidation

Overview of Paper

This section last updated on June 8, 2010 by sthomas

Target Venue: TOIT
Authors: Steve, Curtis, Rick, Rui
Key question: Which is better at validating temporal constraints: XML Schema or the Temporal Validator? We measure "better" by:
- Number of constraints that can be validated
- Speed of validation
- Size (on disk) of temporal documents and representational schema
Challenge #1: We intuitively showed in my Master's thesis that XML Schema alone is not sufficient for validating most temporal constraints. We want to formalize this argument somehow to provide a proof (or proof outline) that XML Schema lacks the ability. (We spent a little bit of time trying to go down this road last year, but quickly realized that this might be a big effort.)
Challenge #2: We will augment temporal schemas with XQuery, so that XML Schema alone is able to validate some (or all) temporal constraints.
Challenge #3: We want to have a robust experiment design:
- Large, random temporal documents (based on Dengfun Gao's tools, which were based on XBench)
- Test several instances of each constraint type (based on a detailed and consistent scenario/example)
- Test several types of "temporal scenarios": slices with large variation in size; slices with large variation in number of elements; slices with minimal changes; etc.
- Consider physical annotations as well as temporal annotations
- Do many repetitions to reduce any bias in the runtime metric
Challenge #4: Do we have to re-implement the tools to use SAX, if the testing scenarios become too big?

This section last updated on June 8, 2010 by sthomas

Introduction/Motivation
Background
- Temporal Documents/Constraints
- tauXSchema
Approach
- XML Schema
  - (Why XML Schema doesn't work)
  - (Modifying XML Schema with XQuery)
- Temporal Validator
Experiments
- Scenario Description
- Measures/Metrics
- Results
Discussion of Results
- Conclusions
- Threats to Validity
- Recommendations
Conclusion

Steve, Rick, Rui
Notes and Decisions

Rui has outline his synopsis proposal (https://docs.google.com/Doc?docid=0AUYmVArSs9kTZGZnN3NwajNfNDNkZnJycWpjcw&hl=en). Everyone agrees that the design looks good, and Rui will decide if hash tables are better than sorted lists for storing referential integrity keys.
Steve has imported all of Dengfeng's auxiliary functions for tXQuery, and gotten them to run in Galax. He has also written an example (current) XQuery for all four types of constraints.
Steve has created a repository for this paper and the related experiments in the Iowa repository, under docs/val (for VALidation).
Due to time constraints and pending deadlines in other projects, Rui will halt his implementation until after September 10.

TODOS

Steve, Rick, Curtis, Rui
Notes and Decisions

Rui will continue to work on the SAX implementation and synopses, while in parallel Steve works on formulating the XQuery templates and their necessary transformations. Steve can eventually start running small test cases, which he can pass to Rui so that Rui can test the validator on the same test cases.
Rui will need to consider content-constant constraints, which can be added to any of our four types. The synopses must deal with this somehow.
Schema versioning support is still limited in the tools. However, schema versioning can be implemented as a wrapper to each tool, calling the tool for each schema constant period. Thus, we will continue work on the tool (SAX), and address schema versioning later.

TODOS

~~Steve: Update wiki.~~
~~Rui: think more about SAX implementation and synopses, and send email to group with a working example~~
~~Steve: learn more about XQuery, and how to transform non-temporal queries into sequenced queries. Also, learn about denotational semantics.~~
~~Steve: Create SVN repository for paper and experiments (possible at Queen's? Can use Iowa for now)~~
~~Next Meeting: Tuesday, August 10 @ 4pm EDT (1pm MST, 2pm MDT)~~

Steve, Rick, Curtis, Rui
Notes and Decisions

Will consider journals in the following order: TOIT, VLDBJ, TKDE, TODS, SP+E, InforSys, WWW Journal. (Hopefully we won't have to walk down the whole list!)
Formally proving that XML Schema is incapable of validating some temporal constraints will be hard, so we won't tackle it, at least not yet. We will stick with the intuition-level counter examples that are present in Steve's thesis.
We need to be clear about our independent and dependent variables within our experimental design.
Need to investigate XQuery tools. Possibilities are eXist and MonetDB (for full-scale DBMS capabilities) and Saxon, XQJ, Qizx for lighter-weight tools.
Need to decide whether we will invoke XQuery via an API (called from the tXScheme tools) or from the command line (via a system command).
We talked about using SAX for validation within the tools, since it will be able to better handle large squashed documents. A key idea to make this work is building a so-called synopsis of the temporal document, which basically is the minimum amount of info needed to validate the set of constraints (such as number of time an item has occurred so far, and the timestamps at which it occurred). This brings the issue incremental vs. full validation of a squashed temporal document. Our preference is for incremental validation, where a synopsis is first build on the temporal document, and then subsequent slices can be validated on the fly using the synopsis (a new feature for tXSchema!)

TODOS

~~Rick: Investigate tXQuery. Can it help us somehow?~~
~~Rui: Think about implementing SAX into tXSchema's validator. How much work will be required?~~
~~Steve: Think more about XQuery, and the available tools. How will everything fit together (ie, when does the XQuery get fired?)~~
~~Steve: Read Dengfeng Gao's disseration.~~
~~Next Meeting: Tuesday, June 15 @ 4pm EDT (1pm MST, 2pm MDT).~~