As Mark said you can avoid the graph issue with tabling. core.logic has tabling. If you look at the tabling section here - https://github.com/clojure/core.logic, you should see something related to your problem.
While defrel/facts are neat - they are really intended for people who don't already have a bunch of data already in memory. If you do then you should probably just write you own goals that can source data from your graph. This can easily be done by returning a Choice from your custom goal. (defn custom-goal [x y z] ... (choice a (fn [] ...)) choice is like a lazy sequence, you have your first value, and then a thunk to produce the remainder of the sequence. You can do whatever you want in the body of the custom-goal to make sure the optimal resultset is operated on. For example, you might have indexed your data on the possible values x, or y, or z. You can check to see if in this call to your custom-goal whether x, y, or z are "ground", that is, they are either not logic variables, or they are logic variables that are bound to values. If they are you can use those values to looked at the indexed version of your data. I plan to document this more. If you examine the defrel/fact architecture you can see exactly how this done. David On Thu, Nov 24, 2011 at 3:49 AM, Tassilo Horn <tass...@member.fsf.org>wrote: > 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 > -- 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
