Constructing a linked list

Users GraphQL
1

Hey,

I’m checking dgraph out for a personal project before pitching it at work, but I am getting my butt kicked when trying to implement a (singly) linked-list, or any ordered list for that matter.

I’m trying to build a fifo queue using the following schema (simplified):

succ: uid .
head: uid .
tail: uid . 
name: string . 

type Link {
    succ: Link
    name
}

type List {
  head: Link
  tail: Link
}

My main idea is that I need to store the last created link in the tail attribute and when a new Link needs to be created, set the succ of the new Link to the old tail and then override the tail. This seems to work somewhat, but my main issue is with ensuring I have a head. When the list is empty (no head, no tail) and I am adding the first Link, I can set both the head and tail. But how do I ensure that I do not override the head when the next Link needs to be added?

Can you please point me in the right direction of how to create a (fifo) queue using dgraph, or help me figure out how to make my approach succesful.

2

You can to control the mutation depending on the size of the list using variables.
It can be achieved in the following way.
Get the list(Assume ListID is 0x0123)

query {
	getList(id: "0x123") {
		head
		tail
	}
}

After getting the head and tail pointer you can decide if the list is empty.
Empty condition: head = null and tail = null

mutation updateList($patch: UpdateListInput!) {
	updateList(input: $patch) {
		list {
			listID
			head
			tail
		}
	}
}

When the list is empty, $patch

{
	"patch": {
		"filter": {
			"listID": ["0x123"]
		},
		"set": {
			"head": "0x01",
			"tail": "0x01"
		}
	}
}

Update the tail after adding to the List.

{
	"patch": {
		"filter": {
			"listID": ["0x123"]
		},
		"set": {
			"tail": "0x02"
		}
	}
}

Update the head after deletion from the List.

{
	"patch": {
		"filter": {
			"listID": ["0x123"]
		},
		"set": {
			"head": "0x02"
		}
	}
}
3

Thanks for the quick reply!

So basically split it in two queries and determine whether to update the head when it is empty in a single transaction.

Since my google-fu might be lacking, is there a reason why there is no “inverted has” function, or a coalesce function?

4

I am not sure what “inverted has” or “coalesce” are. Can you explain? I found SQL documentation about coalesce but Dgraph is not a SQL database so I am not sure if the same concept applies.

But what Arjit said is correct, query the list and decide based on the result if your application should update both the head and tail or just the tail.

5

There exists a has function to check whether a predicate exists right? So an inverted has would be where you can ask whether a predicate does not exist.

A coalesce in this case would mean (for me) that within a mutation you can set a predicate only if it does not exist (yet). If it would exist, the old value would not be overwritten.

I now know you can do this by doing two queries in a transaction, but in many cases retrieving the data before updating can be quite a waste. For instance: suppose after some time it is desired to add a predicate to some type. The application itself is modified so that it now sets that value, but all old data still needs to be migrated. Some values already have that predicate, while others do not. It would be nice to be able and write a single mutation that sets that value only if it is not set yet, so you do not overwrite the already set values.