Aggregate functions in disjunctive logic programming: semantics, complexity, and implementation in DLV

TLDR

Disjunctive Logic Programming is highly expressive, yet it cannot naturally encode simple arithmetic aggregate properties that arise in real‑world applications. This work extends DLP by introducing aggregate functions to address that limitation. The authors formalize the semantics of the resulting language, DLPA, implement it in the DLV system, and report experimental results demonstrating its practical usefulness and computational efficiency. DLPA proves useful on knowledge‑based problems and, according to a complexity analysis, the addition of aggregates does not increase the overall computational cost.

Abstract

Disjunctive Logic Programming (DLP) is a very expressive formalism: it allows to express every property of finite structures that is decidable in the complexity class ΣP2 (NPNP). Despite the high expressiveness of DLP, there are some simple properties, often arising in real-world applications, which cannot be encoded in a simple and natural manner. Among these, properties requiring to apply some arithmetic operators (like sum, times, count) on a set of elements satisfying some conditions, cannot be naturally expressed in DLP. To overcome this deficiency, in this paper we extend DLP by aggregate functions. We formally define the semantics of the new language, named DLPA. We show the usefulness of the new constructs on relevant knowledge-based problems. We analyze the computational complexity of DLPA, showing that the addition of aggregates does not bring a higher cost in that respect. We provide an implementation of the DLPA language in DLV- the state-of-the-art DLP system - and report on experiments which confirm the usefulness of the proposed extension also for the efficiency of the computation.