Extract Entity

[michielbdejong]

How would we solve the Extract Entity challenge described in section 2 of https://arxiv.org/pdf/2309.11406 ?

[michielbdejong]

I think it's easy to allow switching back and forth between the one-table and the two-table serialisation of this dataset, if we make a few assumptions:

• if we have two customers who both have name "Wile E Coyote" and address "123 Desert Station", then we can safely merge them into one
• if we have two customers who both have name "Wile E Coyote" but their addresses are, say, "123 Desert Station" and "234 Desert Station", then we cannot safely merge them into one. In that case we need to have two entries in the Customer table, one for each.

Consequently, customer name cannot be a primary key, we need to assign some other identifier. That makes it hard to do in parallel in various replicas of a distributed storage system.

Also, if you change the address of a customer while in two-table view, it has a different effect than if you change the address on an order in one-table view.

But that's not impossible to represent I think, it reminds me of the "halve this recipe" operation from https://mattweidner.com/2023/09/26/crdt-survey-1.html

[michielbdejong]

A customer with zero orders would have to be represented in the one-table view with item and quantity set to null.

So:

• fields
  • item is a string or null
  • quantity is an integer or null
  • ship date is a date or null
  • customer name is a string
  • customer address is a string
• operations:
  • add/remove an order
  • add/remove a customer (cascading delete for orders of that customer)
  • update item / quantity / ship date / customer name / customer address
  • view as one table
  • view as two tables

[michielbdejong]

To generalise the solution away from the example:

• let's only support strings for now, not dates and integers
• the main dataset is a two-dimensional array of strings
• arbitrary multi-table views can be defined by saying which columns go into which table
• if you edit a row in a table, this edit should be visible consistently for other nodes that have other table definitions

[michielbdejong]

The implementation should be more efficient than just storing the whole two-dimensional array, but its behaviour should be equivalent

[michielbdejong]

I guess I could just define a Lens between the one-table and the two-table view.

[michielbdejong]

All replicas should switch to the new schema and the code that lists unshipped orders should change at the same time. This can be done with a Lens, probably?

[michielbdejong]

I looked into Cambria and its existing lenses. An 'extract' lens should be possible.

Input document:

{
   "orders": [
    {
      "item":"anvil",
      "quantity": 1,
      "ship_date": "2/3/23",
      "customer_name": "Wile E Coyote",
      "customer_address": "123 Desert Station"
    },
    {
      "item":"dynamite",
      "quantity": 2,
      "ship_date": null,
      "customer_name": "Daffy Duck",
      "customer_address": "White Rock Lake"
    },
    {
      "item":"bird seed",
      "quantity": 1,
      "ship_date": null,
      "customer_name": "Wile E Coyote",
      "customer_address": "123 Desert Station"
    }
  ]
}

Lens:

lens:
  - extract
  [...]

Output document:

{
  "orders": [
   {
     "item":"anvil",
     "quantity": 1,
     "ship_date": "2/3/23",
     "customer": 1
   },
   {
     "item":"dynamite",
     "quantity": 2,
     "ship_date": null,
     "customer": 2
   },
   {
     "item":"bird seed",
     "quantity": 1,
     "ship_date": null,
     "customer": 1
   }
  ],
  "customers": [
    {
      "id": 1,
      "name": "Wile E Coyote",
      "address": "123 Desert Station"
    },
    {
      "id": 2,
     "name": "Daffy Duck",
     "address": "White Rock Lake"
    }
  ]
}

[michielbdejong]

A but to make it deterministic you need to know the LRI mapping!