Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: PROLOG ENGINES ARE REALLLLLLY SLOW! ((SQL-UNIFY))
Replies: 5   Last Post: Nov 20, 2012 4:40 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Graham Cooper

Posts: 4,348
Registered: 5/20/10
PROLOG ENGINES ARE REALLLLLLY SLOW! ((SQL-UNIFY))
Posted: Nov 20, 2012 3:59 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

It's a simple algorithm to program,
a simple problem to solve!

f(a,X) <=> f(Q,g) ?

Can these two TREES? be made equivalent?

f(a,g) !!

Haha!

X=g
Q=a

------------

But examine a BIGGER NESTED ATOMIC PREDICATE!

f(A,b(c,d), e(F,g(H,I,j(K,l),m,N),o,p(A,d,F)))).

AND

f(z, Q , e(l(m,n), g(h,i,J,m,w),o,P)).

I'll tell you I've been programming exactly this for 5 months!

It is a debuggers dream if you like bugs!

ALL THE UNIFY(F1,F2) ALGORITHMS ARE RECURSIVE!

1st you unify f(.....) to f(.....)
then 1 argument at a time....
A to z
b(c,d) to Q
....

then some of those terms are predicates that have to be unified
FURTHER!


A lot of variable renaming conventions, trial and error,
backtracking... very tricky and particular code covering dozens of
potential matching scenerios!

----------------

OK here is how it SHOULD BE DONE!

Each term in the predicate is given a REFERENCE NUMBER!

f(A,b(c,d), e(F,g(H,I,j(K,l),m,N),o,p(A,d,F)))).

OK, see that g(H,I).

that 'I" might be ANYTHING, it's a capital VARIABLE.

But it's reference number is:

REF 333

1 2 3
f A e

1 2 3
e F g

1 2 3
g H I

I is at position 333!

------------------

Now all facts, rules and Queries fit into a simple SQL TABLE!

A PROLOG FACT

vert ( pnt( X,Y ) pnt( X,Z ) )


TPRO
ID REF FIELD TYP
=================
21 1 vert H
21 2 pnt P
21 3 pnt P
21 21 X V
21 22 Y V
21 31 X V
21 32 Z V



A PROLOG QUERY

?- vert ( pnt( 1,2 ) pnt( 1,4 ) )

TTAILS
ID REF FIELD TYP
=================
1 1 vert H
1 2 pnt P
1 3 pnt P
1 21 1 T
1 22 2 T
1 31 1 T
1 32 4 T


THIS 1 LINE OF SQL WILL DO 100 LINES OF UNIFY RECURSION!

The ORDER IN WHICH YOU WORK OUT THE TERMS is IRRELEVANT!
No need to do a recursive descent match by match!

SQL-UNIFY

SELECT * FROM TTAILS, TPRO
WHERE TTAILS.REF = TPRO.REF
AND TTAILS.FIELD = TPRO.FIELD
GROUP BY COUNT(ID)
ORDER BY ID DESC

This will put all the MAXIMUM TERMS MATCHED RESULTS
at the top of the Query Result, and UNIFY just has to allocate
variables to terms, then recurse the tail facts of any matched rules.

Slight drawback is program order is lost using the fastest match
method, but PROLOG is overused as a simple FETCH cycle for 3GL style
coding.


Herc


--
www.microPROLOG.com
if( if(t(S),f(R)) , if(t(R),f(S)) ).
if it's sunny then it's not raining
ergo
if it's raining then it's not sunny























Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.