Author name cluster

Sebastian Link

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

2 author rows

LPAR Conference 2017 Conference Paper

On the Interaction of Inclusion Dependencies with Independence Atoms

Miika Hannula
Juha Kontinen
Sebastian Link

Inclusion dependencies are one of the most important database constraints. In isolation their finite and unrestricted implication problems coincide, are finitely axiomatizable, PSPACE-complete, and fixed-parameter tractable in their arity. In contrast, finite and unrestricted implication problems for the combined class of functional and inclusion de- pendencies deviate from one another and are each undecidable. The same holds true for the class of embedded multivalued dependencies. An important embedded tractable fragment of embedded multivalued dependencies are independence atoms. These stipulate independence between two attribute sets in the sense that for every two tuples there is a third tuple that agrees with the first tuple on the first attribute set and with the second tuple on the second attribute set. For independence atoms, their finite and unrestricted implication problems coincide, are finitely axiomatizable, and decidable in cubic time. In this article, we study the implication problems of the combined class of independence atoms and inclusion dependencies. We show that their finite and unrestricted implication problems coincide, are finitely axiomatizable, PSPACE-complete, and fixed-parameter tractable in their arity. Hence, significant expressivity is gained without sacrificing any of the desirable properties that inclusion dependencies have in isolation. Finally, we establish an efficient condition that is sufficient for independence atoms and inclusion dependencies not to inter- act. The condition ensures that we can apply known algorithms for deciding implication of the individual classes of independence atoms and inclusion dependencies, respectively, to decide implication for an input that combines both individual classes.

Details

TCS Journal 2015 Journal Article

Frontiers for propositional reasoning about fragments of probabilistic conditional independence and hierarchical database decompositions

Sebastian Link

Conditional independence provides an essential framework to deal with knowledge and uncertainty in Artificial Intelligence, and is fundamental in probability and multivariate statistics. Its associated implication problem is paramount for building Bayesian networks. Unfortunately, the problem does not enjoy an axiomatization, by a finite set of Horn rules, and is already coNP-complete to decide for some fragments of conditional independencies. Saturated conditional independencies form an important fragment whose implication problem is decidable in almost linear time. We establish an axiomatization, by a finite set of Horn rules, for the fragment of generalized saturated conditional independencies. These state the conditional independence between finitely many sets of random variables. The special case of two sets captures Geiger and Pearl's finite axiomatization for saturated conditional independencies. Even for this special case, our completeness proof is new. The proof argument utilizes special probability models where two events have probability one half. Special probability models allow us to establish an equivalence between the implication of generalized saturated conditional independencies and that of formulae in a Boolean propositional fragment. This duality is then extended to a trinity including the implication problem of Delobel's full first-order hierarchical database decompositions. Already for the independence between two sets of random variables, the dualities cannot be extended to cover conditional independencies in general, or first-order hierarchical decompositions.

Details DOI

JELIA Conference 2014 Conference Paper

Logical Foundations of Possibilistic Keys

Henning Köhler
Uwe Leck
Sebastian Link
Henri Prade

Abstract Possibility theory is applied to introduce and reason about the fundamental notion of a key for uncertain data. Uncertainty is modeled qualitatively by assigning to tuples of data a degree of possibility with which they occur in a relation, and assigning to keys a degree of certainty which says to which tuples the key applies. The associated implication problem is characterized axiomatically and algorithmically. It is shown how sets of possibilistic keys can be visualized as possibilistic Armstrong relations, and how they can be discovered from given possibilistic relations. It is also shown how possibilistic keys can be used to clean dirty data by revising the belief in possibility degrees of tuples.

Details

JELIA Conference 2014 Conference Paper

Logics for Approximating Implication Problems of Saturated Conditional Independence

Henning Köhler
Sebastian Link

Abstract Random variables are declared complete whenever they must not admit missing data. Intuitively, the larger the set of complete random variables the closer the implication of saturated conditional independence statements is approximated. Two different notions of implication are studied. In the classical notion, a statement is implied jointly by a set of statements, the fixed set of random variables and its subset of complete random variables. For the notion of pure implication the set of random variables is left undetermined. A first axiomatization for the classical notion is established that distinguishes purely implied from classically implied statements. Axiomatic, algorithmic and logical characterizations of pure implication are established. The latter appeal to applications in which the existence of random variables is uncertain, for example, when statements are integrated from different sources, when random variables are unknown or when they shall remain hidden.

Details

UAI Conference 2014 Conference Paper

Saturated Conditional Independence with Fixed and Undetermined Sets of Incomplete Random Variables

Henning Köhler
Sebastian Link

The implication problem for saturated conditional independence statements is studied in the presence of fixed and undetermined sets of incomplete random variables. Here, random variables are termed incomplete since they admit missing data. Two different notions of implication arise. In the classic notion of V -implication, a statement is implied jointly by a set of statements and a fixed set V of random variables. In the alternative notion of pure implication, a statement is implied by a given set of statements alone, leaving the set of random variables undetermined. A first axiomatization for V -implication is established that distinguishes purely implied from V -implied statements. Axiomatic, algorithmic and logical characterizations of pure implication are established. Pure implication appeals to applications in which the existence of random variables is uncertain, for example, when independence statements are integrated from different sources, when random variables are unknown or shall remain hidden.

Details

AAAI Conference 2013 Conference Paper

Reasoning about Saturated Conditional Independence Under Uncertainty: Axioms, Algorithms, and Levesque’s Situations to the Rescue

Sebastian Link

The implication problem of probabilistic conditional independencies is investigated in the presence of missing data. Here, graph separation axioms fail to hold for saturated conditional independencies, unlike the known idealized case with no missing data. Several axiomatic, algorithmic, and logical characterizations of the implication problem for saturated conditional independencies are established. In particular, equivalences are shown to the implication problem of a propositional fragment under Levesque’s situations, and that of Lien’s class of multivalued database dependencies under null values.

PDF Details

I&C Journal 2010 Journal Article

Numerical constraints on XML data

Sven Hartmann
Sebastian Link

Boundaries occur naturally in everyday life. This paper introduces numerical constraints into the framework of XML to take advantage of the benefits that result from the explicit specification of such boundaries. Roughly speaking, numerical constraints restrict the number of elements in an XML data fragment based on the data values of selected subelements. Efficient reasoning about numerical constraints provides effective means for predicting the number of answers to XQuery and XPath queries, the number of updates when using the XQuery update facility, and the number of encryptions or decryptions when using XML encryption. Moreover, numerical constraints can help to optimise XQuery and XPath queries, to exclude certain choices of indices from the index selection problem, and to generate views for efficient processing of common queries and updates. We investigate decision problems associated with numerical constraints in order to capitalise on the range of applications in XML data processing. To begin with we demonstrate that the implication problem is strongly coNP-hard for several classes of numerical constraints. These sources of potential intractability direct our attention towards the class of numerical keys that permit the specification of positive upper bounds. Numerical keys are of interest as they are reminiscent of cardinality constraints that are widely used in conceptual data modelling. At the same time, they form a natural generalisation of XML keys that are popular in XML theory and practice. We show that numerical keys are finitely satisfiable and establish a finite axiomatisation for their implication problem. Finally, we propose an algorithm that decides numerical key implication in quadratic time using shortest path methods.

Details DOI

TCS Journal 2006 Journal Article

Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets

Sven Hartmann
Sebastian Link
Klaus-Dieter Schewe

We investigate functional dependencies in databases that support complex values such as records, lists, sets and multisets. Therefore, an abstract algebraic framework is proposed that classifies data models according to the underlying types they support. This allows to emphasise the impact of the data types rather than the specifics of a particular data model. The main results are finite, minimal, sound and complete sets of inference rules for the implication of functional dependencies in the presence of records and all combinations of lists, sets and multisets. The inference rules are similar to Armstrong's original axioms for the relational data model, thanks to the algebraic framework. The completeness result, however, requires a deep analysis in the case of sets and, in particular, multisets.

Details DOI

TCS Journal 2006 Journal Article

Deciding implication for functional dependencies in complex-value databases

Sven Hartmann
Sebastian Link

Modern applications increasingly require the storage of data beyond relational structure. The challenge of providing well-founded data models that can handle complex objects such as lists, sets, multisets, unions and references has not been met yet in a completely satisfactory way. The success of such data models will greatly depend on the existence of automated database design techniques that generalise achievements from relational databases. In this paper, we study the implication problem of functional dependencies (FDs) in the presence of records, sets, multisets and lists. Database schemata are defined as nested attributes, database instances as nested relations and FDs are defined in terms of subattributes of the database schema. The expressiveness of FDs deviates fundamentally from previous approaches in different data models including the nested relational data model and XML. The implication problem is to decide whether for an arbitrary database schema, and an arbitrary set Σ ∪ { σ } of FDs defined on that schema, every database instance that satisfies all FDs in Σ also satisfies σ. The difficulty in generalising the solution from the relational data model to the presence of sets and multisets is caused by the fact that the value on the join of subattributes is no longer determined by the values on the subattributes. Based on the notion of a unit, we propose to decompose the database schema in such a way that the closure of a set of nested attributes can be computed on the components of the schema. The implementation of the algorithm is based on a representation theorem for Brouwerian algebras. The main contribution is the proof that the algorithm works correctly and in polynomial-time in the size of the input. Defining the size of the input is not trivial since the measure should both generalise the one that is used for relational databases and do justice to the presence of sets and multisets. Our solution to the implication problem allows to solve other important problems that occur in database design. We present polynomial-time algorithms to determine non-redundant covers of sets of FDs, and to decide whether a given set of subattributes forms a superkey.

Details DOI

TCS Journal 2006 Journal Article

Erratum to “Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets”

Sven Hartmann
Sebastian Link
Klaus-Dieter Schewe

This note corrects two errors that occurred during the typesetting of our paper “Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets”, which appeared in Hartmann et al. [Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets, Theoret. Comput. Sci. 353(2) (2006) 167–196].

Details DOI

TCS Journal 2006 Journal Article

On a problem of Fagin concerning multivalued dependencies in relational databases

Sven Hartmann
Sebastian Link

Multivalued dependencies (MVDs) are an important class of relational constraints that is fundamental to relational database design. Reflexivity axiom, complementation rule, and pseudo-transitivity rule form a minimal set of inference rules for the implication of MVDs. The complementation rule plays a distinctive role as it takes into account the underlying relation schema R which the MVDs are defined on. The R-axiom ∅ ↠ R is much weaker than the complementation rule, but is sufficient to form a minimal set of inference rules together with augmentation and pseudo-difference rule. Fagin has asked whether it is possible to reduce the power of the complementation rule and drop the augmentation rule at the same time and still obtain a complete set. It was argued that there is a trade-off between complementation rule and augmentation rule, and one can only dispense with one of these rules at the same time. It is shown in this paper that an affirmative answer to Fagin's problem can nevertheless be achieved. In fact, it is proven that R-axiom together with a weaker form of the reflexivity axiom, pseudo-transitivity rule and exactly one of union, intersection or difference rule form such desirable minimal sets. The positive solution to this problem gives further insight into the difference between the notions of functional and multivalued dependencies.

Details DOI