Research On Task Scheduline Of Xquery Parallelization

With the development of Internet, XML has been widely used in data exchangingand storage for its self-descriptive, semi-structured characteristics. Along with theincreasing amount of XML data, how to improve the performance of XML query hasbecome an important research field. XQuery is a W3C recommendation for XMLquery language with powerful query function and description ability. As a functionallanguage, XQuery describes the calculation through the combination of expressions.According to the dependencies between the expressions, various forms of parallelismcan be applied to XQuery programs, such as task parallelism, data parallelism andpipeline parallelism. In recent years, due to the development of parallel technology,the ability to take advantage of multi-thread technology to improve the efficiency ofXQuery has become an important issue in XML data query. Utilizing the implicitparallelism existed in XQuery programs become to an important way for the tasksscheduling in XQuery’s automatic parallel implementation.Exploiting parallelism is very essential in parallel programming. Thus manyscheduling algorithms are proposed. However, the current studies are mostly based onsingle or two kinds of parallelism in parallel system, could not make full use of themulti-parallelism in XQuery. They are also could not support the dynamic schedulingfor uncertain arrival of the ready task in XQuery. Based on those problems, this paperstudies the scheduling problem in the implementation of the XQuery. A multi-taskmapping/scheduling algorithm using task dependence degree and task cost as priorityis proposed for the semi-structured characteristic of XML and the complicatedstructure of XQuery, which can deal with multi-parallelism existed in XQuery.According the current system resource and task state, it can also meet the dynamicscheduling requirement. An automaton model is established to optimize the pipelineparallelism by making use of the idle time between pipeline steps, which supports themigration of pipeline tasks between different work states. The experimental resultsshow that our approach could improve the performance of the XQuery processing andmake full use of resources.