In semistructured databases there is no schema fixed in advance. To
provide the benefits of a schema in such environments, we introduce
DataGuides: concise and accurate structural summaries of
semistructured databases. DataGuides serve as dynamic schemas,
generated from the database; they are useful for browsing database
structure, formulating queries, storing information such as statistics
and sample values, and enabling query optimization. This paper
presents the theoretical foundations of DataGuides along with an
algorithm for their creation and an overview of incremental
maintenance. We provide performance results based on our
implementation of DataGuides in the Lore DBMS for semistructured data.
We also describe the use of DataGuides in Lore, both in the user
interface to enable structure browsing and query formulation, and as a
means of guiding the query processor and optimizing query execution.