Mark <markaddle...@gmail.com> writes:
Hi Mark,
> Let's take a specific example: Suppose I have a Person table with id,
> name and gender columns. Then, I have a Parent-Child table that
> contains two id columns, both of which are foreign keys back into the
> Person table. I'd could use the logic system to define a set of rules
> about family relationships. I could express a query in logic terms
> which would then be translated into a series of SQL calls to obtain
> the results (forget any optimization concerns for the moment).
I'm pretty much experimenting in the same direction, but not with
databases but with graphs. Currently, my approach is to translate the
graph's schema (type graph) to a set of relations. For example, if the
schema defines a node type Person, I generate a
(defrel +Person x)
which succeeds if x is a Person vertex.
If the schema defines an edge type Knows between Person, I generate a
relation
(defrel +Knows e a o)
which succeeds if e is a Knows edge starting at a node a and ending at a
node e. (There are also relations for the attributes of nodes and
edges.)
Those relations are then populated with facts about the graph.
Then I can use core.logic to query the graph in terms of a fact base.
For example, here's a query on a graph representing a route map that
finds for any County the City being its capital. (with-fresh is only a
convenience macro that expands into a `fresh' declaring fresh logic vars
for all the ?variables.)
(run* [q]
(with-fresh
(+Locality ?loc)
(+ContainsLocality _ ?county ?loc)
(+HasCapital _ ?county ?capital)
(!= ?capital ?loc)
(+name ?capital ?cname)
(+name ?loc ?lname)
(== q [?cname ?lname])))
Basically, that works pretty well, but there are some issues, which are
probably because I take the wrong approach.
First, it's very memory intensive. I have the graph in memory anyway,
and basically I duplicate it into the relations. That doesn't feel
correct.
Second, with my simply translation approach, when I'd change the graph,
the relations would be out of sync...
Basically, I'd like to be able to define the relations that I have right
now, at least interface-wise. But instead of duplicating the graph in
facts, I'd like to give an own implementation directly on the graph. I
mean, for all these relations I can easily tell when they succeed. For
examle, for (+ContainsLocality e a b), if b is given, I can tell the
valid bindings for e and a in O(degree(b)).
Third, it quickly becomes very slow when I define some recursive
relations like that:
--8<---------------cut here---------------start------------->8---
(defn connected
"Succeeds, if the junctions j1 and j2 are connected by connections (Ways,
Streets, AirRoutes)."
[j1 j2]
(with-fresh
(conde
((+Connection _ j1 j2))
((+Connection _ j2 j1))
((connected j1 ?middle)
(connected ?middle j2)))))
(defn connected-locs
"Succeeds, if the localities l1 and l2 are connected.
Localities are connected, if they contain crossroads that are connected by
connections (Ways, Streets, AirRoutes)."
[l1 l2]
(with-fresh
(conde
((+Airport! l1) (+Airport! l2) (connected l1 l2))
((+ContainsCrossroad _ l1 ?c1)
(connected ?c1 ?c2)
(+ContainsCrossroad _ l2 ?c2)))))
;; What locality is connected with what other locality?
(run 250 [q]
(with-fresh
(+Locality ?l1) (+Locality ?l2)
(!= ?l1 ?l2) (connected-locs ?l1 ?l2)
(== q [?l1 ?l2])))
--8<---------------cut here---------------end--------------->8---
Running that last query takes several minutes on a graph that contains
less than thousand nodes and edges, whereas our usual graphs contain
millions. Even worse, the 250 results are in fact only 3 when removing
duplicates. That's probably because I get a result tuple [A B] for any
possibly street connection between A and B, even if it contains cycles,
etc. Is there something to restrict the search by expressing that any
route between A and B makes no sense if the same node is visited twice?
Bye,
Tassilo
--
(What the world needs (I think) is not
(a Lisp (with fewer parentheses))
but (an English (with more.)))
Brian Hayes, http://tinyurl.com/3y9l2kf
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
