On the Desirability of Acyclic Database Schemes
From MaRDI portal
Publication:3026382
DOI10.1145/2402.322389zbMATH Open0624.68087OpenAlexW2148417962MaRDI QIDQ3026382FDOQ3026382
Authors: Catriel Beeri, Ronald Fagin, David Maier, 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
Recommendations
hypergraphsacyclicitymultivalued dependenciesrelational databasejoin dependencydatabase schemesconflict-freedom
Cited In (only showing first 100 items - show all)
- Computing the maximum-entropy extension of given discrete probability distributions
- Decomposing a relation into a tree of binary relations
- Cycle structure of edge labelled graphs
- On some partial line graphs of a hypergraph and the associated matroid
- On axioms constituting the foundation of hypergraph theory
- An algorithm for handling many relational calculus queries efficiently.
- An invariant for hypergraphs
- Allocating relations in a distributed database system
- Computing the union join and subset graph of acyclic hypergraphs in subquadratic time
- Chordal graphs and their clique graphs
- Minimal vertex separators of chordal graphs
- On the complexity of constrained Nash equilibria in graphical games
- Breaking Symmetry of Interchangeable Variables and Values
- On the complexity of binary polynomial optimization over acyclic hypergraphs
- Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures
- Interaction-free multivalued dependency sets
- Hierarchical fault diagnosis for discrete-event systems under global consistency
- Hamiltonian decomposition of complete bipartite \(r\)-hypergraphs
- A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs
- Matrices with chordal inverse zero-patterns
- Title not available (Why is that?)
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- An efficient representation of chordal graphs
- Weighted hypertree decompositions and optimal query plans
- On the complexity of division and set joins in the relational algebra
- Twins in Subdivision Drawings of Hypergraphs
- The tree projection theorem and relational query processing
- Robustness to dependency in portfolio optimization using overlapping marginals
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Fuzzy functional dependencies and Bayesian networks
- Title not available (Why is that?)
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Local consistency for extended CSPs
- Arboricity: an acyclic hypergraph decomposition problem motivated by database theory
- Wheel-Free Deletion Is W[2]-Hard
- Studies on hypergraphs. I: Hyperforests
- Enumeration complexity of conjunctive queries with functional dependencies
- Enumeration complexity of conjunctive queries with functional dependencies
- On the notion of cycles in hypergraphs
- A universal table model for categorical databases
- Testing arbitrary subhypergraphs for the lossless join property
- Paths and cycles of hypergraphs
- Optimal distributed execution of join queries
- NP-complete problems simplified on tree schemas
- On the existence of acyclic views in a database scheme
- Counting acyclic hypergraphs
- The semijoin algebra and the guarded fragment
- A characterization of multivalued dependencies equivalent to a join dependency
- Acyclic join dependency and data base projections
- Enumeration of maximum acyclic hypergraphs
- GYO reductions, canonical connections, tree and cyclic schemas, and tree projections
- A formal framework for independence with respect to transactions in the universal relation model
- Unifying functional and multivalued dependencies for relational database design
- Recognizing different types of beta-cycles in a database scheme
- Decomposable convexities in graphs and hypergraphs
- An implementation of the iterative proportional fitting procedure by propagation trees.
- Closures of database hypergraphs
- Local and global relational consistency
- Probability propagation
- Equivalence between hypergraph convexities
- Hypergraph planarity and the complexity of drawing venn diagrams
- Nested Precedence Networks with Alternatives: Recognition, Tractability, and Models
- Spanning trees in random regular uniform hypergraphs
- A hybrid tractable class for non-binary CSPs
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Uniform Constraint Satisfaction Problems and Database Theory
- Connections in acyclic hypergraphs
- On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
- Dynamic Management of Heuristics for Solving Structured CSPs
- Reformulation of global constraints based on constraints checkers
- Connectivity and equilibrium in random games
- Compositional models and conditional independence in evidence theory
- A vertex incremental approach for maintaining chordality
- Treewidth computation and extremal combinatorics
- Hypertree decompositions and tractable queries
- A linear time recognition algorithm for proper interval graphs
- Title not available (Why is that?)
- Canonical and monophonic convexities in hypergraphs
- On hypergraph acyclicity and graph chordality
- On improving dependency implication algorithms
- A unified theory of structural tractability for constraint satisfaction problems
- Structural learning about directed acyclic graphs from multiple databases
- A fast algorithm for query optimization in universal-relation databases
- Decomposition of structural learning about directed acyclic graphs
- Unifying tree decompositions for reasoning in graphical models
- A complete axiomatization of full acyclic join dependencies
- Finite approximatization of languages for representation of system properties: Axiomatization of dependencies
- Minimal triangulations of graphs: a survey
- Lossless outer joins with incomplete information
- Decomposition of a hypergraph by partial-edge separators
- A practical algorithm for making filled graphs minimal
- Decomposing constraint satisfaction problems using database techniques
- Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
- Tractability-preserving transformations of global cost functions
- The cyclicity of a hypergraph
- Fast minimal triangulation algorithm using minimum degree criterion
- A comparison of structural CSP decomposition methods
- Path-based supports for hypergraphs
- Path-based supports for hypergraphs
- Binary join trees for computing marginals in the Shenoy-Shafer architecture
This page was built for publication: On the Desirability of Acyclic Database Schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3026382)
