Abstract: Subtree results construction is a core problem in keyword query processing over XML data，for which computing the set of relevant keyword nodes (RKN) for each subtree’s root node will greatly affect the overall system performance. Considering that existing methods cannot correctly identify RKN for ELCA semantics，the definitions of RKN and the RKN-Base algorithm were proposed，which can correctly judge whether a given node is an RKN of some ELCA node by sequentially scanning the set of inverted lists once. As RKN-Base cannot avoid processing all useless nodes，an optimized algorithm，namely RKN-Optimized，was then proposed，which computes RKN sets based on the set of ELCA nodes, rather than the set of inverted lists as RKN-Base does. As a result，RKN-Optimized avoids processing useless nodes, and reduces the time complexity. The experimental results verified the efficiency of the proposed algorithms.