Distributed Query-Sub-Query Project

Overview:

The purpsoe of this project is to develop a distributed algorithm based on Query-Sub-Query technique for optimization of Datalog queries in a peer-to-peer environment.
The algorithm is implemented using the Active XML system.

Abstract:

Research on deductive databases and Datalog led to beautiful results in the late 80s, but with little industrial impact, essentially because recursive data that required such technology was in practice rare. Years later, with networks everywhere, recursive data management is essential, and consequently this research is becoming relevant. Things are of course more complex than in classical Datalog: the architecture is often based on distributed autonomous peers and the interaction is often asynchronous. Nevertheless, one encounters again the management of a mix of intensional and extensional information in a recursive setting, and the old optimization methods proposed for Datalog meet the new needs.

Specifically, our research showed that it is possible to adapt Query-Sub-Query (QSQ), a technique that optimizes the evaluation of Datalog queries, to a distributed setting, and use it to make query evaluations over distributed data more efficient. The problem is modeled using a distributed version of Datalog, which is called dDatalog, and optimized with a distributed version of QSQ, called dQSQ.

We checked the feasibility of implementing a real system for optimization of distributed Datalog queries based on the dQSQ technique, examined the challenges that arise from it, and eventually built such a system that can be used in practice.

Our implementation of dQSQ is based on Active XML (AXML), a system with XML documents where some parts of the data are given explicitly, while other parts are given intensionally as calls to Web services. We defined a mechanism to represent dDatalog programs using AXML. We also defined a termination detection mechanism and showed how to embed it to the system. Finally, we developed a full-fledged dQSQ system, based on these mechanisms.

People:

Prof. Tova Milo
Noam Pettel
External: Zoe Abrams (Stanford), Serge Abiteboul (INRIA), Stefan Haar (IRISA)

Publications:

Diagnosis of Asynchronous Discrete Event Systems - Datalog to the Rescue!. S. Abiteboul, Z. Abrams, S. Haar, T. Milo, PODS'05. June 2005.
Optimizing Query Evaluation with Distributed Query-Sub-Query N. Pettel, M.Sc thesis, Tel Aviv University, 2006.

Downloads:

dQSQ System - Latest Version (zip file)