XML is an emerging standard for data representation and exchange on the
World-Wide Web.  Due to the nature of information on the Web and the
inherent flexibility of XML, we expect that much of the data encoded in
XML will be semistructured: the data may be irregular or incomplete, and
its structure may change rapidly or unpredictably.  This paper describes
the query processor of Lore, a DBMS for XML-based data supporting an
expressive query language.  We focus primarily on Lore's cost-based
query optimizer.  While all of the usual problems associated with
cost-based query optimization apply to XML-based query languages, a
number of additional problems arise, such as new kinds of indexing, more
complicated notions of database statistics, and vastly different query
execution strategies for different databases.  We define appropriate       
logical and physical query plans, database statistics, and a cost model,
and we describe plan enumeration including heuristics for reducing the
large search space.  Our optimizer is fully implemented in Lore and
preliminary performance results are reported.