7 ms·

Isn't this just promoting the concept of a well written wiki? Linking documents together IS a graph, whether you store it in a graph db or not. Graph DBs shine

by dchuk 11y ago

Isn't this just promoting the concept of a well written wiki? Linking documents together IS a graph, whether you store it in a graph db or not. Graph DBs shine when it comes to graph queries, storing documents that are well linked can be handled with any old relational DB

jsprogrammer 11y ago
Every computation and/or representation is isomorphic to some (hypothetical) graph.
- catnaroek 11y ago
  Could you clarify: What are the nodes and edges? May the graph contain cycles? May the graph be infinite? If the graph is infinite, do we need a distinguished initial node? Do non-isomorphic graphs always correspond to different computations, or do you have a coarser notion of equivalence (say, graph homeomorphism)? I've read papers where the space of possible computations for a given (typically, toy, even loop-free) nondeterministic concurrent program is represented as a directed topological space (see “directed algebraic topology” for more information), but these spaces are more general than directed graphs.
  - andrewflnr 11y ago
    The point isn't necessarily one graph representation, but simply that any problem can be looked at in a graphy manner if you try hard enough, so "hey, it's a graph" isn't an interesting insight. But to answer your question, data flow graphs are a general representation of function composition, and Turing machines can be looked at as graphs with labeled edges. Yes, we're using "isomorphism" in the pop-compsci, Gödel-Escher-Bach sense.
  - jsprogrammer 11y ago
    I don't mean directed graphs, only vertices and edges. I don't think you would need to deal with infinite graphs, as "arbitrarily large" should be able to cover all (finite) possible computations and/or representations. My guess is that every graph may correspond to an infinite number (though, not necessarily every) of possible computations and/or representations, depending on which "correspondence function" is being used to analyze the graph (though there may be additional "correspondences" between those functions and/or their results).
    - catnaroek 11y ago
      At the very least, answer this: What are the nodes and edges in your graph? What information is associated to them?
      - jsprogrammer 11y ago
        We'd need to be talking about a concrete example to say with much specificity, but a node is basically a "thing" and an edge is a binary relationship between two things. A thing may have relationships with itself. The precise "information" associated to them could be "anything", but would be proscribed by the computation and/or representation being disccussed and the graph in question.
        catnaroek 11y ago
        How disappointing. I was expecting something more concrete, like “every node is a sequence point and every edge is a possible transition” or “every node is a point at which a nondeterministic event occurs and every edge corresponds to a causal relation between events”. But if you just say “a computation is a graph” and give no further details, then there's no actual benefit to modeling computations as graphs. I'm even more annoyed by your use of the word “isomorphic”, which, FYI, doesn't mean “vaguely similar in some way I can't articulate”. It only makes sense two speak of two mathematical objects being “isomorphic” when they belong in the same category. What category do you have in mind, that includes both computations and graphs as objects, and what are the morphisms between them?
        jsprogrammer 11y ago
        Disappointing? You are the one coming to me expecting an example-oracle that produces them on demand. E.g. Computation / representation: 2 + 2 Graph [+] / \ [2] [2] There is a way to produce the graph from the computation / representation and vice versa. There is a way to do that for every possible computation / representation and every possible graph (though, not necessarily with every pair). This could be described as a compiler or compiler-like. There are many interesting things to do with them, but in this example all that is needed to consider is the construction of an Abstract Syntax Tree from a string and an in-order tree walker that emits the contents of the nodes to an output string.
brudgers 11y ago
One advantage of a graph database implementation over a traditional wiki implementation is in regard to querying along edges as opposed to following links. Which is to say that the edges of a graph database will tend to have richer semantics than a wiki's generic hyperlinks [but it is not to say that a graph database is necessarily better]. To put it another way, at best a link from a wiki page gets implied importance based on it's position within a document. A graph database edge can have many properties including "weight" or "relevance". Of course these could be added to wiki markup as properties, but there is a point at which the right tool is better than layered make-do's.
- Someone 11y ago
  I don't see it is that different. A wiki page typically assigns human-readable properties through its text. You don't write <a href="foo.html">Read more</a> <a href="bar.html">Read more</a> but: <a href="foo.html">Example code</a> <a href="bar.html">Grammar</a> If desired, one can even make this easier to parse programmatically: <a href="foo.html" class="ExampleCode">Hello world example</a> <a href="bar.html" class="GrammarNotes">Grammar</a> That allows for styling different types of links differently. Also, a wiki's backend software could extract separate indexes for sample code, grammar fragments, links to compiler source, etc. you could also easily include an attribute for, e.g. Click-through rate, and, if desired, style links accordingly. In fact, the difference between a classical wiki and a graph database is, IMO, an implementation choice. If you want to process complex queries rapidly or a lot of your attributes aren't textual or aren't intended primarily for visual display, a graph database is more appropriate. If you want to serve standard web pages rapidly, storing the content as HTML may be more appropriate, even if that means that processing queries such as "give me all links to source code examples" run way more slowly.

by dchuk 11y ago

jsprogrammer 11y ago

Every computation and/or representation is isomorphic to some (hypothetical) graph.

catnaroek 11y ago
Could you clarify: What are the nodes and edges? May the graph contain cycles? May the graph be infinite? If the graph is infinite, do we need a distinguished initial node? Do non-isomorphic graphs always correspond to different computations, or do you have a coarser notion of equivalence (say, graph homeomorphism)? I've read papers where the space of possible computations for a given (typically, toy, even loop-free) nondeterministic concurrent program is represented as a directed topological space (see “directed algebraic topology” for more information), but these spaces are more general than directed graphs.
- andrewflnr 11y ago
  The point isn't necessarily one graph representation, but simply that any problem can be looked at in a graphy manner if you try hard enough, so "hey, it's a graph" isn't an interesting insight. But to answer your question, data flow graphs are a general representation of function composition, and Turing machines can be looked at as graphs with labeled edges. Yes, we're using "isomorphism" in the pop-compsci, Gödel-Escher-Bach sense.
- jsprogrammer 11y ago
  I don't mean directed graphs, only vertices and edges. I don't think you would need to deal with infinite graphs, as "arbitrarily large" should be able to cover all (finite) possible computations and/or representations. My guess is that every graph may correspond to an infinite number (though, not necessarily every) of possible computations and/or representations, depending on which "correspondence function" is being used to analyze the graph (though there may be additional "correspondences" between those functions and/or their results).
  - catnaroek 11y ago
    At the very least, answer this: What are the nodes and edges in your graph? What information is associated to them?
    - jsprogrammer 11y ago
      We'd need to be talking about a concrete example to say with much specificity, but a node is basically a "thing" and an edge is a binary relationship between two things. A thing may have relationships with itself. The precise "information" associated to them could be "anything", but would be proscribed by the computation and/or representation being disccussed and the graph in question.
      - catnaroek 11y ago
        How disappointing. I was expecting something more concrete, like “every node is a sequence point and every edge is a possible transition” or “every node is a point at which a nondeterministic event occurs and every edge corresponds to a causal relation between events”. But if you just say “a computation is a graph” and give no further details, then there's no actual benefit to modeling computations as graphs. I'm even more annoyed by your use of the word “isomorphic”, which, FYI, doesn't mean “vaguely similar in some way I can't articulate”. It only makes sense two speak of two mathematical objects being “isomorphic” when they belong in the same category. What category do you have in mind, that includes both computations and graphs as objects, and what are the morphisms between them?
        jsprogrammer 11y ago
        Disappointing? You are the one coming to me expecting an example-oracle that produces them on demand. E.g. Computation / representation: 2 + 2 Graph [+] / \ [2] [2] There is a way to produce the graph from the computation / representation and vice versa. There is a way to do that for every possible computation / representation and every possible graph (though, not necessarily with every pair). This could be described as a compiler or compiler-like. There are many interesting things to do with them, but in this example all that is needed to consider is the construction of an Abstract Syntax Tree from a string and an in-order tree walker that emits the contents of the nodes to an output string.

brudgers 11y ago

One advantage of a graph database implementation over a traditional wiki implementation is in regard to querying along edges as opposed to following links. Which is to say that the edges of a graph database will tend to have richer semantics than a wiki's generic hyperlinks [but it is not to say that a graph database is necessarily better]. To put it another way, at best a link from a wiki page gets implied importance based on it's position within a document. A graph database edge can have many properties including "weight" or "relevance". Of course these could be added to wiki markup as properties, but there is a point at which the right tool is better than layered make-do's.

Someone 11y ago
I don't see it is that different. A wiki page typically assigns human-readable properties through its text. You don't write <a href="foo.html">Read more</a> <a href="bar.html">Read more</a> but: <a href="foo.html">Example code</a> <a href="bar.html">Grammar</a> If desired, one can even make this easier to parse programmatically: <a href="foo.html" class="ExampleCode">Hello world example</a> <a href="bar.html" class="GrammarNotes">Grammar</a> That allows for styling different types of links differently. Also, a wiki's backend software could extract separate indexes for sample code, grammar fragments, links to compiler source, etc. you could also easily include an attribute for, e.g. Click-through rate, and, if desired, style links accordingly. In fact, the difference between a classical wiki and a graph database is, IMO, an implementation choice. If you want to process complex queries rapidly or a lot of your attributes aren't textual or aren't intended primarily for visual display, a graph database is more appropriate. If you want to serve standard web pages rapidly, storing the content as HTML may be more appropriate, even if that means that processing queries such as "give me all links to source code examples" run way more slowly.