This paper describes techniques for building and exploiting indexes on
semistructured data: data that may not have a fixed schema and that may
be irregular or incomplete.  We first present a general framework for
indexing values in the presence of automatic type coercion.  Then based
on Lore, a DBMS for semistructured data, we introduce four types of
indexes and illustrate how they are used during query processing.  Our
techniques and indexing structures are fully implemented and integrated
into the Lore prototype.