Degrees of acyclicity for hypergraphs and relational database schemes
Journal of the ACMPublished 1 July 1983Open access
Ronald Fagin
Citations476
SJR quartileQ1
SJR score2.25
SNIP3.16
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
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.
Abstract
article Free Access Share on Degrees of acyclicity for hypergraphs and relational database schemes Author: Ronald Fagin IBM Research Laboratory K51/281, 5600 Cottle Road, San Jose, CA IBM Research Laboratory K51/281, 5600 Cottle Road, San Jose, CAView Profile Authors Info & Claims Journal of the ACMVolume 30Issue 3July 1983 pp 514–550https://doi.org/10.1145/2402.322390Published:01 July 1983Publication History 317citation1,088DownloadsMetricsTotal Citations317Total Downloads1,088Last 12 Months124Last 6 weeks16 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Keywords
Computer Science
ACM Transactions on Database SystemsExtending the database relational model to capture more meaning
1,555 Citations1979E. F. Codd
This paper proposes extensions to the relational model to support certain atomic and molecular semantics, a synthesis of many ideas from the published work in semantic modeling plus the introduction of new rules for insertion, update, and deletion, as well as new algebraic operators.
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.
Extending the data base relational model to capture more meaning
562 Citations1979E. F. Codd
This paper proposes extensions to the relational model to support certain atomic and molecular semantics, and represents a synthesis of many ideas from the published work in semantic modeling.
IBM Journal of Research and DevelopmentSEQUEL 2: A Unified Approach to Data Definition, Manipulation, and Control
521 Citations1976Donald D. Chamberlin, M. M. Astrahan +6 more
SEQUEL 2 is a relational data language that provides a consistent, English keyword-oriented set of facilities for query, data definition, data manipulation, and datac ontrol.
Very Large Data BasesAlgorithms for acyclic database schemes
495 Citations1981Mihalis Yannakakis
The purpose in this paper is to describe efficient algorithms in this setting for various problems, such as computing projections, minimizing joins, inferring dependencies, and testing for dependency satisfaction.
ACM Transactions on Database SystemsThe theory of joins in relational databases
423 Citations1979A. V. Aho, Catriel Beeri +1 more
An efficient algorithm to determine whether the join of several relations is semantically meaningful (lossless) and an efficient algorithm to determine whether a set of relations has a subset with a lossy join are given.
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.
ACM Transactions on Database SystemsA normal form for relational databases that is based on domains and keys
231 Citations1981Ronald Fagin
A new normal form for relational databases, called domain-key normal form (DK/NF), is defined and formal definitions of insertion anomaly and deletion anomaly are presented.
Journal of the ACMOn the Equivalence of Database Models
226 Citations1982Y. Edmund Lien
It is proved that network databases with loop-free Bachman diagrams are superior to relational databases which are free of conflicts and contenUons and shown that the decomposition approach can be apphed to conflictand contention-free relational databases without any of these problems.
SIAM Journal on ComputingPower of Natural Semijoins
225 Citations1981Philip A. Bernstein, Nathan Goodman
This paper characterizes the queries for which full reducer exist and presents an efficient algorithm for constructing full reducers where they do exist and considers “natural” semijoin operator, which is used in the SDD-1 distributed database system.
ACM SIGMIS Database the DATABASE for Advances in Information SystemsData structure diagrams
199 Citations1969Charles W. Bachman
The invention of algebra, essentially a graphic technique for communicating truths with respect to classes of arithmetic statements, broke the bond that slowed the development of mathematics.
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.
Lecture notes in computer scienceTheory of relations for databases — a tutorial survey
96 Citations1978J. Rissanen
This is an account of a theory of relations that has advanced from Codd's relational model of data for databases that deals with syntactic characterizations of the closed families of functional, multivalued, and general join dependencies that hold in relations.
Can we use the universal instance assumption without using nulls?
94 Citations1981Yehoshua Sagiv
It is claimed that the representative instance of [Ho1, Va3] is a correct representation of the data stored in a database even when the relations of the database are not the projections of a single universal instance.
Inclusion dependencies and their interaction with functional dependencies
88 Citations1982Marco A. Casanova, Ronald Fagin +1 more
It is shown that finite implication (implication over databases with a finite number of tuples) is the same as unrestricted implications for INDs, although finite implication and unrestricted implication are distinct for FDs and INDs taken together.
SIAM Journal on ComputingEquivalence of Relational Database Schemes
87 Citations1981Catriel Beeri, Alberto O. Mendelzon +2 more
The U. R. strikes back
74 Citations1982Jeffrey D. Ullman
This paper taxonomize the varieties of ideas that are sometimes called the "universal relation assumption" and considers some of the arguments pro and con.
ACM Transactions on Database SystemsTree queries
74 Citations1982Nathan Goodman, Oded Shmueli
It is argued, qualitatively, that queries which imply a tree schema are easier to process than those implying a cyclic schema, and the study of the semijoin operator is extended.
Assumptions in relational database theory
62 Citations1982Paolo Atzeni, D. Stott Parker
The purpose of the present paper is to clarify many of the existing assumptions, and point out weaknesses, and to evaluate recent suggestions that certain assumptions may be useful for modeling "real world" databases.
Horn clauses and database dependencies (Extended Abstract)
50 Citations1980Ronald Fagin
The purpose of this paper is to help bring order to the chaos by presenting certain mathematical properties shared by all of these dependencies by introducing the concept of “faithfulness”, and showing that IDs and EIDs are faithful, whereas slight variations are not necessarily faithful.
Minimal Coverings of Acyclic Database Schemata
19 Citations1984Giorgio Ausiello, Aurora D’Atri +1 more
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.
Connections in acyclic hypergraphs
19 Citations1982David Maier, Jeffrey D. Ullman
A sense in which the equivalence between blocks and biconnected components that holds in ordinary graph theory can be generalized to hypergraphs is demonstrated.
The revenge of the JD
11 Citations1983David Maier, Jeffrey D. Ullman +1 more
If the user's view is the representative instance, then the ability to answer queries about the universal relation, by applying relational algebra to the actual database, is equivalent to a "boundedness" condition on the dependencies of the database scheme.