Browse Prior Art Database

N Ary Join for Processing Query by Example

IP.com Disclosure Number: IPCOM000087010D
Original Publication Date: 1976-Nov-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 5 page(s) / 46K

Publishing Venue

IBM

Related People

Niebuhr, KE: AUTHOR [+2]

Abstract

Given a relational data base, the present method provides an efficient way of performing the join operations needed to solve a query-by-example query. In an earlier publication [1], the joining was accomplished by a sequence of binary joins, each of which produced a temporary relation which could be involved in subsequent joins. That approach had the following potential disadvantages: (1) Overhead associated with storing the data tuples in the temporary relations resulting from the joins. (2) Because all possible solutions were carried throughout the sequence of joins, the cardinalities of the temporary relations could become very large for a modest size data base. (3) Inversions were not available in the temporary results so they had to be created, if needed.

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 35% of the total text.

Page 1 of 5

N Ary Join for Processing Query by Example

Given a relational data base, the present method provides an efficient way of performing the join operations needed to solve a query-by-example query. In an earlier publication [1], the joining was accomplished by a sequence of binary joins, each of which produced a temporary relation which could be involved in subsequent joins. That approach had the following potential disadvantages:
(1) Overhead associated with storing the data tuples in the

temporary relations resulting from the joins.
(2) Because all possible solutions were carried throughout the

sequence of joins, the cardinalities of the temporary

relations could become very large for a modest size data

base.
(3) Inversions were not available in the temporary results so they

had to be created, if needed. Moreover, existing inversions

were frequently not used. The proposed method overcomes all of these shortcomings with a single operation which is called the n-ary join.

Terminology.
A. Query Tuples and Data Tuples.

It is necessary to distinguish between two kinds of tuples. The user constructs a query-by-example query in the form of "query tuples" within skeleton tables [1,2]. Corresponding to each skeleton table and its query tuples is a relation containing "data tuples". The query tuples specify the constraints which the data tuples must satisfy in order to be included in the answer to a query. B. Selection and Linkage Constraints.

The data tuples which comprise the answer to a query must satisfy two kinds of constraints, "selection" constraints and "linkage" constraints. Selection constraints are intra-tuple conditions specified by a query tuple. Examples of selection constraints are: *Column 3 must have a value equal to 10.

*The value in column 5 must be greater than the value in

column 2. In general, a selection constraint is a function over the entries in a single data tuple which evaluates to true or false.

Linkage constraints are inter-tuple conditions specified between multiple query tuples. Examples of linkage constraints are: *The value in column 3 of the data tuple in R2 must be greater

than the value of column 5 of the data tuple currently

selected from R1.

*The set of column 4 values for all data tuples in a relation,

R2, which have the same value in column 3 of the data tuple in

R2 under investigation (column 3 is a "grouper" column) must

be contained in a similarly defined set for the currently

selected data tuple of a relation R1. ("set join", see [1]).
C. Search List.

1

Page 2 of 5

Prior to initiating the n-ary join operation, the query tuples are organized in a list called the Search List. This list determines the order in which the query tuples and their underlying data relations are processed with the query tuple at the top being processed first. Explicit join query tuples are not placed on the Search List. If explicit join tuples exist in a query, their "print" elements are temporarily transferred to the appropr...