Power of Natural Semijoins
From MaRDI portal
Publication:3923637
DOI10.1137/0210059zbMath0469.68090OpenAlexW2046649829MaRDI QIDQ3923637
Nathan Goodman, Philip A. Bernstein
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210059
Related Items
An algorithm for handling many relational calculus queries efficiently., The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Optimization of a subclass of conjunctive queries, Finding minimum height elimination trees for interval graphs in polynomial time, Clique tree generalization and new subclasses of chordal graphs, A clique tree algorithm for partitioning a chordal graph into transitive subgraphs, On the expressive power of semijoin queries, Towards a characterization of leaf powers by clique arrangements, Graph searches and their end vertices, Multigraph representations of hierarchical loglinear models, Complexity and approximability of the happy set problem, Weighted hypertree decompositions and optimal query plans, Graph Bisection with Pareto Optimization, On the complexity of division and set joins in the relational algebra, The dynamic complexity of acyclic hypergraph homomorphisms, Distributed minimum vertex coloring and maximum independent set in chordal graphs, Minimum Average Distance Clique Trees, Tree projections and structural decomposition methods: minimality and game-theoretic characterization, Corrigendum to: ``Complexity and approximability of the happy set problem, Finding intersection models: from chordal to Helly circular-arc graphs, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Subgraph trees in graph theory, On the complexity of core, kernel, and bargaining set, Characterizing and computing the structure of clique intersections in strongly chordal graphs, Intersection representations of matrices by subtrees and unicycles on graphs, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, A REVIEW OF TREE CONVEX SETS TEST, On some partial line graphs of a hypergraph and the associated matroid, Clique trees of infinite locally finite chordal graphs, Cycle structure of edge labelled graphs, Tree decomposition and discrete optimization problems: a survey, Hypertree decompositions and tractable queries, Querying incomplete information in semistructured data, On the power of structural decompositions of graph-based representations of constraint problems, Dynamic programming and planarity: improved tree-decomposition based algorithms, Computing role assignments of chordal graphs, Unnamed Item, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Representing triangulated graphs in stars, Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs, The clique-separator graph for chordal graphs, Connections in acyclic hypergraphs, Tree Projections: Game Characterization and Computational Aspects, On the notion of cycles in hypergraphs, Uniform Constraint Satisfaction Problems and Database Theory, A comparison of structural CSP decomposition methods, NP-complete problems simplified on tree schemas, A characterization of multivalued dependencies equivalent to a join dependency, Structural tractability of enumerating CSP solutions, Interval graphs and related topics, The tree projection theorem and relational query processing, Intersection graphs of \(k\)-acyclic families of subtrees and relational database query processing., GYO reductions, canonical connections, tree and cyclic schemas, and tree projections, Unnamed Item