Re: indexing on facts?

Chuang Liu wrote:
> Hi there:
> I build a large set of facts about network link
> between machines in internet, and want to query a
> network link with particular bandwidth. Because the
> performance of my implementation is very bad, can any
> one help to take a look at my solution, please? Any
> suggestion is appreciated.
> 
> The facts is in the format of
>    band(bandwidth, host1, host2).
> For example: ( 500, 1, 2) means the bandwidth between
> host 1 and host 2 is 500.
> 
> I build a query for network link with bandwidth bigger
> than N defined as
>   find(H1, H2, T) :-
>     [H1, H2] :: [ 1..300],
>     nconnect(H1, H2, T),
>     indomain(H1),
>     indomain(H2).
> 
>   nconnect(H1, H2, T) :-
>     nonvar(T),
>     band(B, H1, H2),
>     B #>= T.
> 
> When I submit a query, I notice every fact is checked,
> is there a way to improve it? For example, using B #>=
> T and a kind of index on B of fact (B, Host1, Host2)
> to filter facts with bandwidth less than T without
> checking them one by one?


Step 1: your code is unnecessarily complicated, you can achieve
the same result with

find(H1, H2, T) :-
	B #>= T,
	band(B, H1, H2).

Like your code, this will enumerate all H1-H2 pairs on backtracking,
e.g. with the facts

band(600, 1, 5).
band(300, 3, 5).
band(500, 2, 7).

you get the behaviour

?- find(H1, H2, 500).
H1 = 1
H2 = 5
Yes (0.00s cpu, solution 1, maybe more)
H1 = 2
H2 = 7
Yes (0.02s cpu, solution 2)

If that is all you want, stop reading here :-)



Step 2: if you want a more 'constraint'-like behaviour, then this is
a typical case for lib(propia):

?- lib(propia).
Yes (0.07s cpu)

?- band(H1, H2, B) infers ac.
H1 = H1{[300, 500, 600]}
H2 = H2{1 .. 3}
B = B{[5, 7]}
There are 3 delayed goals.
Yes (0.11s cpu)

As you see, propia computes for you the most general domains that
the variables can have in order to satisfy the band/3 predicate.
When you then restrict the bandwith, the H1/H2 variables will be
updated automatically:

?- band(B, H1, H2) infers ac, B #>= 500.
H1 = H1{[1, 2]}
H2 = H2{[5, 7]}
B = B{[500, 600]}
There are 3 delayed goals.
Yes (0.00s cpu)

If you look at the delayed goals, you'll see that the band/3 predicate
has essentially been replaced by several element/3 constraints,
which effectively represent an indexed form of the band/3 predicate.

I don't have time to go into more detail here, but you can find further
information in the Eclipse Tutorial and the Constraint Library Manual.


Cheers,
-- 
   Joachim Schimpf              /             phone: +44 20 7594 8187
   IC-Parc                     /      mailto:J.Schimpf@imperial.ac.uk
   Imperial College London    /    http://www.icparc.ic.ac.uk/eclipse