A method for handling a database containing objects extending into a coordinate system, representing a multidimensional reality. The coordinate system is divisible into a plurality of defined, multidimensional intervals. Each time an object is entered into the database, the method determines the multidimensional intervals into which the object extends. For each of these intervals, the method determines the number of objects extending into the interval and compares the number of objects with a predetermined threshold value. If the threshold value is exceeded, the interval is divided into at least two smaller intervals, in order to limit the number of objects within any interval. Each interval is linked to a set of objects extending into that interval, and each object is linked to a set of intervals into which the object at least partly extends.

An apparatus, program product and method that employ a dynamic use of Look Ahead Predicate Generation that will enable the database, database engine, and/or query optimizer to alter the processing of a query, and react to sub-optimal access plan selection and additional factors arising after processing has begun, to heal many poor performing queries. Conventional use of LPG requires the query optimizer to decide whether or not to use LPG before the processing of a query begins. As a result, the query optimizer may not only make sub-optimal decisions, but the query optimizer may not consider additional factors that may arise as the query is processing. However, the dynamic use of LPG allows predicates to be built after processing of the query has started and the ability to alter the query's processing to improve query performance.

According to the invention, a method is provided for forming an information closure of a plurality of rows in a listing stack built by a wrapper program for accessing semistructured information. This method includes removing a first row from the listing stack and computing a cross product of the fields in the first row. A step of adding this cross product to a list of accepted rows can also be part of the method. For each remaining row in the listing stack, the method includes a step of computing a selective cross product according to a plurality of steps. In one step, a result is initialized to empty. Then, for each row in the list of accepted rows, a step of determining for a first new row from the accepted row, extended with the non-empty fields of the remaining row is performed. The method can also include a step of determining a second new row from the remaining row, extended with the non-empty fields in the accepted row. Thereupon, a step of adding the two new rows to the result can be performed. Repeating the determining steps and the adding step for all rows in the list of accepted rows, and removing from the result any identical rows can provide an information closure.

An improved mechanism for processing a multiple table query includes: determining if any tables in the query require materialization; for each table in the query that requires materialization, deriving at least one join predicate on a join column; determining if any tables earlier in a join sequence for the query has same join predicates; and applying the at least one derived join predicate to an earlier table in the join sequence, if there is at least one table earlier in the join sequence that has the same join predicate. This significantly reduces the number of rows that are joined before arriving at the final result.

According to the invention, a system and method for extracting information from a semistructured information source. The system includes a listing stack for holding extracted information. A means for matching at least one extractor to the semistructured information to return a list of potential matches is also included. The system can also include a means for iterating through the list of potential matches and a means for retrieving information from a particular match in the list of potential matches. A means for adding a particular match into the listing stack can also be part of the system.