The tree projection theorem and relational query processing

DOI10.1016/0022-0000(84)90076-XMaRDI QIDQ1061514zbMATH OpenFDO

Authors Nathan Goodman, Oded Shmueli

Publication date 1984

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(84)90076-X

zbMATH Keywords

natural join queriesrelational database schemastree schema

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Review text

The class of relational database schemas can be partitioned into two subclasses: tree schemas and cyclic schemas. This partitioning has consequences in several areas of database theory, including query processing, dependency theory, and schema design. Query processing consequences of the partitioning are examined. Queries, called natural join queries, that compute the natural join of all relations in the database projected onto a prescribed set of attributes are considered. Also programs that solve natural join queries by applying joins, semijoins, and projections in some order are considered. It is shown that if such a program solves a natural join query then it must create an embedded tree schema, called a tree projection. Conversely, if a program creates a tree projection then the program augmented with a small number of semijoins solves the query. Thus, forming a tree projection is the crux of the query processing problem for natural join queries.

Recommendations

• Acyclic join dependency and data base projections
• On Determining Tree Query Membership Of A Distributed Query
• Complexity of Views: Tree and Cyclic Schemas
• The complexity of evaluating relational queries
• Joins and solutions of the projection synthesis problem in relational databases. II

Cites work

• A simplied universal relation assumption and its properties
• Acyclic join dependency and data base projections
• Connections in acyclic hypergraphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• Equivalences among Relational Expressions
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maximal objects and the semantics of universal relation databases
• NP-complete problems simplified on tree schemas
• On Determining Tree Query Membership Of A Distributed Query
• On the Desirability of Acyclic Database Schemes
• Power of Natural Semijoins
• Syntactic Characterization of Tree Database Schemas
• Tree queries
• Using Semi-Joins to Solve Relational Queries

Cited in

(9)

• Relational depth-first-search with applications
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• Structural tractability of enumerating CSP solutions
• Intersection graphs of \(k\)-acyclic families of subtrees and relational database query processing.
• On Determining Tree Query Membership Of A Distributed Query
• Tree projections: Game characterization and computational aspects
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• GYO reductions, canonical connections, tree and cyclic schemas, and tree projections

Describes a project that uses

Uses Software

• INGRES

This page was built for publication: The tree projection theorem and relational query processing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1061514)