Planning and heuristic optimization of queries

Search Computing queries are expressed in a high-level conjunctive form, that declaratively lists which services are to be invoked and how to compose them. In order to be executed, queries need to be translated into a low-level execution plan consisting of a DAG (directly acyclic graph) of functional nodes (e.g. service invocation nodes, joins, selections, sort nodes, etc.) interconnected by both data and control flows. Queries can be translated to a number of different execution plans. The planning process should, therefore, also select a good execution plan among the possible ones to minimize certain cost metrics, by means of heuristics or branch and bound techniques evaluated on available Web service statistics.

The aim of the proposed thesis is to extend and improve an existing solution for the planning and heuristic optimization of Search Computing queries, by:

• devising a flexible query planning and optimization methodology that deals with different service statistics and cost metrics and can provide good results on a best effort basis;
• criticizing, refining, and extending the cost metrics currently in use;
• implementing and evaluating a query planner component that implements the methodology.

Previous knowledge of Web service technologies and database systems is useful. Good analysis and programming skills are recommended.