Degrees of acyclicity for hypergraphs and relational database schemes
From MaRDI portal
Publication:3026383
DOI10.1145/2402.322390zbMath0624.68088OpenAlexW2104498537MaRDI QIDQ3026383
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.322390
hypergraphsrelational databasejoin dependencydatabase schemesdegree of acyclicityloop-free Bachman diagram
Related Items
Indiscernibility structures induced from function sets : Graph and digraph case, Belief Merging by Examples, The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs, On the non-efficient PAC learnability of conjunctive queries, Dually chordal graphs, On optimization problems in acyclic hypergraphs, On the strength of recursive McCormick relaxations for binary polynomial optimization, On the complexity of binary polynomial optimization over acyclic hypergraphs, CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT, Unnamed Item, The Running Intersection Relaxation of the Multilinear Polytope, Unnamed Item, Querying Geometric Figures Using a Controlled Language, Ontological Graphs and Dependency Lattices, An algorithm for handling many relational calculus queries efficiently., Optimal distributed execution of join queries, The parallel solution of domination problems on chordal and strongly chordal graphs, An algorithm for determining minimal reduced-coverings of acyclic database schemes, Doubly lexical ordering of dense 0--1 matrices, A faster algorithm to recognize undirected path graphs, Incorporating processor costs in optimizing the distributed execution of join queries, Computing the union join and subset graph of acyclic hypergraphs in subquadratic time, The nested universal relation data model, Union Closed Tree Convex Sets, The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs, Characterization of desirable properties of general database decompositions., Reformulation of global constraints based on constraints checkers, Executing join queries in an uncertain distributed environment, Hierarchical fault diagnosis for discrete-event systems under global consistency, Semantic Acyclicity on Graph Databases, Allocating relations in a distributed database system, Domain permutation reduction for constraint satisfaction problems, Minimizing the response time of executing a join between fragmented relations in a distributed database system, Interaction-free multivalued dependency sets, On the desirability of \(\gamma\)-acyclic BCNF database schemes, On hypergraph acyclicity and graph chordality, LATTICES OF STRUCTURE MODELS AND DATABASE SCHEMES, How to draw a hypergraph, Algorithmic aspects of intersection graphs and representation hypergraphs, A note on odd/even cycles, Relational decomposition and structural analysis of systems, Vertices removal for feasibility of clustered spanning trees, Satisfiability of acyclic and almost acyclic CNF formulas, Tractable counting of the answers to conjunctive queries, On the Galois Lattice of Bipartite Distance Hereditary Graphs, Completion to chordal distance-hereditary graphs: a quartic vertex-kernel, The dynamic complexity of acyclic hypergraph homomorphisms, Tree projections and structural decomposition methods: minimality and game-theoretic characterization, The complexity of weighted counting for acyclic conjunctive queries, The Minimal Hitting Set Generation Problem: Algorithms and Computation, Equivalence between hypergraph convexities, The colorful Helly theorem and general hypergraphs, Block-wise construction of tree-like relational features with monotone reducibility and redundancy, Computing partial hypergraphs of bounded width, A polyhedral study of lifted multicuts, Hypergraph incidence coloring, A hybrid tractable class for non-binary CSPs, Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time, Applying a hypergraph to determine the structure of some finite modules, METASYSTEMS AND THE MAXIMUM ENTROPY PRINCIPLE, Testing arbitrary subhypergraphs for the lossless join property, An algebra of probability over finite product spaces, with applications, Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs, Optimising the distributed execution of join queries in polynomial time, Consistency checking and querying in probabilistic databases under integrity constraints, Characterizing and computing the structure of clique intersections in strongly chordal graphs, The Multilinear Polytope for Acyclic Hypergraphs, Connection-trap-free database schemes, Hypergraph modeling and visualisation of complex co-occurence networks, Satisfiability of Acyclic and almost Acyclic CNF Formulas (II), Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, Computing the largest H-eigenvalue of large-scale tensors generated from directed hypergraphs, Berge-acyclic multilinear 0-1 optimization problems, A REVIEW OF TREE CONVEX SETS TEST, Generating hinges from arbitrary subhypergraphs, Inferring null join dependencies in relational databases, On some partial line graphs of a hypergraph and the associated matroid, UNCERTAINTY AND ESTIMATION IN RECONSTRUCTABILITY ANALYSIS, Hypertree decompositions and tractable queries, Entity-relationship diagrams which are in BCNF, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Database query processing using finite cursor machines, On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay, Unnamed Item, Chordality properties on graphs and minimal conceptual connections in semantic data models, Ramsey numbers of Berge-hypergraphs and related structures, Lossless outer joins with incomplete information, Subdivision Drawings of Hypergraphs, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, The Complexity of Acyclic Subhypergraph Problems, Evaluating multiple join queries in a distributed database system, Optimisation and hypergraph theory, On winning strategies in Ehrenfeucht-Fraïssé games, Characterization of Optimal Complements of Database Views Defined by Projection, Coding Theory Motivated by Relational Databases, A fast algorithm for query optimization in universal-relation databases, Laminar structure of ptolemaic graphs with applications, Arboricity: an acyclic hypergraph decomposition problem motivated by database theory, Evaluating Datalog via tree automata and cycluits, Fast and parallel decomposition of constraint satisfaction problems, Canonical and monophonic convexities in hypergraphs, On the notion of cycles in hypergraphs, The existence condition of \(\gamma\)-acyclic database schemes with MVDs constraints., NP-complete problems simplified on tree schemas, On the existence of acyclic views in a database scheme, Interval graphs and related topics, Prediction-hardness of acyclic conjunctive queries, The tree projection theorem and relational query processing, GYO reductions, canonical connections, tree and cyclic schemas, and tree projections, Recognizing different types of beta-cycles in a database scheme, Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT, On the Galois lattice of bipartite distance hereditary graphs, Decomposing constraint satisfaction problems using database techniques
