On the Desirability of Acyclic Database Schemes
From MaRDI portal
Publication:3026382
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
acyclicityhypergraphsrelational databasemultivalued dependenciesjoin dependencydatabase schemesconflict-freedom
Related Items
Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, Optimal distributed execution of join queries, The parallel solution of domination problems on chordal and strongly chordal graphs, A distributed algorithm for determining minimal covers of acyclic database schemes, On improving dependency implication algorithms, Incorporating processor costs in optimizing the distributed execution of join queries, Computing the union join and subset graph of acyclic hypergraphs in subquadratic time, A complete axiomatization of full acyclic join dependencies, On the complexity of constrained Nash equilibria in graphical games, Tractability-preserving transformations of global cost functions, Distributed revision of composite beliefs, Existence of extensions and product extensions for discrete probability distributions, Characterization of desirable properties of general database decompositions., Reformulation of global constraints based on constraints checkers, Probability propagation, Hierarchical fault diagnosis for discrete-event systems under global consistency, Minimizing the response time of executing a join between fragmented relations in a distributed database system, Interaction-free multivalued dependency sets, Structure learning in Bayesian networks using regular vines, On hypergraph acyclicity and graph chordality, Tree clustering for constraint networks, Simplicial decompositions of graphs: A survey of applications, Algorithmic aspects of intersection graphs and representation hypergraphs, A special case for subset interconnection designs, Recognizing single-peaked preferences on a tree, Finite approximatization of languages for representation of system properties: Axiomatization of dependencies, Relational decomposition and structural analysis of systems, The cyclicity of a hypergraph, On computing minimal models, Weighted hypertree decompositions and optimal query plans, On the complexity of division and set joins in the relational algebra, Discovering implied constraints in precedence graphs with alternatives, Local and global relational consistency, Matching and multidimensional matching in chordal and strongly chordal graphs, Equivalence between hypergraph convexities, Fuzzy functional dependencies and Bayesian networks, On the discovery of the cycle-axiom of hypergraphs, A hybrid tractable class for non-binary CSPs, The power of propagation: when GAC is enough, Decomposing a relation into a tree of binary relations, Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time, Path-based supports for hypergraphs, A universal table model for categorical databases, Testing arbitrary subhypergraphs for the lossless join property, Inferring multivalued dependencies from functional and join dependencies, An alternative characterization of a Bayesian network., An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, A unified theory of structural tractability for constraint satisfaction problems, Counting the number of independent sets in chordal graphs, An inertia formula for Hermitian matrices with sparse inverses, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, On some partial line graphs of a hypergraph and the associated matroid, Clique trees of infinite locally finite chordal graphs, Homology cycles and dependent cycles of hypergraphs, Design of desirable relational database schemes, Structure identification in relational data, Hypertree decompositions and tractable queries, Studies on hypergraphs. I: Hyperforests, Connectivity and equilibrium in random games, Fast minimal triangulation algorithm using minimum degree criterion, Compositional models and conditional independence in evidence theory, Chordality properties on graphs and minimal conceptual connections in semantic data models, A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs, Lossless outer joins with incomplete information, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Counting clique trees and computing perfect elimination schemes in parallel, A linear time recognition algorithm for proper interval graphs, A characterization of finite fd-acyclicity, A fast algorithm for query optimization in universal-relation databases, Approximations for subset interconnection designs, Laminar structure of ptolemaic graphs with applications, Connections in acyclic hypergraphs, Decomposition of a hypergraph by partial-edge separators, Arboricity: an acyclic hypergraph decomposition problem motivated by database theory, Minimal vertex separators of chordal graphs, Paths and cycles of hypergraphs, Local consistency for extended CSPs, Enumeration complexity of conjunctive queries with functional dependencies, Estimating high-dimensional intervention effects from observational data, Canonical and monophonic convexities in hypergraphs, On the notion of cycles in hypergraphs, A practical algorithm for making filled graphs minimal, A comparison of structural CSP decomposition methods, NP-complete problems simplified on tree schemas, A characterization of multivalued dependencies equivalent to a join dependency, On the existence of acyclic views in a database scheme, Interval graphs and related topics, Acyclic join dependency and data base projections, The tree projection theorem and relational query processing, 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, Computing the maximum-entropy extension of given discrete probability distributions, Unifying functional and multivalued dependencies for relational database design, Recognizing different types of beta-cycles in a database scheme, Fixed-parameter complexity in AI and nonmonotonic reasoning, Unique complements and decompositions of database schemata, An implementation of the iterative proportional fitting procedure by propagation trees., Decomposing constraint satisfaction problems using database techniques, Counting acyclic hypergraphs, 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
