ABSTRACT. In several different settings, one comes across situations in which the objects of study are locally consistent but globally inconsistent. Earlier work in probability theory in the 1960s and in relational database theory in the 1980s produced characterizations of when local consistency implies global consistency. We will discuss two different generalizations of these results: the first considers K-relations over an arbitrary positive semiring K, while the second considers K-relations over an arbitrary positive monoid K. In each of these two settings, we explore when a database schema has the property that every pairwise consistent collection of K-relations over that schema is globally consistent; special cases include the earlier results about local vs. global consistency in relational database theory and more recent results about local vs. global consistency of bags.

ABSTRACT. Errors in knowledge bases (KBs) written in a Description Logic (DL) are usually detected when reasoning derives an inconsistency or a consequence that does not hold in the application domain modelled by the KB. Whereas classical repair approaches produce maximal subsets of the KB not implying the inconsistency or unwanted consequence, optimal repairs maximize the consequence sets. In this paper, we extend previous results on how to compute optimal repairs from the DL $\mathcal{EL}$ to its extension $\mathcal{EL}^{\bot}$, which in contrast to $\mathcal{EL}$ can express inconsistency. The problem of how to deal with inconsistency in the context of optimal repairs was addressed previously, but in a setting where the (fixed) terminological part of the KB must satisfy a restriction on cyclic dependencies. Here, we consider a setting where this restriction is not required. We also show how the notion of optimal repairs obtained this way can be used in inconsistency- and error-tolerant reasoning.

ABSTRACT. In this work, we discover a connection between finding subset-maximal repairs for a set of functional dependencies (FDs) and inclusion dependencies (IDs), and computing extensions within argumentation frameworks (AFs). We study the complexity of existence of a repair and deciding whether a given tuple belongs to some (or every) maximal repair, by simulating the instances of these problems via an argumentation framework. We prove that subset-maximal repairs under functional dependencies correspond to the naive extensions, which also coincide with the preferred and stable extensions in the resulting AFs. For inclusion dependencies, one needs a pre-processing step on the resulting AFs in order for the extensions to coincide. Allowing both types of dependencies breaks this relationship between extensions, and only preferred semantics captures the maximal repairs. Finally, we establish that the complexities of the above decision problems are NP-complete and Pi^P_2-complete, when both functional and inclusion dependencies are allowed.

ABSTRACT. As yet another semantically enriched data model, we consider relational schemas with finite domain sizes and multiplicity bounds and diversity bounds together with functional dependencies as semantic constraints. As a simple variant of cardinality constraints, for a set of attributes, a multiplicity bound requires that a possible value combination occurs at most as often as the bound extension says. As a new kind of constraints, for a set of attributes, a diversity bound describes how many different value combinations under these attributes may at most occur in a relation instance. A multiplicity bound and a diversity bound together are seen as a weak abstraction of a so-called structure for the set of attributes on the left-hand side of a functional dependency. Such a structure specifies the exact size of the active domain of that set and the respective exact numbers of occurrences, summing up to a given instance size. We study how multiplicity bounds, diversity bounds and functional dependencies under finite sizes of attribute domains interact. We exhibit a powerful sound derivation system for all these items, together with a generation procedure for approximating the entailment closure of such constraints. We further analyze how to construct relation instances that exactly achieve the best/strongest multiplicity or diversity bound extension, respectively, for some attribute set or even all of them.

ABSTRACT. Hartmann et. al. proved that calculating Armstrong instance for a collection of cardinality constraints is exactly exponential problem by giving a collection of cardinality constraints based on some special graphs that the minimal Armstrong instance is of of exponential size. In the present paper we take up the task to determine sizes of minimum Armstrong instances of collections of cardinality constraints based on graphs and give exact results for several classes or give polynomial time algorithm to construct the minimum Armstrong table for other cases. We show that Armstrong tables of cardinality constraints based on graphs correspond to another graph defined on the maximal independent vertex sets of the constraint graph. It turns out that the problem is strongly related to line graphs, and feasible edge colorings of graphs.

ABSTRACT. It has been shown that c-inference is an inductive inference operator, mapping belief bases to inference relations, that exhibits many desirable properties put forward for nonmonotonic reasoning. It is based on c-representations which are a special kind of ranking function. However, the definition of c-representation only takes belief bases into account that satisfy a rather strong notion of consistency requiring every world to be at least somewhat plausible. In this paper, we employ the concepts of strong and weak consistency for conditional belief bases and extend the notions of c-representation and c-inference to also cover weakly consistent belief bases. We adapt a constraint satisfaction problem characterizing c-inference so that it captures extended c-inference and provides a basis for its implementation. Furthermore, we show various properties of extended c-inference and in particular, we prove that the extended notion of c-inference fully satisfies syntax splitting.

ABSTRACT. c-Representations constitute a family of ranking models of symbolic conditional belief bases with outstanding inference properties. In this paper, we identify the subclass of core c-representations which inherit all beneficial properties from c-representations but are stratified, hence, easier to compute. Moreover, this class provides a unique minimal representative, the minimal core c-representation of a conditional belief base. Based on that, we define a novel inference operation, c-core closure, analyze its properties, and compare it to System P, System Z, and skeptical c-inference. Like skeptical c-inference, c-core closure satisfies syntax splitting and does not suffer from the drowning problem. In addition, it satisfies rational monotony and inductive enforcement.