On the Desirability of Acyclic Database Schemes

DOI10.1145/2402.322389zbMath0624.68087OpenAlexW2148417962MaRDI QIDQ3026382

David Maier, Catriel Beeri, Ronald Fagin, Mihalis Yannakakis

Publication date: 1983

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2402.322389

zbMATH Keywords

acyclicityhypergraphsrelational databasemultivalued dependenciesjoin dependencydatabase schemesconflict-freedom

Mathematics Subject Classification ID

Hypergraphs (05C65) Information storage and retrieval of data (68P20)

Related Items (only showing first 100 items - show all)

An algorithm for handling many relational calculus queries efficiently. ⋮ Spanning trees in random regular uniform hypergraphs ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Optimal decomposition by clique separators ⋮ Counting Subgraphs in Degenerate Graphs ⋮ A faster algorithm to recognize undirected path graphs ⋮ Local computations in Dempster-Shafer theory of evidence ⋮ Convexity in Graphs and Hypergraphs ⋮ Weighted 2-sections and hypergraph reconstruction ⋮ Unnamed Item ⋮ Matrices with chordal inverse zero-patterns ⋮ Executing join queries in an uncertain distributed environment ⋮ Foundations of compositional models: structural properties ⋮ Allocating relations in a distributed database system ⋮ Marginalization in models generated by compositional expressions ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ On the expressive power of semijoin queries ⋮ Treewidth computation and extremal combinatorics ⋮ Unnamed Item ⋮ Mixed covering arrays on 3-uniform hypergraphs ⋮ Covers of Query Results ⋮ The dynamic complexity of acyclic hypergraph homomorphisms ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Brief Introduction to Probabilistic Compositional Models ⋮ Power surplus solutions for weighted hypergraph communication situations ⋮ Intermittent sampling for statistical process control with the number of defectives ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Compact scheme forests in nested normal form ⋮ Comments on: Sequences of regressions and their independences ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ Structural learning about directed acyclic graphs from multiple databases ⋮ Chordal graphs and their clique graphs ⋮ Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries ⋮ Unnamed Item ⋮ On the impact of running intersection inequalities for globally solving polynomial optimization problems ⋮ Dually chordal graphs ⋮ Weak Cartesian properties of simplicial sets ⋮ Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments ⋮ Computing partial hypergraphs of bounded width ⋮ Twins in Subdivision Drawings of Hypergraphs ⋮ On the complexity of binary polynomial optimization over acyclic hypergraphs ⋮ Hypergraph incidence coloring ⋮ Dynamic Management of Heuristics for Solving Structured CSPs ⋮ Breaking Symmetry of Interchangeable Variables and Values ⋮ Decomposable convexities in graphs and hypergraphs ⋮ Nested Precedence Networks with Alternatives: Recognition, Tractability, and Models ⋮ Reasoning about functional and full hierarchical dependencies over partial relations ⋮ Hypergraph planarity and the complexity of drawing venn diagrams ⋮ An efficient representation of chordal graphs ⋮ Searching for better fill-in ⋮ Decomposition of structural learning about directed acyclic graphs ⋮ Unifying tree decompositions for reasoning in graphical models ⋮ Path-Based Supports for Hypergraphs ⋮ Blocks of Hypergraphs ⋮ CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT ⋮ GLOBAL PROPAGATION IN BAYESIAN NETWORKS VS SEMIJOIN PROGRAMS IN RELATIONAL DATABASES ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ Compatibility, desirability, and the running intersection property ⋮ Berge-acyclic multilinear 0-1 optimization problems ⋮ A REVIEW OF TREE CONVEX SETS TEST ⋮ Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Another view of functional and multivalued dependencies in the relational database model ⋮ Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network ⋮ On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs ⋮ On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay ⋮ Unnamed Item ⋮ Hamiltonian decomposition of complete bipartite \(r\)-hypergraphs ⋮ On axioms constituting the foundation of hypergraph theory ⋮ Robustness to Dependency in Portfolio Optimization Using Overlapping Marginals ⋮ The Running Intersection Relaxation of the Multilinear Polytope ⋮ Decomposability of abstract and path-induced convexities in hypergraphs ⋮ Evidential Networks from a Different Perspective ⋮ Evaluating multiple join queries in a distributed database system ⋮ Binary join trees for computing marginals in the Shenoy-Shafer architecture ⋮ Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach ⋮ A Formal Context for Acyclic Join Dependencies ⋮ Characterization of Optimal Complements of Database Views Defined by Projection ⋮ Coding Theory Motivated by Relational Databases ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Split-freedom and MVD-intersection: A new characterization of multivalued dependencies having conflict-free covers ⋮ Unnamed Item ⋮ Information Algebra ⋮ An invariant for hypergraphs ⋮ Bayesian networks: the minimal triangulations of a graph ⋮ The semijoin algebra and the guarded fragment ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ The existence condition of \(\gamma\)-acyclic database schemes with MVDs constraints. ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Unnamed Item ⋮ View-based propagator derivation ⋮ On matrices, automata, and double counting in constraint programming ⋮ Prediction-hardness of acyclic conjunctive queries ⋮ Enumeration of maximum acyclic hypergraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimal triangulations of graphs: a survey ⋮ A vertex incremental approach for maintaining chordality

This page was built for publication: On the Desirability of Acyclic Database Schemes