Project Description
During the past years, our research team has been able to provide significant contributions to the design and implementation of Logic Programming (LP) systems. Our contributions range over the sequential, parallel and distributed execution of logic programs, with support for extensions such as Tabling and the Extended Andorra Model (EAM). More recently, our work has been focused on support for major applications of LP, such as Inductive Logic Programming (ILP), Model Checking and Program Analysis. Throughout, we have relied on the Yap Prolog system, a mainstream Prolog system widely recognized as one of the fastest Prolog systems.The STAMPA project is motivated by recent results on applying our research to real-world problems. Namely, we focus on tabling technology, currently one of the main research topics in LP technology. We believe that tabling is key in supporting applications of LP such as ILP, Program Analysis, Model Checking, among a variety of Deductive Databases (DDB) style applications. Moreover, tabling is fundamental in the efficient support of novel extensions of LP that take us further than standard Prolog, such as Answer Set Programming (ASP) and Warren's Extended Andorra Model. Tabling techniques are a common factor in all these cases: they highly benefit the efficiency of execution of these LP based systems, thus allowing developers to address a wider range of real-world applications.
Our work on tabling, the YapTab tabling system, provided significant and important contributions to the area. Original aspects of YapTab include the support for or-parallel tabling; the ability to support dynamic mixed-strategy evaluation of the two most successful tabling scheduling strategies; a novel fix-point check algorithm based on the data structures corresponding to suspended sub-computations; and innovative proposals to efficiently handle incomplete and complete tables. To the best of our knowledge, YapTab is also the single system that compares favorably with the current versions of XSB, the most well-known Prolog tabling system.
The STAMPA project starts from these solid foundations, and tackles two main research directions. On the one hand, we will focus on improving our tabling engine with novel and original contributions to the state-of-the-art as well as the support of further innovative features to tabling systems. This includes support for negation; support for external storage of tables, in database systems; support for alternative data structures and algorithms for representing and managing the table space; support for alternative tabling mechanisms; and better support for deterministic applications. These proposals are mainly motivated by our experience with actual real-world applications. The design and implementation of these proposals will thus be mainly validated by using concrete ILP and DDB style applications. Note that because ILP and DDB systems are often developed on top of Prolog systems, they can transparently take advantage of tabling just by using a Prolog tabling system.
The other challenging goal of this research is to study how tabling technology can be efficiently combined with different LP execution models, such as ASP systems and the EAM. ASP is a form of declarative programming oriented towards complex combinatorial search problems, typically with exponential search trees. ASP programs are logic programs, but the computational mechanisms are quite different: instead of evaluating queries, ASP solvers compute models consisting of answer sets. A main contribution of this research should be the design and implementation of an ASP system incorporating tabling technology as a means to significantly reduce the search space for these kind of problems. A second goal of this research is to have a first implementation of a system that fully supports tabled logic programs running within the David H. D. Warren's Extended Andorra Model environment. Such a system will combine the power of tabling with that of EAM to produce an execution model with advanced control strategies that guarantees termination, avoids looping, reduces the search space, and is less sensible to goal ordering, being therefore a powerful environment for applications that dynamically generate queries, such as ILP and DDB.
The proposed work will be implemented on top of the existing systems and will profit from the expertise of our research team. We believe that at the end of the project we will have contributed to the state-of-the-art LP systems and to increase the range of applications for LP. Although our research work will be evaluated by particular applications, we believe that our contributions can be of much broader interest, by providing a powerful and robust tabling environment for many other complex problems.
