Formal Properties of Conjunctive Queries
Conjunctive queries are one of the great success stories of database theory in that many interesting problems that are computationally hard or undecidable for larger classes of queries are feasible for conjunctive queries. For example, consider the query containment problem. We write for two database relations of the same schema if and only if each tuple occurring in also occurs in . Given a query and a relational database instance, we write the result relation of evaluating the query on the instance simply as . Given two queries and and a database schema, the query containment problem is the problem of deciding whether for all possible database instances over the input database schema, . The main application of query containment is in query optimization: Deciding whether two queries are equivalent is possible by simply checking mutual containment.
The query containment problem is undecidable for relational algebra and SQL but is decidable and NP-complete for conjunctive queries. In fact, it turns out that the query containment problem for conjunctive queries is exactly the same problem as the query evaluation problem. Since queries tend to be small, NP-completeness here is usually considered acceptable. The query containment problem for conjunctive queries is also equivalent to the constraint satisfaction problem.
An important class of conjunctive queries that have polynomial-time combined complexity are the acyclic conjunctive queries. The query evaluation, and thus query containment, is LOGCFL-complete and thus in polynomial time. Acyclicity of conjunctive queries is a structural property of queries that is defined with respect to the query's hypergraph: a conjunctive query is acyclic if and only if it has hypertree-width 1. For the special case of conjunctive queries in which all relations used are binary, this notion corresponds to the treewidth of the dependency graph of the variables in the query (i.e., the graph having the variables of the query as nodes and an undirected edge between two variables if and only if there is an atomic formula or in the query) and the conjunctive query is acyclic if and only if its dependency graph is acyclic.
An important generalization of acyclicity is the notion of bounded hypertree-width, which is a measure of how close to acyclic a hypergraph is, analogous to bounded treewidth in graphs. Conjunctive queries of bounded tree-width have LOGCFL combined complexity.
Unrestricted conjunctive queries over tree data (i.e., a relational database consisting of a binary child relation of a tree as well as unary relations for labeling the tree nodes) have polynomial time combined complexity.
Read more about this topic: Conjunctive Query
Famous quotes containing the words formal, properties and/or queries:
“On every formal visit a child ought to be of the party, by way of provision for discourse.”
—Jane Austen (1775–1817)
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“All I can say, in answer to this kind queries [of friends] is that I have not the distemper called the Plague; but that I have all the plagues of old age, and of a shattered carcase.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)