Author name cluster

Sven Hartmann

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.

5 papers

1 author row

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