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 (54)
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
This page was built for publication: Power of Natural Semijoins
