the well-founded semantics of aggregation
Common aggregation predicates have natural definitions in logic, either as first order sentences ( min, max, etc.), or with elementary induction over a data structure that represents the relation ( sum, count, etc.). The well-founded semantics for logic programs provides an interpretation of such definitions. The interpretation of first-order aggregates seems to be quite natural and intuitively satisfying, even in the presence of recursion through aggregation. Care is needed to get useful results on inductive aggregates, however. A basic building block is the subset predicate, which states that a data structure represents a subset of an IDB predicate, and which is definable in the well-founded semantics. The analogous superset is also definable, and their combination yields a generic form of findall . Surprisingly, findall must be used negatively to obtain useful approximations when the exact relation is not yet known. Extensions to the semantics, restrictions on the input, and other supplementary requirements proposed in earlier studies appear to be unnecessary for the purpose of attaching a meaning to a program that involves recursion through aggregation. For example, any reasonable definition of shortest paths tolerates negative weight edges, correctly computes shortest paths that exist, and leave tuples undefined where negative-weight cycles cause the shortest path not to exist. Other examples exhibit similarly robust behavior, when defined carefully. Connections with the generic model of computation are discussed briefly.
semantic aggregate definition logic order inductance data structures relation logic program interpretation presence recursion building block combinational generic input requirements examples shortest path robust behavior connection model of computation