...
| Triple Store Data Structure | Pros | Cons | Comments |
|---|---|---|---|
| doubly linked list | + all updates effect at most 3 items (i.e., prev, current, and next) | - requires traversal of links during fetch (i.e. fetch each item individually - one query for each item) | |
| doubly linked list + order index | + much faster fetch retrieving all items in the range with a single querya range (i.e., single query gets all items) | - adding/removing items from list can be very slow when item is early in the list (worst case touches all list items) |
...
| In-memory Data Structure | Pros | Cons | Comments |
|---|---|---|---|
| doubly linked list | + least amount of processing during fetch (probably not significant relative to overall processing required) | - iteration requires traversing next links | |
| convert to array on fetch | + allows for fast access by position to loaded items | ||
| convert to hash on fetch | + allows for fast fast access by proxy URI to loaded items | - iteration requires traversing next links | I anticipate the need to have direct access by proxy URI more than positional. |
...
List Header Info
Lists with headers will hold the following informationThe list header info will be a hash. It holds information about the list as a whole and the currently loaded range of items as a sub-structure. The values for the list information stored depends on the type of the loaded items sub-structure. The loaded items sub-structure holds items as a group are in-memory using one of four possible grouping methods: doubly linked lists, doubly linked lists + order index, array, or hash with proxy URI as the key. NOTE: Order index is global to the entire list. The array and hash implementations may also have this global order index information stored with the item info.
| example value types | Comments | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| key | description of value | doubly linked | doubly linked + order | array | hash | ||||
| first | pointer to first item in list | URI of first proxy | URI of first proxy | URI of first proxy | URI of first proxy | ||||
| last | pointer to last item in list | URI of last proxy | URI of last proxy | URI of last proxy | URI of last proxy | ||||
| count | count of all items in list | X | X | X | X | last.index | last.index | last.index | Count for full list is available for array and hash when order index is stored in triplestore. |
| first_loaded | pointer to first item in loaded range of items | item | item | array[0] | URI of first loaded proxy | ||||
| current | pointer to current item | item | item | int cpos | URI of current proxy |
| |||
| last_loaded | pointer to last item in loaded range of items | item | item | array[size of array] | URI of last loaded proxy | ||||
| count_loaded | count of items in currently loaded range | X | =position of last - position of first | size of array | size of hash | ||||
| resume_token | pointer to item after last_loaded | URI of proxy | URI of proxy | URI of proxy | URI of proxy | ||||
| loaded_items | pointer to loaded items | use first_loaded | use first_loaded | array | hash | ||||
List Item Info
Each item's info is stored in a hash. It holds information about the individual item. The loaded items as a group are in-memory using one of four possible grouping methods: doubly linked lists, doubly linked lists + order index, array, or hash with proxy URI as the key.
| example value types | |||||||
|---|---|---|---|---|---|---|---|
| key | description of value | doubly linked | doubly linked + order | array | hash | Comments | |
| uri | URI of proxy for this item | URI of this proxy | URI of this proxy | URI of this proxy | URI of this proxy | This is the hash key for loaded_items when the list is implemented as a hash. | |
| prev | pointer to previous item in list | URI of prev proxy | URI of prev proxy | = p - 1 | URI of prev proxy | ||
| next | pointer to next item in list | URI of next proxy | URI of next proxy | = p + 1 | URI of next proxy | ||
| prev_loaded | pointer to previous item in loaded range of items | prev item | prev item | = pl - 1 | URI of prev proxy | ||
| next_loaded | pointer to next item in loaded range of items | next item | next item | = pl + 1 | URI of next proxy | ||
| proxyFor | URI of list item being aggregated | URI | URI | URI | URI | ||
| proxyIn | URI of list aggregation | URI of aggregation | URI of aggregation | URI of aggregation | URI of aggregation | ||
| proxyIn_loaded | pointer to List Header | header | header | header | header | ||
| position (p) | position in full list | X | p | p | X | p | Position in full list is available for array and hash when order index is stored in triplestore. |
| position_loaded (pl) | position in loaded range of items | X | pl | pl | X | ||
...