Concurrent tabling

In the past few years Tabling has emerged as a powerful logic programming model. The integration of concurrent features into the implementation of Tabling systems is demanded by need to use recently developed tabling applications within distributed systems, where a process has to respond concurrently to several requests. The support for sharing of tables among the concurrent threads of a Tabling process is a desirable feature, to allow one of Tabling’s virtues, the re-use of computations by other threads and to allow efficient usage of available memory. However, the incremental completion of tables which are evaluated concurrently is not a trivial problem. In this dissertation we describe the integration of concurrency mechanisms, by the way of multi-threading, in a state of the art Tabling and Prolog system, XSB. We begin by reviewing the main concepts for a formal description of tabled computations, called SLG resolution and for the implementation of Tabling under the SLG-WAM, the abstract machine supported by XSB. We describe the different scheduling strategies provided by XSB and introduce some new properties of local scheduling, a scheduling strategy for SLG resolution. We proceed to describe our implementation work by describing the process of integrating multi-threading in a Prolog system supporting Tabling, without addressing the problem of shared tables. We describe the trade-offs and implementation decisions involved. We then describe an optimistic algorithm for the concurrent sharing of completed tables, Shared Completed Tables, which allows the sharing of tables without incurring in deadlocks, under local scheduling. This method relies on the execution properties of local scheduling and includes full support for negation. We provide a theoretical framework and discuss the implementation’s correctness and complexity. After that, we describe amethod for the sharing of tables among threads that allows parallelism in the computation of inter-dependent subgoals, which we name Concurrent Completion. We informally argue for the correctness of Concurrent Completion. We give detailed performance measurements of the multi-threaded XSB systems over a variety of machines and operating systems, for both the Shared Completed Tables and the Concurrent Completion implementations. We focus our measurements inthe overhead over the sequential engine and the scalability of the system. We finish with a comparison of XSB with other multi-threaded Prolog systems and we compare our approach to concurrent tabling with parallel and distributed methods for the evaluation of tabling. Finally, we identify future research directions.

O futuro da web semântica e sua importância nas organizações

Trabalho realizado sob orientação do Prof. António Brandão Moniz para a disciplina “Factores Sociais da Inovação” do Mestrado Engenharia Informática realizado na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa (Portugal)

Desenvolvimento do segundo e terceiro pilares da Segurança Social: o caso de Cabo Verde

Dissertação para obtenção do Grau de Mestre em Matemática e Aplicações, no ramo Actuariado, Estatística e Investigação Operacional

Molecular modulation of brain development and function: lessons from “old” and “new”

Dissertation presented to obtain the Ph.D degree in Biology

The impact of knowledge transfer on innovation in multinational corporations: Exploring the contingent effects

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

Modelling and Forecasting Mortality Patterns

Thesis submitted in partial fulfillment of the requirements for the Degree of Doctor of Statistics and Information Management

Fluvial system restoration – case study: river Tua

Dissertação para obtenção do Grau de Mestre em Engenharia do Ambiente, Perfil de Engenharia de Sistemas Ambientais

Role of surfactants in filtration and fouling of colloidal silica

The EM3E Master is an Education Programme supported by the European Commission, the European Membrane Society (EMS), the European Membrane House (EMH), and a large international network of industrial companies, research centres and universities

Afonso de Albuquerque e a primeira expedição portuguesa ao Mar Vermelho (1513)

Este artigo pretende analisar a primeira expedição portuguesa ao Mar Vermelho, capitaneada pelo governador Afonso de Albuquerque, em 1513. Quinhentos anos depois desta viagem, reavaliamos a política manuelina para o Mar Roxo, observando o ataque à cidade de Adém e a consecutiva entrada naquele mar. Através da correspondência de Albuquerque e da cronística da época, tentamos compreender os motivos da derrota no assalto àquela cidade portuária e a importância desta expedição na acção daquele governador e na estratégia imperial de D. Manuel I.