Keyword search on XML documents has received considerable research interests recently. Most existing methods put their emphases on the document side, and focus on how to utilize structural properties of XML documents to produce better search results, more effective ranking methods, or more efficient algorithms. However, effective XML search requires a full understanding of not only XML documents but also XML keyword queries, whereas little attention has been paid to the latter. In this paper, we focus on the query side of XML keyword search instead of the document side. We show that keyword queries have structures, and define a concept called keyword query with structure (QWS) to capture query structure. As query structure provides hints about the intent of the query, it can be used to improve the quality of the search results. We exploit some key observations to characterize the structure in a keyword query and show how to refine search results with the assistance of query structure. In order to take the benefits of query structure, we design a query processing approach to produce results given a keyword query. It first derives some QWSs based on heuristics, and computes results of these queries, then expands the results if needed. We implement the proposed methods and conduct comprehensive experiments. Experimental results verify the effectiveness of our methods. (C) 2013 Elsevier Inc. All rights reserved.