Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Reflexive Index for Relational Databases

IP.com Disclosure Number: IPCOM000105619D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 6 page(s) / 166K

Publishing Venue

IBM

Related People

Hoffman, JL: AUTHOR [+2]

Abstract

Reflexive indexes provide a comprehensive solution to the problem of efficiently accessing reflexive data. Recursive processing is moved from query time to data update time by using incremental maintenance of transitive closure data including retention of accumulation columns. Reflexive indexes allow and support:

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 43% of the total text.

Reflexive Index for Relational Databases

      Reflexive indexes provide a comprehensive solution to the
problem of efficiently accessing reflexive data.  Recursive
processing is moved from query time to data update time by using
incremental maintenance of transitive closure data including
retention of accumulation columns.  Reflexive indexes allow and
support:

o   Single pass access to reflexive data

o   Tracking of depth of reflexion

o   Multiple table reflexion

o   Multiple paths

o   Side paths

o   Index maintenance based on index data, rather than table data

o   Multiple path support

o   Data cycles

o   Precomputed accumulation columns

      The use of accumulation columns with an EVALUATE function
allows reflexive indexes managed by a database management system to
be used to track the values of production rule statements.

      A common problem in the use of relational databases is
accessing tables that reflexively refer to themselves.  Common
examples of this type of table include a bill of materials hierarchy,
manager-employee relations, class enrollment prerequisites, work task
dependency lists, a parent-child hierarchy, or production rule
statements and working memory data.  Accessing this type of data is
typically done through recursive processing, or by building nested
SELECT statements.  However, both of these approaches require
multiple passes over the data to answer all but simple queries.

      Recursive processing during retrieval can be avoided by
maintaining an index on the key field(s) that define the reflexive
relationship.  This is equivalent to maintaining a transitive closure
for this data.  The key idea is to perform the required recursive
processing when the data is updated rather than each time it is
accessed.  Also, the user forming a query no longer need to include
specification of how to recursively retrieve the data.  The reflexive
structure is captured in an index definition rather than in each
query.

      Initial loading of reflexive indexes is based directly on the
table(s) the index covers.  After the index has been built, the index
data, along with individual update data, is often sufficient to build
and maintain the index entries.  Maintenance processing supports
additions and deletions of table entries:

o   at the top of a reflexive chain

o   at the bottom of a reflexive chain

o   in the middle of a reflexive chain

The logic allows for detection of cycles, use of internal path
identifiers, side path support, and calculation of accumulation
columns.

STRUCTURED QUERY LANGUAGE EXTENSIONS

CREATE REFLEXIVE INDEX STATEMENT - In order for a relational database
management system to support reflexive indexes, the Data Definition
Language must be extended to allow their definition.  The required
syntax includes specification of:

o   Parent key

o   Child key

o   Path maintenance option

o   Side paths

o   Accumulation column algorithms

o   Top-d...