# Implementation of Conjunctive Queries in Relational Data Base

Original Publication Date: 1976-Mar-01

Included in the Prior Art Database: 2005-Mar-02

## Publishing Venue

IBM

## Related People

## Abstract

Given a conjunctive query, it is translated into a corresponding graph in which a small cycle cutting set of nodes is used to answer the query.

**This text was extracted from a PDF file.**

**At least one non-text object (such as an image or picture) has been suppressed.**

**This is the abbreviated version, containing approximately 43% of the total text.**

__Page 1 of 7__**Implementation of Conjunctive Queries in Relational Data Base **

Given a conjunctive query, it is translated into a corresponding graph in which a small cycle cutting set of nodes is used to answer the query.

Given a relational data base [1] with relations S(1), S(2),

..., a conjunctive query is of the form:

(Image Omitted)

where w, y are vectors of a variable, and Phi is a formula consisting of a conjunction of the form:

(Image Omitted)

where the z(i,j)'s are either constants, or variables from w, y. The answer of such a query is the set values of vectors w for which the formula y.Phi(w, y) is true in the data base.

Conjunctive queries arise frequently in query systems [2].

Given a conjunctive query it is simplified [3] into an equivalent query with only unary and binary relations, and the result is also a conjunctive query, of the form:

(Image Omitted)

where Phi'(w,x) is of the form:

(Image Omitted)

where the z(i), u(i), v(i) are either constants, or variables taken from w, x,
relations R(i)'s may include some relations other than the S(i)'s (created in the
simplification step), R(j)(1), R(j)(2), ... are unary relations, and Rk(k)(1), R(k)(2),

... are binary relations.

For each vector of constants c for the variable w, the question to be answered is:

(Image Omitted)

This is the problem addressed below. Below Phi' means Phi'(c,x)

L1. Constant terms. For all terms of the form R(i)(a), R(i)(a(1),a(2))in Phi' where a, a(1), a(2) are constants, check to see if each is true. If not, (1) is false.

L2. Construct the graph. Otherwise, construct a labeled directed multigraph having one node labeled with each variable in x, and one edge labeled with relation R(i), from node labeled x(1) to x(2) if there is an atomic formula R(i)(x(1),x(2)) in Phi'.

L3. Associate domains. Also associate with each node labeled, say x, a domain D(x) of possible values for x. D(x) is subject to

1

__Page 2 of 7__change as computation proceeds, and if for any x, D(x) ever becomes
empty, computation stops, and (1) is false. For each x, D(x) is
initialized to the intersection of the following sets:

(i) The universe of elements in the data base.

(ii) R(i) for each term R(i)(x) in Phi'.

(iii) The image of a in R(i) (where a is some constant)

for each term R(i)(a,x) in Phi'.

(iv) The preimage of a in R. (where a is some constant),

for each term R(i)(x,a) in Phi'.

(v) The projection of R(i) on the first coordinate,

for each term R(i)(x,x(1)) in Phi' for any x(1).

(vi) The projection of R(i) on the second coordinate,

for each term R(i)(x(1),x) in Phi' for any x(1).

L4. Self-Loops. If there is a node (labeled) x having a self-loop (edge from x to itself) labeled R, then replace D(x) by D(x) Omega {a: R(a,a)} and delete this self-loop. Continue until all self-loops are removed.

L5. Nodes with no edges. Delete nodes with zero edges. (Note: if for any node x, D(x) is empty computation stops, and (1) is false.)

Below, an edge is considered from x(1) to x(2) labeled by relation R...