Abstract: Unlike in conventional databases, queries on XML stream data are bounded by not only the memory capacity but also the real time processing. Based on the Hole-Filler model, a path frequency tree (PFT) is defined according to the statistic information on queries about XML to set out a sibling-based document fragmentation policy including corresponding algorithm. Then, an alternative membership-based document fragmentation policy and corresponding algorithm are proposed. Both algorithms can effectively enhance the utilization and cohesion of XML fragments. Testing results showed that the PFT-based document fragmentation algorithms perform well on query cost and other properties.