Next: Using Arguments Other Up: Extensions of the Previous: Quadratic Indexing

# Our Approach

The next sections will describe our approach. Instead of directly presenting our final indexing technique, its components are introduced in order of increasing complexity.

The following part of a PROLOG program (a normalizer producing DNFs of propositional formulas) is used to demonstrate our heuristics for generating index trees:

norm(X, X) :- literal(X).
norm(or(X, Y), or(X, Y)) :- literal(X), literal(Y).
norm(and(X, Y), and(X, Y)) :- literal(X), literal(Y).

norm(or(X, Y), or(X1, Y)) :-
literal(Y),
norm(X, X1).

norm(or(X, or(Y, Z)), W) :-
norm(or(or(X, Y), Z), W).

norm(or(X, and(Y1, Y2)), or(X1, Y12)) :-
norm(X, X1),
norm(and(Y1, Y2), Y12).

norm(and(X, Y), and(X1, Y)) :-
literal(Y),
norm(X, X1).

norm(and(X, and(Y, Z)), W) :-
norm(and(and(X, Y), Z), W).

norm(and(X, or(Y1, Y2)), and(X1, Y12)) :-
norm(X, X1),
norm(or(Y1, Y2), Y12).

Only the following information (entirely extracted from the clause heads) is used for the index tree generation; all algorithms in this paper can easily be extended to use additional information such as inner structure arguments and ``guards'' (see section 12.1):

The following sections describe the heuristics for our indexing techniques:

• 1N-Algorithm: One Argument / No Variables
• MN-Algorithm: Multiple Arguments / No Variables
• MBN-Algorithm: MN-Algorithm / Breadth Oriented
• MDN-Algorithm: MN-Algorithm / Depth Oriented
• 1V-Algorithm: One Argument / Variables
• MV-Algorithm: Multiple Arguments / Variables

Michael Sintek - sintek@dfki.uni-kl.de