Minimal Coverings of Acyclic Database Schemata
Published 1 January 1984
Giorgio Ausiello, Aurora D’Atri, Marina Moscarini
Citations19
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
In this chapter classes of acyclic hypergraphs associated with classes of relational database schemata are investigated and several results concerning the computational complexity of determining minimal coverings are provided.
Abstract
In this chapter classes of acyclic hypergraphs associated with classes of relational database schemata are investigated. Various concepts of minimal coverings over a given set of nodes are considered, their interpretation in terms of the relational model is given and their properties studied with respect to the acyclicity degree of the hypergraphs. Several results concerning the computational complexity of determining minimal coverings are provided.
Keywords
Computer Science
Journal of Computer and System SciencesApproximation algorithms for combinatorial problems
2,225 Citations1974David S. Johnson
Journal of the ACMOn the Desirability of Acyclic Database Schemes
797 Citations1983Catriel Beeri, Ronald Fagin +2 more
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.
Journal of the ACMDegrees of acyclicity for hypergraphs and relational database schemes
476 Citations1983Ronald Fagin
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.
SIAM Journal on ComputingEquivalences among Relational Expressions
364 Citations1979A. V. Aho, Yehoshua Sagiv +1 more
A polynomial time algorithm is presented for the equivalences of tableaux that correspond to an important subset of expressions, although the equivalence problem is shown to be NP-complete under slightly more general circumstances.
ACM Transactions on Database SystemsA simplied universal relation assumption and its properties
301 Citations1982Ronald Fagin, Alberto O. Mendelzon +1 more
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.
Approximation algorithms for combinatorial problems
257 Citations1973David S. Johnson
For the problem of finding the maximum clique in a graph, no algorithm has been found for which the ratio does not grow at least as fast as 0(nε), where n is the problem size and ε> 0 depends on the algorithm.
Properties of acyclic database schemes
141 Citations1981Catriel Beeri, Ronald Fagin +4 more
The purpose of this paper is to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property.
ACM Transactions on Database SystemsSYSTEM/U: a database system based on the universal relation assumption
110 Citations1984Henry F. Korth, Gabriel M. Kuper +3 more
The theory behind System/U is described, in particular the theory of maximal objects and the connection between a set of attributes and the implementation of the DDL and the DML.
Windows on the world
55 Citations1983David Maier, David Rozenshtein +1 more
This work examines several examples of each type of window function, and defines implicit objects, which are relation schemes that a window function treats in a special manner, and which are useful for describing the behavior of window functions.
Toward logical data independence
46 Citations1982David Maier, David Rozenshtein +3 more
The goal is a powerful, yet concise, query language with natural semantics, where a user need not be concerned with how the data has been partitioned into various relations in a relational database.
Lecture notes in computer scienceAcyclic database schemes (of various degrees): A painless introduction
37 Citations1983Ronald Fagin
This paper is intended to be an informal introduction, in which the focus is mainly on the originally studied (and least restrictive) degree of acyclicity.
The tree property is fundamental for query processing
29 Citations1982Nathan Goodman, Oded Shmueli
This paper considers a class of queries that compute the join of all relations in the database projected onto a prescribed set of attributes, and shows that solving such queries is tantamount to creating an "embedded" tree schema which is called a tree projection.
A universal relation database system implemented via the network model
29 Citations1982Sharon McCure Kuck, Yehoshua Sagiv
A network schema design algorithm that uses a well-designed relational schema as input and shows how to map the representative instance to the network database.
Towards A Universal Relation Interface
28 Citations1979Sylvia L. Osborn
It is shown that it is possible to automatically generate all valid answers to a query on a relational data base such that the user need not be aware of the relations used to form the answer, but can express queries simply in terms of attribute names.
Transforming cyclic schemas into trees
25 Citations1982Nathan Goodman, Oded Shmueli
A relational database schema can be thought of as a hypergraph whose nodes are attributes and whose edges are relations such that for each attribute, the subtree of nodes containing this attribute is connected.
Answering queries in relational databases
11 Citations1983Alessandro D’Atri, Marina Moscarini +1 more
A formal treatment of unambiguous contexts is presented and it is shown that they provide a suitable basis for discussing the universal relation assumption, the relationship uniqueness assumption, maximal objects, and other related concepts.
Lecture notes in computer scienceAn application of the theory of graphs and hypergraphs to the decomposition of relational database schemes
8 Citations1983Jan Paredaens, Dirk Van Gucht
An application of the theory of graphs and hypergraphs to the decomposition of Relational Database Schemas is studied.
Universal Relation Database Systems.
2 Citations1983Jeff Ullman
The query facility for their universal relation database system is now working and the fundamental paper unifying ideas on what a UR system can and should be has been published.
ACM SIGMOD RecordAnswering queries in relational databases
2 Citations1983Alessandro D’Atri, Marina Moscarini +1 more
This paper concerns query answering in relational databases and assumes a universe U of attributes and a set of values associated with each attribute.
Transforming cyclic schemas into trees
2 Citations1982N. Goodman, O. Shmueli