[Prev][Next][Index][Thread]
Paper announcement: Validation and boolean operations for attribute-element constraints
Dear folks,
We are pleased to announce the availability of our new paper
Validation and boolean operations for attribute-element constraints
by Haruo Hosoya and Makoto Murata. This paper is concerned with core
algorithms that are needed in implementing a statically typed language
for XML processing. The PS file of the paper can be retrieved from:
http://www.kurims.kyoto-u.ac.jp/~hahosoya/papers/attelm.ps
Comments and questions are welcome.
Cheers,
Haruo Hosoya
Makoto Murata
----------------------------------------------------------------------
Abstract:
Algorithms for validation and boolean operations play a crucial role
in developing XML processing systems involving schemas. Although
much effort has previously been made for treating {\em elements}, very
few studies have paid attention to {\em attributes}. This paper
presents a validation and boolean algorithms for Clark's
attribute-element constraints. Although his mechanism has a prominent
expressiveness and generality among other proposals, treating this is
algorithmically challenging since naive approaches easily blow up even
for typical inputs. To overcome this difficulty, we have developed
(1) a two-phase validation algorithm that uses what we call {\em
attribute-element automata} and (2) intersection and difference
algorithms that proceed by a ``divide-and-conquer'' strategy.