Access control policies for XML typically use regular path expressions such as XPath for specifying the objects for access-control policies. However such access-control policies are burdens to the query engines for XML documents. To relieve this burden, we introduce static analysis for XML access-control. Given an access-control policy, query expression, and an optional schema, static analysis determines if this query expression is guaranteed not to access elements or attributes that are hidden by the access-control policy but permitted by the schema. Static analysis can be performed without evaluating any query expression against actual XML documents. Run-time checking is required only when static analysis is unable to determine whether to grant or deny access requests. A side effect of static analysis is query optimization: access-denied expressions in queries can be evaluated to empty lists at compile time. We further extend static analysis for handling value-based access-control policies and introduce view schemas.

On the basis of regular tree grammars, we present a formal framework for XML schema languages. This framework helps to describe, compare, and implement such schema languages in a rigorous manner. Our main results are as follows: (1) a simple framework to study three classes of tree languages (local, single-type, and regular); (2) classification and comparison of schema languages (DTD, W3C XML Schema, and RELAX NG) based on these classes; (3) efficient document validation algorithms for these classes; and (4) other grammatical concepts and advanced validation algorithms relevant to an XML model (e.g., binarization, derivative-based validation).

Access control policies for XML typically use regular path expressions such as XPath for specifying the objects for access control policies. However such access control policies are burdens to the engines for XML query languages. To relieve this burden, we introduce static analysis for XML access control. Given an access control policy, query expression, and an optional schema, static analysis determines if this query expression is guaranteed not to access elements or attributes that are permitted by the schema but hidden by the access control policy. Static analysis can be performed without evaluating any query expression against an actual database. Run-time checking is required only when static analysis is unable to determine whether to grant or deny access requests. A nice side-effect of static analysis is query optimization: access-denied expressions in queries can be evaluated to empty lists at compile time. We have built a prototype of static analysis for XQuery, and shown the effectiveness and scalability through experiments.

Query languages for XML often use path expressions to locate elements in XML documents. Path expressions are regular expressions such that underlying alphabets represent conditions on nodes. Path expressions represent conditions on paths from the root, but do not represent conditions on siblings, siblings of ancestors, and descendants of such siblings. In order to capture such conditions, we propose to extend underlying alphabets. Each symbol in an extended alphabet is a triplet (e1, a, e2), where a is a condition on nodes, and e1 (e2) is a condition on elder (resp. younger) siblings and their descendants; e1 and e2 are represented by hedge regular expressions, which are as expressive as hedge automata (hedges are ordered sequences of trees). Nodes matching such an extended path expression can be located by traversing the XML document twice. Furthermore, given an input schema and a query operation controlled by an extended path expression, it is possible to construct an output schema. This is done by identifying, where in the input schema the given extended path expression is satisfied.