Data warehousing accounts for a significant fraction of database use today. As XML becomes ever more popular, more and more XML data finds its way into data warehouse repositories. This paper examines the modeling mismatch between the tree structure of XML data model and the multidimensional model of a typical data warehouse, and proposes an XML warehouse model based on the multi-colored trees (MCT) logical data model that resolves the modeling issue naturally. Furthermore, this data model ameliorates some well-known modeling limitations of the XML data warehouse. To cope with ad-hoc OLAP queries, we extend bit-map join indices to the XML context. We then tackle the difference between the bit-map and the stack-based structural join processing paradigm popular in XML query processing, permitting both styles of query processing to be used seamlessly in consort to evaluate queries. We demonstrate experimentally the benefit of bit-map join indices for typical queries, and particularly those with low cardinality or high selectivity.

With increasing amounts of data being exchanged and even generated or stored in XML, a natural question is how to perform OLAP on XML data, which can be structurally heterogeneous (e.g., parse trees) and/or marked-up text documents. A core operator for OLAP is the data cube. While the relational cube can be extended in a straightforward way to XML, we argue such an extension would not address the specific issues posed by XML. While in a relational warehouse, facts are flat records and dimensions may have hierarchies, in an XML warehouse, both facts and dimensions may be hierarchical. Second, XML is flexible: (a) an element may have missing or repeated subelements; (b) different instances of the same element type may have different structure. We identify the challenges introduced by these features of XML for cube definition and computation. We propose a definition for cube adapted for XML data warehouse, including a suitably generalized specification mechanism. We define a cube lattice over the aggregates so defined. We then identify properties of this cube lattice that can be leveraged to allow optimized computation of the cube. Finally, we present the results of an extensive performance evaluation experiment gauging the behavior of alternative algorithms for cube computation.

XML schema design has two opposing goals: elimination of update anomalies requires that the schema be as normalized as possible; yet higher query performance and simpler query expression are often obtained through the use of schemas that permit redundancy. In this paper, we show that the recently proposed MCT data model, which extends XML by adding colors, can be used to address this dichotomy effectively. Specifically, we formalize the intuition of anomaly avoidance in MCT using notions of node normal and edge normal forms, and the goal of efficient query processing using notions of association recoverability and direct recoverability. We develop algorithms for transforming design specifications given as ER diagrams into MCT schemas that are in a node or edge normal form and satisfy association or direct recoverability. Experimental results using a wide variety of ER diagrams validate the benefits of our design methodology.

XML has a tree-structured data model, which is used to uniformly represent structured as well as semi-structured data, and also enable concise query specification in XQuery, via the use of its XPath (twig) patterns. This in turn can leverage the recently developed technology of structural join algorithms to evaluate the query efficiently. In this paper, we identify a fundamental tension in XML data modeling: (i) data represented as deep trees (which can make effective use of twig patterns) are often un-normalized, leading to update anomalies, while (ii) normalized data tends to be shallow, resulting in heavy use of expensive value-based joins in queries.Our solution to this data modeling problem is a novel multi-colored trees (MCT) logical data model, which is an evolutionary extension of the XML data model, and permits trees with multi-colored nodes to signify their participation in multiple hierarchies. This adds significant semantic structure to individual data nodes. We extend XQuery expressions to navigate between structurally related nodes, taking color into account, and also to create new colored trees as restructurings of an MCT database. While MCT serves as a significant evolutionary extension to XML as a logical data model, one of the key roles of XML is for information exchange. To enable exchange of MCT information, we develop algorithms for optimally serializing an MCT database as XML. We discuss alternative physical representations for MCT databases, using relational and native XML databases, and describe an implementation on top of the Timber native XML database. Experimental evaluation, using our prototype implementation, shows that not only are MCT queries/updates more succinct and easier to express than equivalent shallow tree XML queries, but they can also be significantly more efficient to evaluate than equivalent deep and shallow tree XML queries/updates.

XML has become ubiquitous, and XML data has to be managed in databases. The current industry standard is to map XML data into relational tables and store this information in a relational database. Such mappings create both expressive power problems and performance problems.In the TIMBER [7] project we are exploring the issues involved in storing XML in native format. We believe that the key intellectual contribution of this system is a comprehensive set-at-a-time query processing ability in a native XML store, with all the standard components of relational query processing, including algebraic rewriting and a cost-based optimizer.