# Characterization of desirable properties of general database decompositions

@article{Hegner2005CharacterizationOD, title={Characterization of desirable properties of general database decompositions}, author={S. Hegner}, journal={Annals of Mathematics and Artificial Intelligence}, year={2005}, volume={7}, pages={129-195} }

The classical theory of acyclicity of universal relational schemata identifies a set of “desirable” properties of such schemata, and then shows that all of these properties are equivalent to one another, and in turn equivalent to certain acyclicity characterizations of a hypergraph underlying the schema. The desirable properties include the simplicity of constraints, the correctness of certain efficient query evaluation algorithms, and the complexity of maintaining the integrity of a decomposed… Expand

#### Figures and Topics from this paper

#### 8 Citations

The complexity of embedded axiomatization for a class of closed database views

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2005

This question is addressed for closed update strategies, which are based upon the constant-complement approach of Bancilhon and Spyratos, and is to address a more general question – that of characterizing the complexity of axiomatization of views, relative to the complexity to the main schema. Expand

The Relative Complexity of Updates for a Class of Database Views

- Computer Science
- FoIKS
- 2004

This paper has shown that the complexity of testing the correctness of a view update which follows a closed update strategy is no greater than that of testing a corresponding update to the main schema. Expand

An Order-Based Theory of Updates for Closed Database Views

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2004

The paper develops a theory which identifies conditions under which a natural, maximal, update strategy exists for a view, and applies this theory to a ubiquitous example – single-relational schemata constrained by equality-generating dependencies. Expand

Lossless Decompositions in Complex-Valued Databases

- Computer Science
- FoIKS
- 2008

This work extends the relational model to a complex-valued data model based on record, list, set and multiset constructor, where finite domains occur naturally for subattributes, even if the domains of flat attributes are infinite. Expand

Stephen J. Hegner, 490317-0498, Attachment A, Page 1 Complexity of Updates on Closed Database Views 1. Specific Goals of the Project 2. Overview of the Research Area

Two essential features of any large, modern database management system are the capability of performing updates and the capability of delivering limited access through views. The integration of these… Expand

Three Research Projects Based upon Database Views 2 . 1 View Updates and the Complexity of View Axiomatization

Modern database schemata are very large and complex. Even modest schemata often have hundreds of relations; the largest have thousands. As a tool to manage this complexity, the notion of a view — a… Expand

A Model of Database Components and their Interconnection Based upon Communicating Views

- Computer Science, Mathematics
- EJC
- 2007

A formalism for constructing database schemata from simple components is presented in which the components are coupled to one another via communicating views and a characterization of such, based upon the acyclicity of an underlying hypergraph is obtained. Expand

Two Research Projects on Updates to Database Components 2 . 1 Foundations of Update Support on Database Components

Modern database schemata are very large and complex. Even the most modest often have hundreds of relations; the largest have thousands. Fortunately, it is often possible to model even the largest… Expand

#### References

SHOWING 1-10 OF 70 REFERENCES

Pairwise-Definable Subdirect Decompositions of General Database Schemata

- Mathematics, Computer Science
- MFDBS
- 1991

This paper shows that the equivalence of acyclicity of the hypergraph of the schema to numerous desirable properties regarding simplicity of constraints, correctness of query evaluation algorithms, and complexity of integrity maintenance applies in a much more general context in which schemata are just sets and views are defined by surjective functions. Expand

Unique Complements and Decomposition of Database Schemata

- Computer Science
- J. Comput. Syst. Sci.
- 1994

This work shows that by adding a modest amount of additional structure to database schemata, many important uniqueness results may be obtained, and establishes that under the condition that the schema is constrained by universal Horn sentences, there is a unique ultimate decomposition into a finite set of type restrictions. Expand

Degrees of acyclicity for hypergraphs and relational database schemes

- Mathematics, Computer Science
- JACM
- 1983

Various desirable properties of database schemes are constdered and it is shown that they fall into several equivalence classes, each completely characterized by the degree of acycliclty of the scheme. Expand

A simplied universal relation assumption and its properties

- Computer Science
- TODS
- 1982

This work proposes a simpler method of describing the real world, where constraints are given by functional dependencies and a single join dependency, and characterize in terms of hypergraphs those multivalued dependencies that are the consequence of a given join dependency. Expand

On decomposition of relational databases

- Computer Science
- 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)
- 1982

It is got that the reconstruction map, which is the inverse to the decomposition map, is also first-order, but is not necessarily the natural join, by applying Beth's Definability Theorem from model theory. Expand

On the Desirability of Acyclic Database Schemes

- Mathematics, Computer Science
- JACM
- 1983

It is shown that this class of database schemes, called acychc, has a number of desirable properties that have been studied by other researchers and are shown to be eqmvalent to acydicity. Expand

Foundations of Canonical Update Support for Closed Database Views

- Computer Science
- ICDT
- 1990

The proper context is shown to be that of update translation under constant meet complement, a refinement of the constant complement strategy of Bancilhon and Spyratos. Expand

On the family of generalized dependency constraints

- Mathematics, Computer Science
- JACM
- 1982

A common framework is provided for the investigation of various types of integnty constraints for relaaonal databases. The family of generahzed dependency constraints is introduced. It is shown that… Expand

On interpretations of relational languages and solutions to the implied constraint problem

- Computer Science
- TODS
- 1982

The interconnection between conceptual and external levels of a relational database is made precise in terms of the notion of “interpretation” between first-order languages. This is then used to… Expand

Towards a Logical Reconstruction of Relational Database Theory

- Mathematics, Computer Science
- On Conceptual Modelling
- 1982

Insofar as database theory can be said to owe a debt to logic, the currency on loan is model theoretic in the sense that a database can be viewed as a particular kind of first order interpretation,… Expand