Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-09-30
2002-09-24
Choules, Jack (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06456998
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to a computer-implemented relational database management system, and more particularly, to the efficient processing of parent-child relationships in a relational database management system.
2. Description of Related Art
Data in an Relational DataBase Management System (RDBMS) is organized into one or more tables that are comprised of rows and columns of data, wherein the rows are known as tuples and the columns are known as attributes. A database will typically have many tables and each table will typically have multiple tuples and multiple attributes. Users formulate relational operations on the tables, rows, and attributes, either interactively, in batch files, or embedded in host languages, such as C and COBOL.
It is common, in Internet “text mining” and “business intelligence” applications, for example, for tuples or attributes to be related to one another by one or more concepts or groups. For example, an Internet search engine works efficiently when a large collection of documents (e.g., web pages) are described and queried by a set of descriptive “concepts” (stemmed keywords after filtering stopwords and/or “characteristics” obtained by various means of parsing document content). Concept relationships are a natural way to provide meta-data. In particular, concept relationships often comprise parent-child relationships.
The Internet search engine may use tuples to represent documents and the attributes of those tuples may comprise pointers that define one or more concepts or groups among the documents. It may be necessary in such an application to access the tuples and then ascertain whether or not a tuple is or is not a descendant of another tuple in a particular group. One example is “document” ranking of documents or pages in an Internet “text mining” application by updating aggregate counts of various “concepts” derived from the text of a search query.
In such applications, the computation of aggregate functions for each individual concept or group is a basic, often repeated, operation. Often, an aggregate grouping function is used to rank one collection versus another. For example, an Internet search engine may use an aggregate grouping function to rank and/or organize documents or pages found by the Internet search engine.
A. Klug,
Access Path in the “Abe” Statistical Query Facility
, Proc. ACM SIGMOD, 1982, pp. 161-172, which is incorporated by reference herein, teaches that special treatment should be given to aggregation of groups. Efficiency for the aggregate grouping operator is addressed in D. J. Haderle, and E. J. Lynch,
Evaluation of Column Function on Grouped Data During Data Ordering
, IBM Technical Disclosure Bulletin, Mar. 10, 1990, pp. 385-386, which is incorporated by reference herein.
There remains, however, a need in the art for new techniques for representing such relationships and for processing queries relating to these relationships. The present invention provides these needed techniques.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, article of manufacture, and data structure for efficiently identifying parent-child relationships. The parent-child relationships are encoded into a matrix, wherein a particular member is represented by a particular row and a particular column of the matrix. A value at an intersection of a specific one of the rows and a specific one of the columns indicates whether a parent-child relationship exists between the member represented by the row and the member represented by the column. Thereafter, matrix operations may be applied to the matrix.
An object of the invention is to provide an improved system for encoding parent-child relationships. Another object of the present invention is to encode such relationships in a manner that allows various operations to be performed on the encoding. Yet another object of the present invention is to identify multiple levels of ancestors/descendants of a member based on the encoding.
REFERENCES:
patent: 5303367 (1994-04-01), Leenstra, Sr. et al.
patent: 5355317 (1994-10-01), Talbott et al.
patent: 5359523 (1994-10-01), Talbott et al.
patent: 5787439 (1998-07-01), Taysom
patent: 6094650 (2000-07-01), Stoffel et al.
OTMMATX.TXT -Matrix Transformation Tutorial (or if you prefer, a proven antidote for VLA 3d tutorials), Zach Mortensen, © 1995 found at www.aha.ru/-perrago/articles/matrix.txt on Sep. 30, 2000, 1995.*
“Representation of Tree Data Structures as Matrices Suitable for User Defined Traversing.” IBM Technical Disclosure Bulletin, Apr. 1972, vol. 14, No. 11, pp. 3553-3554.*
“Representation of Tree Data Structures for Data Manipulation and Search Operations.” IBM Technical Disclosure Bulletin, Apr. 1972, vol. 14, No. 11, pp. 3521-3522.*
Haderle, D.J. et al., Evaluation of Column Function on Grouped Data During Data Ordering, IBM Technical Bulletin No. 10B, vol. 32, Mar. 1990,. pp. 385-386.
Klug, A., “Access Path in the ‘Abe’ Statistical Query Facility”, Proc. ACM SIGMOD, 1982, pp. 161-173.
Bui Thuan Quang
Iyer Balakrishna Raghavendra
Choules Jack
Gates & Cooper LLP
International Business Machines - Corporation
LandOfFree
Efficient processing of parent-child relationships in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient processing of parent-child relationships in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient processing of parent-child relationships in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2912878