  As probabilistic data management is becoming one of the main research focuses
and keyword search is turning into a more popular query means, it is natural to
think how to support keyword queries on probabilistic XML data. With regards to
keyword query on deterministic XML documents, ELCA (Exclusive Lowest Common
Ancestor) semantics allows more relevant fragments rooted at the ELCAs to
appear as results and is more popular compared with other keyword query result
semantics (such as SLCAs).
  In this paper, we investigate how to evaluate ELCA results for keyword
queries on probabilistic XML documents. After defining probabilistic ELCA
semantics in terms of possible world semantics, we propose an approach to
compute ELCA probabilities without generating possible worlds. Then we develop
an efficient stack-based algorithm that can find all probabilistic ELCA results
and their ELCA probabilities for a given keyword query on a probabilistic XML
document. Finally, we experimentally evaluate the proposed ELCA algorithm and
compare it with its SLCA counterpart in aspects of result effectiveness, time
and space efficiency, and scalability.
