DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases

Abstract

In F7Times-ItalicF7S38semistructured 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 ofsemistructured databases. DataGuides serve as dynamic schemas, generated from the database; they areuseful for browsing database structure, formulating queries, storing information such as statistics andsample values, and enabling query optimization. This paper presents the theoretical foundations of DataGuides along with algorithms for their creation and incremental maintenance. We provideperformance results based on our implementation of DataGuides in the Lore DBMS for semistructureddata. We also describe the use of DataGuides in Lore, both in the user interface to enable structurebrowsing and query formulation, and as a means of guiding the query processor and optimizing queryexecution.F5S58