Browse Prior Art Database

Optimal Application of Selection in Hierarchy Tabulation

IP.com Disclosure Number: IPCOM000044426D
Original Publication Date: 1984-Dec-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Larner, A: AUTHOR

Abstract

Given a collection of data which is to be accessed along a hierarchical path in order to generate a row in a table of results and a number of criteria which determine those rows which are to be kept and those which are to be deleted from the table, it may be more efficient to apply some of these criteria before accessing the path from top to bottom. This article addresses the problem of application of criteria at the earliest time, that is, as near to the top of the hierarchical path as possible, in order to minimize the total access time of the tabulation in a system executing queries on, or extracting data from, a hierarchical data base.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 34% of the total text.

Page 1 of 3

Optimal Application of Selection in Hierarchy Tabulation

Given a collection of data which is to be accessed along a hierarchical path in order to generate a row in a table of results and a number of criteria which determine those rows which are to be kept and those which are to be deleted from the table, it may be more efficient to apply some of these criteria before accessing the path from top to bottom. This article addresses the problem of application of criteria at the earliest time, that is, as near to the top of the hierarchical path as possible, in order to minimize the total access time of the tabulation in a system executing queries on, or extracting data from, a hierarchical data base. Minimization of data base access in, and therefore efficiency of execution of, tabulation of hierarchically accessed data may be achieved by conversion of the restriction of the tabulation to conjunctive normal form, sorting of criteria within conjuncts and of conjuncts themselves by level of pertinent segment, applying each criterion at its level of pertinence, ceasing evaluation of a conjunct on a TRUE evaluation of one of its criteria, and avoiding iteration of access at lower levels on a FALSE evaluation of the last criterion in any conjunct. Hierarchy Tabulation We assume paths (P1, P2, ... Pm) with each path, Pu, comprising an ordered set of segments (su1, su2, ... sun). Segments of common index, j (that is, for all u the segments suj), are said to be of common type and are of common name and format (accordingly, they contain fields of the same names and formats). Two paths may overlap to some degree at the top, that is, paths Pu and Pv may be such that for some segment type, j, suj is the same segment as svj, suj-1 as svj-1, ..., su1 as sv1. Paths are read in a sequence depending on their degree of overlap such that each segment is read only once. Thus, segment s11 is read first, then the remainder of all paths Pu such that s11 is the same segment as su1; within this remainder, segment s12 is read first, then the remainder of all paths Pv such that s11 is the same segment as sv1 and s12 as sv2, and so on. The output of this process is, at its greatest, a table each row of which is derived from one path. In general, however, not all these rows are required. The rows required are specified by a restriction which is an expression comprising a truth function of criteria, where each criterion is some function returning a truth value (TRUE or FALSE) and having as operands fields of common type in each path. If evaluation of the restriction for a path gives the value TRUE, then a row is created from the values of fields in the segments of that path, otherwise not. Efficiency of Access Clearly, the required tabulation could be obtained by reading all paths and then applying the restriction to each, but this might be very inefficient. Suppose that in segments of type 1 there is a field F1 and that the restriction is simply 'F1 has the value...