In an earlier article, we motivated the need for structure-agnostic, that is, nonnavigational, queries against XML documents. The conventional XML query languages require the users to know the structure of the XML documents and specify search conditions on the structure. However, the expressive flexibility of XML can give rise to many different representations and structures for the same document contents. A structure-agnostic query against XML documents is a very useful complement to the conventional navigation-based XML query languages. A structure-agnostic query language is very simple; however, the burden of processing a given query against XML documents of diverse representations and structures falls entirely on the query processor. In this article, we identify four key issues that arise in the automatic processing of structure-agnostic XML queries.