quoestion on index/1

[Lukas Degener-2]

Hi,
I was reading through the online help entry for index/1.
There are two things that I am not sure I understand:

"Indexing as specified by this predicate uses a quick but linear scan."
Does this mean that the process of creating an index uses a linear scan,
or that index lookups are linear?

Then further down, there is this subclass example.
It is recommended there that if one wants to use the predicate
sub_type/2 for both finding subtypes and supertypes, one should resort
to index/1. But on the other hand, it is said that lookups will still be
linear - which sounds dramatically worse than those of the hash index
structure that is used by default.

What is this index/1 thing good for, if the lookup is still linear? The
manual states that "this type of indexing makes selecting clauses much
faster". Could you give more details on what this indexing actually does?


And finally, at least for dynamic predicates with a lot of clauses,
wouldn't it make more sense to use two predicates (one for each
"direction")?
Something like this:

:- dynamic sub_type_X/2, sub_type_XX/2.

sub_type(Sub,Super):-
    (    nonvar(Super)
    ->  sub_type_X(Sub,Super)
    ;   sub_type_XX(Super,Sub)
    ).

TIA + Regards,
--lu

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Jan Wielemaker]

Lukas,

On Wednesday 07 May 2008 10:59, Lukas Degener wrote:
> I was reading through the online help entry for index/1.
> There are two things that I am not sure I understand:
>
> "Indexing as specified by this predicate uses a quick but linear scan."
> Does this mean that the process of creating an index uses a linear scan,
> or that index lookups are linear?

Both :-)

> Then further down, there is this subclass example.
> It is recommended there that if one wants to use the predicate
> sub_type/2 for both finding subtypes and supertypes, one should resort
> to index/1. But on the other hand, it is said that lookups will still be
> linear - which sounds dramatically worse than those of the hash index
> structure that is used by default.
>
> What is this index/1 thing good for, if the lookup is still linear? The
> manual states that "this type of indexing makes selecting clauses much
> faster". Could you give more details on what this indexing actually does?

Each clause has a mask and a key. For the actually goal it also computes
a mask and a key. Now, finding a candidate clause walks the linked list
of clauses and does a simple and-and-compare to decide whether the
clause is a candidate. It is guaranteed that if that simple check fails,
unification will fail too, so it only starts running the clause if this
check succeeds.  The scan is quite fast, but linear.

It isn't good for many things today. It is still quite nice for tables
you need to use with multiple patterns that have no more than 10s of
clauses. The system badly needs proper just-in-time indexing of multiple
arguments as well as deeper indexing.

> And finally, at least for dynamic predicates with a lot of clauses,
> wouldn't it make more sense to use two predicates (one for each
> "direction")?
>
> Something like this:
> :- dynamic sub_type_X/2, sub_type_XX/2.
>
> sub_type(Sub,Super):-
>     (    nonvar(Super)
>     ->  sub_type_X(Sub,Super)
>     ;   sub_type_XX(Super,Sub)
>     ).

Except that you wrote it exactly the wrong way around :-), this is often
the best option in the current system. Some applications may also
consider using the RDF store, which provides persistency as well as
elaborate indexing on triples.

        Cheers --- Jan


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Lukas Degener-2]

Hi Jan,


Jan Wielemaker schrieb:
> Each clause has a mask and a key. For the actually goal it also computes
> a mask and a key. Now, finding a candidate clause walks the linked list
> of clauses and does a simple and-and-compare to decide whether the
> clause is a candidate. It is guaranteed that if that simple check fails,
> unification will fail too, so it only starts running the clause if this
> check succeeds.  The scan is quite fast, but linear.
>  
I think I understand. So the index/1 directive just tells the system to
compute these masks for all clauses, correct?
Wouldn't it be a good idea to do this by default? Or are there any
disadvantages?

> Except that you wrote it exactly the wrong way around :-),
Right, of course. I meant it the other way around.


Thanks for explaining.
--lu

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...