JUCS - Journal of Universal Computer Science 16(20): 3043-3072, doi: 10.3217/jucs-016-20-3043
XML Database Transformations
expand article infoKlaus-Dieter Schewe, Qing Wang§
‡ Software Competence Center Hagenberg and Johannes Kepler University Linz, Hagenberg, Austria§ University of Otago, Dunedin, New Zealand
Open Access
Abstract
Database transformations provide a unifying umbrella for queries and updates. In general, they can be characterised by five postulates, which constitute the database analogue of Gurevich's sequential ASM thesis. Among these postulates the background postulate supposedly captures the particularities of data models and schemata. For the characterisation of XML database transformations the natural first step is therefore to define the appropriate tree-based backgrounds, which draw on hereditarily finite trees, tree algebra operations, and extended document type definitions. This defines a computational model for XML database transformation using a variant of Abstract State Machines. Then the incorporation of weak monadic second-order logic provides an alternative computational model called XML machines. The main result is that these two computational models for XML database transformations are equivalent.
Keywords
Abstract State Machine, computation background, database transformation, eXtensible Markup Language, Monadic Second-order Logic, Tree Algebra