Optimization of a subclass of conjunctive queries
type: Item
instance of: scholarly article
title: Optimization of a subclass of conjunctive queries
zbMATH Open document ID: 0815.68048
DOI: 10.1007/BF01185403
author: Joachim Biskup
author: Pratul Dublish
author: Yehoshua Sagiv
published in: Acta Informatica
publication date: 1995-03-22T00:00:00Z
review text: The optimization problem for a subclass of conjunctive queries which is formed by the union of the class of fan-out free queries and a subclass of typed fan-out queries is investigated. The typed fan-out queries in this class are obtained from simple tableaux by allowing at most one attribute to violate the simple-tableau property. The optimization problem for several restricted subsets of typed fan-out queries is already known to be NP-hard. It is shown that the queries under consideration possess several useful properties which are then used to obtain an \(O(n^ 2)\) optimization algorithm based on the implication graph technique. The optimization of typed fan-out queries, obtained from simple tableaux by allowing at most two attributes to violate the simple tableau property, is shown to be NP-hard. The optimization of simple tableaux in the presence of functional dependencies is also investigated and is shown to be NP-hard.
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 736400
zbMATH Keywords: query optimization
zbMATH Keywords: otimization problem
zbMATH Keywords: implication graph technique
MaRDI profile type: Publication
cites work: Equivalences among Relational Expressions
cites work: Power of Natural Semijoins
cites work: An \(O(n^ 3)\) algorithm for finding the minimal opaque forest of a convex polygon
cites work: Q3786040
cites work: Q4198056
cites work: Q3691102
cites work: Optimizing Conjunctive Queries that Contain Untyped Variables
cites work: Testing containment of conjunctive queries under functional and inclusion dependencies
cites work: On conjunctive queries containing inequalities
cites work: Q3668890
cites work: Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions
cites work: Equivalences Among Relational Expressions with the Union and Difference Operators
cites work: Ordering conjunctive queries
description: scientific article; zbMATH DE number 736400