Tecniche per la valutazione distribuita di programmi logici

Abstract

Recent developments in IT, and in particular the expansion of networking technologies, have made quite common the availability of software architectures where data sources are distributed across multiple (physically-di erent) sites. As a consequence, the number of applications requiring to e ciently query and reason on natively distributed data is constantly growing. In this thesis we focus on the context in which it is necessary to combine data natively resides on di erent, autonomous and distributed sources and it is appropriate to deal with reasoning task to extract knowledge from the data, via deductive database techniques [1]. The aim is distributed evaluation of logic programs through an optimization strategy that minimizes the cost of the local process and data transmission. We considered that a single logic rule can be seen as a conjunctive query (possibly with negation), whose result must be stored in the head predicate. Then, starting from the conjunctive query optimization techniques, the idea is to extend the best results of these to evaluation of logic programs. In this context the methods based on structural analysis of the queries seem particularly promising. Indeed, logical rules often contain multiple interactions interactions among join variables [2]. In the case of simple queries (acyclic) there are several algorithms that ensure execution time with a polynomial upper bound. Structural methods [3, 4, 5, 6] attempt to propagate the good results of acyclic queries to larger classes of these, whose structure is cyclic, but with a low \degree of cyclicity". The Hypertree Decomposition technique [6] appears to be the most powerful since generalizes strongly all other structural methods and guarantees improved response times for each class of queries. Decomposition can be interpreted as an execution plan for the query, which rst requires the evaluation of the join associated with each cluster, and then requires the processing of the resulting join tree using a bottom-up approach. We used a weighted extension of Hypertree Decomposition [7] that combine structural analysis with evaluation of relevant quantitative information about the data, such as the number of tuples in relations, the selectivity of attributes and so on, and calculates minimum decompositions w.r.t. a cost function. We suitably modi ed this method in order to estimate the cost of data transmission between di erent sites resulting from the distribution of the sources and the correct evaluation of negation in rule bodies. According decomposition the query is transformed into a (tree-like) set of sub-queries which also allows the parallel evaluation of independent sub-query. We used parallel techniques combined with techniques for query optimization. We have adopted DLVDB [8, 9, 10, 11] as core reasoning engine, which allows to evaluate logic programs directly on database and combines appropriately expressive power of logic programming systems and the e cient data management of DBMSs. The interaction with databases is achieved by means ODBC connections, therefore, in case of distributed computing on network it allows to transparently access di erent sources and to express very simply distributed queries. We have implemented a prototype that we used to conduct the experiments. The preliminary results are very encouraging and showed the validity of the approach.