Research On Implementation Of FLW Query Algebra

With the development of Internet, more and more data are descripted, exchangedor stored by XML. As the recommendation of W3C, XQuery is drawing an increasingattention. Since the relationship between XQuery and XML database is just like thatbetween SQL and relational database, a powerful XML query algebra like relationalalgebra is necessary for the efficient implementation of XQuery.Most of the existing XML query algebras focus on how to express the semanticsof XQuery correctly and completely to ensure that the logic optimization commonlyseen in relational database is applicable in XML query. However, they can not meetthe optimization demand of multi nested query in XQuery. This paper proposes a newXML query algebra system, the FLW query algebra, to meet this demand. FLW queryalgebra is composed of logical algebra and physical algebra. In logical algebra, thereare some logical operators, which are used to express the logic relationship of query.However, query implementation is not involved. The logical operators are thefoundation of logic optimization. In physical algebra, there are some physicaloperators to realize the query operations, which include join, filter and enumeration.This paper also puts forward FLW witness tree, the data model of FLW queryalgebra. This is a data model with a tree structure. Compared with XDM, the datamodel of XQuery, this kind of data model can reduce the redundant storage of dataand minish the intermediate result of query. In addition, efficient XML tree patternquery technology can be used easily in FLW witness tree. The implementation ofphysical operators based on FLW witness tree is also be introduced in this paper.The designs above are all realized in SelabQuery system, which is a XML queryengine. We also run a set of XQuery under the environment of FLW query algebra andXQA query algebra, which was used in SelabQuery system earlier. We record the timeof execution of the query. The result of the experiment shows that for the XQueryquery with a multi-data source, FLW query algebra is better than XQA query algebranot only in running time, but also in the usage of internal memory.