Ternary Relations

Technical Development Development Systems
1

After taking a break for a couple of years, I’m back to working on a JavaScript API for interactive fiction. For the story world I’m currently planning on implementing semantic triples in a fully indexed triple store. Each triple is a tuple of [predicate, noun1, noun2], for example [“contains”, “bar”, “locket”] The project will include a simple DSL for writing and selecting facts to and from the knowledge base in a somewhat English-like way:

ishml.reify`${{id:"bar",description:"a dank and dusty den",name:"Dimby's Bar"}} (north) exits_to ${{id:"foyer",description:"a cheerful and welcoming place"}} (south)`
ishml.reify`${{id:"locket",description:"a beautiful locket"}} is thing. Bar contains locket.`
ishml.select`__ contains locket.`  //Returns all facts where noun1 contains locket.
ishml.check`bar contains locket` //Return true if at least one fact matches the pattern.

Anyhow, I’m wondering about extending this idea to ternary relations, [predicate, noun1, noun2, noun3] . I believe Inform does not have this capability and I’m worried that it doesn’t for very good reasons that I don’t understand. So, what’s bad/dangerous about ternary relations? ["gave", "john", "ring", "jane"] //john gave mary ring

2

I believe the experience has been that ternary relations just aren’t terribly useful compared to the complexity they introduce.

FWIW, “john gives mary the ring” is possible in Inform, by specifying the actor as John:

try John giving mary the ring.

What isn’t possible is:

THROW THE ROCK AT JOHN WITH THE SLINGSHOT

1 Like
3

If you want to see some prior art, Dialog has arbitrary n-ary predicates, although I’m not sure how heavily the standard library uses them.

1 Like
4

The trick with ternary relations is that they can consume a horrible amount of storage space (and take a long time to query and update). But Inform actually does support them—just, only in special hard-coded cases. “ROOM1 is mapped DIR of ROOM2” is actually implemented as a separate relation for each direction, which relates rooms to rooms.

Dialog has arbitrary N-place predicates (I think the limit is 12?) but they aren’t dynamic—they have to be specified at compile-time. Dynamic predicates in Dialog can only have two places, and are implemented so inefficiently that using more than one or two of them can destroy your game. It’s the biggest drawback compared to Inform, with its wide variety of relations.

2 Likes
5

I didn’t realize that Dialog supports n-ary predicates. I should take another stab at the docs. I never get very far. I have a hard time relating the syntax to the underlying data model for some reason. I really need a “explain like I’m five” tutorial on Dialog.

1 Like
6

Remember that Inform does not implement actions with relations. It’s true that Inform doesn’t support ternary actions (PUT ICE IN BLENDER WITH TONGS), and it doesn’t support ternary relations, but these are separate unrelated limitations. :)

That’s true. You can come up with efficient implementations for some cases. But you have to know in advance what the relation will look like and how you intend to query it.

(The map can have at most one room north of the Kitchen. You need to look that up efficiently. But you don’t need an efficient way to ask “what rooms can you reach the Round Room by going north from?” or “What directions from the Study lead to the Closet?”)

Unfortunately, Inform’s “one-to-many, one-to-one, many-to-one” taxonomy isn’t sufficient for ternary relations. (I’m not sure it’s sufficient for binary relations!) You need to get down and dirty about what’s indexable, and the whole thing starts to look like a database query planner rather than a mathematical relation or predicate.

3 Likes
7

Semantic n-tuples is what i do in Strand. Mostly triples, but also pairs and some are singletons. As yet i have not had need for more than 3 terms, but it could easily be handled.

instead of contains bag key i will have key in bag so then i also have key foo and even just key.

In a previous system, i used triples with indices so that “X Y ?” can be queried along with “? Y Z” and “X ? Z”. I called these forward, backward and sideways.

This worked but got complicated, especially with iterators and threads.

Now I don’t have any indices at all, which also helps the n-ary situation. I found it is still plenty fast enough.

1 Like
8

Yeah, that’s the way I’m approaching it right now. Also, thinking about allowing a whole triple to be treated like a noun for something I’m calling compound facts and maybe they’re a way to simulate ternary relations. Something like [“to”,[“gave”,“john”,“ring” ],“mary”]. (Not that I’d store it nested like that in the knowledge base, but you get the idea.)

9

Originally i had the same idea which i called “clusters”. The idea was a cluster is a compound of other clusters. This followed the lines of conceptual graphs and conceptual structures.

However, it didn’t work.

This is not surprising in retrospect because there has been no progress in this theoretical area for decades. For example Semantic Web did not get anywhere useful.

Most systems get as far as the semantic triple/RDF and then stop.

I worked on this area for about 5 years and eventually came up with a completely new approach based on a novel data structure and a set of operators on that structure. These operators manipulate the data structure in a way that allows it to grow organically. It is important to understand that organic style growth can happen anywhere in a knowledge structure.

I wanted to use this for world modeling in games. But in the end i discovered that an over-rich world model is not useful for making entertainment and as a result i regressed to simple n-tuples for my base implementation.

Nevertheless the novel work (and code) is still there and i would like to find an outlet to publish it some day.

3 Likes
10

Interested to hear more about this. Don’t want to go down a broken path.

1 Like
11

TADS supports 3-object verbs as well, but they are somewhat discouraged as complicating the player’s life (unless there are clear expectations outlined in the game instructions); at least, I wouldn’t make any puzzle solution require a 3-object construct.

1 Like
12

This is what goes wrong with nested n-tuples:

Let’s say you have a “fact” A B C. Call this F1. Then you replace “A” by a compound, say D E F and call this F2;

So F1 = A B C and F2 = (D E F) B C

F2 is not strictly a specialization of F1 but rather what i call an “elaboration” of F1. ie where you add more information to an exiting fact.

I have a formal definition of elaborations which is essential to knowledge representation. I don’t have my notes here (currently in Kyoto), but could post later.

Anyway, the problem with the above form of using nested tuples is;

any truth query on F1 should return the same for F2.

So asking is ? X Y applied to F1 == A returns true.
and asking ? X Y applied to F2 == A returns false.

If you have enriched a fact from F1 to F2, then F2 should work as a drop-in replacement for F1 for any query that can apply to F1.

If you don’t have this then you don’t have a scalable knowledge base.

The approach i took with elaborations is a more organic growth structure where any term can be elaborated rather like the buds of a plant growing. Of course there is also a mathematical definition.

I needed:

  1. a definition (and code) for elaborations.
  2. a new data structure
  3. a new programming language to apply to this structure.
  4. a set of operator terms that apply to the data structures that essentially perform set and get.
1 Like