News for hackers. Stuff that matters.
Re:Make the “semantic web” web 3.0 again – with the help of ... by Groxx on Wednesday January 12, 2022 @01:29AM (#29903070)
What is a graph database? A miserable little pile of joins.

Though to be serious: what do you expect a graph database to provide that sqlite cannot / does not do efficiently?

Re:Make the “semantic web” web 3.0 again – with the help of ... by wheels on Wednesday January 12, 2022 @03:18AM (#29903748)
You can reasonably model graphs in a column-oriented database, but traditional SQL models tend to be horrible performance-wise, because most graph algorithms need fast traversal of edges, and doing a lot of recursive lookups in SQL is impractically slow. It's not that you can't model it, it's just that performance is terrible. For a graph database to be efficient, you need a high degree of locality for edge information (ideally a vector you can simply read out).

(Note: I've actually written a graph database from scratch, for exactly these reasons.)

Re:Make the “semantic web” web 3.0 again – with the help of ... by simonw on Wednesday January 12, 2022 @10:27AM (#29907649)
SQLite may be uniquely well suited to building graph databases out if all of the relational engines, thanks to this: https://www.sqlite.org/np1queryprob.html
Re:Make the “semantic web” web 3.0 again – with the help of ... by wheels on Wednesday January 12, 2022 @11:08AM (#29908407)
s/uniquely well suited/somewhat less bad/

Fixed that for you. ;-)

Actually a few RDMBSes (Oracle, Postgres, MS SQL) have graph extensions. I've never used any of them, but I assume they work around some of the basic unsuitability of traditional tables for storing graphs.

Re:Make the “semantic web” web 3.0 again – with the help of ... by ahevia on Saturday January 15, 2022 @11:55AM (#29947930)
Do you have examples of Graph DBs that could embedded in a static site as easily as SQLite?
Re:Make the “semantic web” web 3.0 again – with the help of ... by oever on Wednesday January 12, 2022 @04:09AM (#29904044)
Modelling transitive edges can be done in Sqlite with recursive common table expressions. The performance for that is probably less than for graphs databases, but Sqlite has many other advantages over graph databases.
Re:Make the “semantic web” web 3.0 again – with the help of ... by wheels on Wednesday January 12, 2022 @04:28AM (#29904172)
Uhm, that's basically what I said? Aside from the "other advantages" -- which, yeah, sure. Socket sets have other advantages than hammers, but they're not very good at pounding in nails. You can do it, but it'll suck at it.

Also, in this case, "probably less" is "multiple orders of magnitude slower".

Re:Make the “semantic web” web 3.0 again – with the help of ... by oever on Wednesday January 12, 2022 @05:12AM (#29904452)
The locality that you want for performance is available as row values in sqlite. Sqlite seems to have the parts needed to build a graph db.
Re:Make the “semantic web” web 3.0 again – with the help of ... by WJW on Wednesday January 12, 2022 @05:39AM (#29904637)
Why do you keep making the same argument again? Yes, SQLite has the parts needed to build a (very poor) graph db. But it will never be as performant as something dedicated, because the data structures used in SQLite have terrible characteristics for the algorithms used in graph operations. I like SQLite a lot, but it targets a niche and graph operations is simply not that niche.
Re:Make the “semantic web” web 3.0 again – with the help of ... by oever on Wednesday January 12, 2022 @05:58AM (#29904744)
Using Sqlite for semantic web is the topic of the post. And while Sqlite is not suited for billions of triples, it can be adequate for the small graphs. The advantage is that Sqlite is widely deployed.
Re:Make the “semantic web” web 3.0 again – with the help of ... by wheels on Wednesday January 12, 2022 @06:26AM (#29904942)
You're not understanding what I mean by locality in this context. I mean that the on-disk structure should approximate an array of indexes, e.g.:

  const unsigned *edge_indexes = (const unsigned *) mmaped_structure_on_disk[disk_offsets[index]];
That's not the same as just being able to access those via an API; locality in this case means that you shouldn't need extra seeks for every single value, nor have to make a bunch of round trips through SQL.

That is the primary difference between traditional relational databases and column-oriented databases. Normal relational databases have row-based locality; column-oriented databases have column-based locality.

Re:Make the “semantic web” web 3.0 again – with the help of ... by fauigerzigerk on Wednesday January 12, 2022 @07:48AM (#29905608)
If your typical query visits all adjacent edges of a few nodes then the locality you're talking about is great. If your queries typically aggregate over a few types of edges across many nodes then this locality is the worst case.

So the question is, do we actually want to run graph algorithms or is the data graph structured for other reasons? You're implying that choosing a graph representation means we want to perform graph analyses. I disagree with that if we're still talking about the semantic web.

RDF is a general purpose knowledge representation model. The triple structure lends itself well to combining data from different sources with little coordination. It happens to form a graph, but running graph algorithms is just one of many special purpose problems.

Re:Make the “semantic web” web 3.0 again – with the help of ... by wheels on Wednesday January 12, 2022 @07:56AM (#29905706)
Yes, you're mostly correct. (The one caveat being that if you know your access patterns in advance, you can choose if you store the edge type along with the edge, or if you store separate edge types in separate columns.) I'm not even arguing against storing RDF in SQLite. There are times that would make sense, and times that it wouldn't.

I'm primarily replying to:

> What is a graph database? A miserable little pile of joins.

> Though to be serious: what do you expect a graph database to provide that sqlite cannot / does not do efficiently?

That seemed like a general questions of, "What are graph databases for, and why would someone use them?" And I'm trying to answer that question.

Re:Make the “semantic web” web 3.0 again – with the help of ... by Groxx on Wednesday January 12, 2022 @01:08PM (#29910611)
It was intended as both a "what significant benefits would it bring for this problem" (for implied exposed DBs with relatively small datasets... though "relatively" is relative of course), and "I don't see how using SQLite would somehow prevent this from happening".

If there was some kind of "normal" query on thousands-to-millions of items that was prohibitively terrible on SQLite but not on graph-database-X, yea - I'm interested :) And I totally buy that graph DBs are better at graph queries in general. I just have yet to hit these kinds of limits in my use of SQLite (a fair number of instances with tens of gigabytes, a few with billions of rows) - a sprinkling of reasonable database design addresses almost all issues.

The main one I can see is that, with longer-term use, SQLite's lack of any way to force locality would be fairly crippling. You'd need to make a reasonable sort order and periodically re-insert data in that order to optimize / vacuum. That's... technically achievable, but is a big downside compared to something that can dynamically organize / optimize it based on [some heuristic].

Re:Make the “semantic web” web 3.0 again – with the help of ... by oever on Wednesday January 12, 2022 @07:05AM (#29905231)
Sqlite does indeed not have an array type for columns. The overhead of (de)serializing binary values or json values would have to be offset against the advantage of cache coherence. Or one could implement a virtual table that stores arrays in integers.
Re:Make the “semantic web” web 3.0 again – with the help of ... by j-pb on Wednesday January 12, 2022 @05:39AM (#29904634)
A whole pile of joins, that naturally arises if you want to combine data from a ton of domains.

Triple stores are essentially relational databases in 6th normal form. But relational databases like SQLite don't have good join algorithms to deal with this (they do pairwise joins instead of the worst case optimal ones like Leapfrog-Triejoin or Tetris). They also lack good interfaces for so many joins, you want something more declarative like Datalog/SparQL/GraphQL, than to explicitly write out every join.

Re:Make the “semantic web” web 3.0 again – with the help of ... by patates on Wednesday January 12, 2022 @01:39AM (#29903126)
Treating links as an entity. In a RDBMS, it is not possible to map a bidirectional relation semantically. It needs to have a direction (you can define it in both directions but then you have 2 relations). You then also need to duplicate link properties (in the join table) or normalize to yet another join table.

That has been my pet peeve for a while, and can make it hard to define navigation.

Totally not a deal-breaker though. I'd still use sqlite because I ### love it :)

Re:Make the “semantic web” web 3.0 again – with the help of ... by Groxx on Wednesday January 12, 2022 @02:06AM (#29903274)
why would a direction be necessary?

    relation_id │ relatee_id
    ────────────┼───────────
              1 │ x
              1 │ y
voila, directionless relationships. you can even do N-way, just insert more rows with the same relation-id.
Re:Make the “semantic web” web 3.0 again – with the help of ... by patates on Wednesday January 12, 2022 @02:20AM (#29903368)
To quote myself:

> or normalize to yet another join table

This is also semantically incorrect. There needs to be exactly 2 rows there. You cannot in a declarative way, prevent that if you use this approach.

It's also a known dilemma, so we don't have to rediscover the wheel here.

Re:Make the “semantic web” web 3.0 again – with the help of ... by Groxx on Wednesday January 12, 2022 @04:20AM (#29904110)
Custom indexes or insert triggers can both guarantee that, both in a declarative way (in that they prevent normal "blind" inserts. I'm not entirely sure what you mean by declarative here tbh).

Also I have no idea why a separate table is a negative / constraint of some kind. It's a natural way to model it.

Re:Make the “semantic web” web 3.0 again – with the help of ... by patates on Wednesday January 12, 2022 @05:21AM (#29904521)
> no idea why a separate table is a negative

When you are following a chain of relations (a vector), you end up losing a lot of performance.

> not entirely sure what you mean by declarative

Guaranteed by the database semantics, not imperative code even when it runs on the DB.

I don't want to come off sounding like I think it's a bad idea to map graphs on RDBMSs, it's just inconvenient sometimes. Usually not enough to complicate your setup, adding another database, but rarely it is.

I'm not sure though about the suggested use case here, I really don't know it enough to make a suggestion. In such cases I always pick sqlite or postgres (depending on the client model) though. You can't be too wrong with those, and you are most of the times right :)

Not to mention the crazy extensibility of pg and the stuff you can do with it.

Re:Make the “semantic web” web 3.0 again – with the help of ... by Groxx on Wednesday January 12, 2022 @01:41PM (#29911094)
Imperative code run on the DB (i.e. triggers) seems entirely in-scope. It's an incredibly powerful tool provided natively by the DB, intended to be used for exactly this kind of custom constraint. Whether it's begin/end with imperative code or modeled some other way declarative seems absolutely, 100% irrelevant to me - it's the perfect implementation detail, it could have been done with `create unique index max 2 (x, y) on mytable` and you'd never know.

If you meant to prevent "all inserts are now [run this stored procedure / multi-statement operation / transaction with N steps]", then yeah - I agree that runs counter to "normal" use in most cases. It's certainly dramatically more error prone. Triggers don't need this though.

re chain of relations: I haven't poked too hard in this direction in SQLite, but I do totally believe its query planner isn't too sophisticated. And though you can get pretty good data locality with fancy design around the DB, you certainly won't get good locality just by inserting a bunch of data and running queries.

Re:Make the “semantic web” web 3.0 again – with the help of ... by harperlee on Wednesday January 12, 2022 @06:26AM (#29904937)
A directionless link or relation does not require exactly 2 rows here, that’s overconstraining the definition.

A simple example would be to link 3 brothers with the same relation: the worse solution would be dividing it in 3 different binary relations; the reality is that each brother is part of the “brother relation” set by way of sharing parents.

Re:Make the “semantic web” web 3.0 again – with the help of ... by galaxyLogic on Wednesday January 12, 2022 @07:23PM (#29914980)
Brothers yes. But what about children? child_of is a directional relation, right?

Semantic web I assume is full of such directional relations. Bidirecitonal relations are the exception. Things like "causes", "indicates", "enables", "prevents", ...

Re:Make the “semantic web” web 3.0 again – with the help of ... by noctune on Wednesday January 12, 2022 @03:02AM (#29903648)
What if you have something like (relatee_a_id, relatee_b_id, [rest of relation fields ...]) with the constraint that relatee_a_id < relatee_b_id?

Granted, it might not be very nice to query.

Re:Make the “semantic web” web 3.0 again – with the help of ... by patates on Wednesday January 12, 2022 @03:45AM (#29903890)
Well, that is what I actually use most of the time, but to nitpick, it still is not declarative, and semantically a and b have no meaning. Just to be clear, I'm saying these are in 99% of the cases not deal breakers but they can be if all you want to do is map graphs (and follow chains through many members), as there is also a significant performance cost to all this abstraction.

What you described is, IIRC, also what some file-based graph DBs do in the background with sqlite and abstract away from you (I've seen a couple custom ones in some projects). Left with a RDBMS, you just need to do it yourself and analyze how much it costs.