In something like prolog, terms can be nested. So I can express the idea "Socrates believes that he is mortal" with

bel ieves(socrates, mortal(socrates)).

Are there any popular database types that make it easy to have relations of arbitrary arity as parameters of other relations, without unduly adding to the complexity of the schema? Preferably with ungrounded statements and open-world negation? Is there some obvious reason why not? Is there a computational complexity problem that arises in the real world? RDF allows triples to be referenced, I believe, but you are limited to arity 2, which seems needlessly limiting. Labeled graphs have arbitrary arity for non-entities, but entities are limited to two, and you usually can't refer to an edge. It seems... weird to me. Is it just that we don't really have the efficient reasoners over those kinds of expressions, so it hasn't been useful?

Sounds like a "nested hypergraph" (which I have never used before): https://arxiv.org/abs/2405.12235

I've looked at nested hypergraphs before, but atomspace is interesting, thanks!

Can't you do this just with a unique ID/foreign key...? BELIEVES is a relation that takes a tuple as the 2nd parameter. (SOCRATES, IS, MORTAL), 123 (SOCRATES, BELIEVES, 123), 124

RDF* seems to do it that way, putting names on subgraphs and referencing those.

@Chris, I'm not sure how that representation would distinguish between asserting the fact itself, and merely asserting that the fact is believed. Statement 124 should be possible to express even if statement 124 is not known to be true.

Yeah you would have to separately distinguish which statements are TRUE. This would just be a particular relation though? It's no different from which statements are FUNNY or INTERESTING

It is slightly different, because how do you know that 461 is true?

Yeah you're right in that if you want to do some kind of meta level inference there's a special kind of "true" which is USER thinks X is true

yes, but I am not sure it has to look the same as "these are the things the system should believe to be true"

If I have to look to see if the statement exists, and then also check if it is listed as true, that's a lot of needless cognitive overhead for the human user. And as the nesting gets deeper, reading statements is going to get harder and harder.

The reason the relational model forbids this — the reason it is restricted to first order logic — is that this runs into the halting problem. Roughly, once relations can refer to other relations, they can form arbitrarily complex structures where queries never finish. The relational model is, almost mathematically so, the richest model you can have where queries always finish. Note that in the above suggestions where you refer to other relations by a code, you have to go into your external, Turing-complete language to use this. Not a reason a database should not have this feature, of course, but this might be a useful nuance to be aware of.

That helps explain it, thanks.

Every programming language runs into the halting problem, and yet, we don't care. Why do we care for a knowledge language?

SQL has poisoned the entire industry. So you’re used to thinking of a relational database as this heavyweight, fixed sort of thing with a terrible query language. The correct way to understand the relational model is that it lets you separate your first order logic (FOL) computation from the stuff that should be (either logically or pragmatically) done in a Turing complete language. The vast majority of the logic in just about any program can be written in FOL. Folks don’t even think about doing that because SQL is terrible. One of the great features of the relational model is that precisely because of its limits, optimisation is a relatively simple problem. We should be able to use relations freely across all of our programming tasks. The result would be that you can just declaratively specify what comes from what, and the query optimiser will make it work efficiently. These considerations still apply to SQL databases. If you execute a query, it will eventually finish and when it does, you’re guaranteed that if some data satisfies your query, it will be retrieved.

I have difficulty gauging how practical a virtue the guarantee of termination really is. I can end up with non-terminating code elsewhere, and I just fix it. Is the benefit perhaps that someone cannot add data that makes a query stop terminating that used to terminate? Because not a lot of people are letting users run arbitrary untested queries against their data. So it feels like you would know in advance it will terminate unless the data can stop that from happening, maybe?

The relational model is, basically, “essence of declarative programming”. 2nd order logic, subject to halting problems, currently mostly needs to be written by humans. But the rest of it can be declarative — most of most programs, in fact. The part you can express in FOL benefits from this essence of declarative stuff insofar as you can just declare the rules of what facts follow from what other facts, and then the computer writes an efficient algorithm to implement the logic for you. The relational model provides a theory for generating code from declarations about what is true and what follows from what.

Don't get me wrong. I'm sold on declarative logic code. Love it, terminating issues and all. Big fan. I just am not sold on the FOL limitation, and I'm having difficulty believing that anyone without a comp sci degree really cares about guaranteed termination that much, unless it is guaranteed against changes in the data.

But that right there is one reason for the design. If you have a language in which someone can’t express a non-terminating query, they don’t have to understand any of that, but they know they have a completely reliable system that always answers their questions.

Regardless of the data, or just regardless of the query?

I’m curious too. If every query has a 60-second deadline, valid FOL and SOL queries will both sometimes fail. How much does it matter why? Are the performance problems harder to diagnose and fix with the more complicated languages? Are they more common?

Aha! You discovered the weakness in my cunning ruse! Not really. You can certainly write SQL queries that will time out. But in practice, those are rare, and if you had to solve the same problem in a Turing-complete language, there’s a good chance you have no other way to fix it. Computation complexity is always with us, either way. And in practice, there might be some things that are easier to write in a TC language. But I’d have to struggle with some quite unusual sort of data for a while to produce an example. So: a relational database can represent most of most programs more cleanly and simply than any mainstream TC language can, and it does a lot of the programming for you, particularly in terms of working out what order it should process each part of your logic in. And, because it can do that dynamically and automatically, it can retain efficiencies even as you change the model, whereas the typical TC solution might need substantial re-engineering to retain efficiency.

The fact that all queries terminate isn't the actual benefit. As a result of that fact, the user can alter the data arbitrarily, and there is no possibility that by doing so they cause queries to become non-terminating. That's the actual upside. The user can't break it. If you are using a higher-order system, you have to either a) be careful not to use potentially infinite structures in your queries (in which case why not just use FPL), or b) guard against the user adding data that causes infinite loops. For my use case, b) was already taken care of in the context of the limited queries I have. Thanks for the enlightening chat!

You certainly need TC behaviour to be available. But separating what you can into the relational model has enormous benefits in terms of simplicity and flexibility.