<commit_before>= New tree structure
v1.0, June 2015
:imagesdir: resources/images/
:toc: left
:toclevels: 4
:toc-class: toc2
:icons: font
:iconfont-cdn: //cdnjs.cloudflare.com/ajax/libs/font-awesome/4.3.0/css/font-awesome.min.css
:stylesdir: resources/style/
:stylesheet: asciidoctor.css
:description: New tree structure documentation
:keywords: documentation, NSL, APNI, API, APC, tree
:links:
:numbered:

The current tree structure is over complicated and difficult to validate and maintain going forward. The reasons for this
are many, but basically come down to changing understanding of requirements.

I propose to scale back and simplify the structure used to store the trees and to only implement what is currently required,
then evolve the implementation as needed.

The main change in requirements is the idea of using a workspace, or draft tree, to do work. The workspace would then be
published as a new version. once a version is published it is immutable _except_ for minor typographical changes as determined
by policy.

****
This work is designed to make the tree easy to understand and reason about, and therefore

 * easier to change and maintain over time
 * improve performance
****

== Requirements

=== Major requirements:

 . The tree must store and display the parent child taxonomic relationship between names.
 . The tree must be versioned so that a citation (id) of a tree element must reproduce the tree as it was when it was
 viewed.
 . A link to an element on the tree should be able to identify the version of the tree and reproduce that version.
 . You should be able to link to a _version_ of the tree and get the current tree easily.
 . The tree must enforce strict rules about the placement of names on a tree.
 . Profile data including only Comment and Distribution data is to be stored in the tree structure.
 . Tree elements are pointers to an Instance as a representation of a Taxon Concept.
 . Tree elements can represent Accepted and Excluded items which need to be distinguished. This appears to be accepted
 and not accepted, but treated. The "Excluded" is a covering term of a number of reasons these names are not accepted
 (e.g. doubtful) but the distinction is not required. As such for now we can just indicate an element is Accepted or Not.
 . Easy to work with a version of the tree.
 . All common operations must be fast. You should be able to query the status of a name on the current tree without
 noticeable delay.
 . Editors should be able to work on a draft version of the tree without it being public, then publish it at a time of
 their choosing.
 . Versions should be released as a unit of work, collecting a set of changes together (policy).
 . The users need to be able to add a log entry describing the work done and referencing the documents that lead to the changes.
 . Multiple workspaces that can be merged over different time frames is a requirement.
 . It would be nice to be able to list and view older version of the tree and see what changed (diffing)
 . It would be nice to be able to archive older versions of the tree without breaking it.
 . we want to access the trees through RDF.

==== Uber trees

 . we must be able to create an "uber tree" from multiple sub trees.
 . The uber tree should be able to merge sub trees from multiple points - for example lichens have multiple connections
  the the fungi tree.
 . Uber tree elements need to Link back to source tree nodes if compositional.

according to https://www.environment.gov.au/science/abrs/publications/other/numbers-living-species/executive-summary[ABRS Numbers of Living Species in Australia and the World]
there are ~2million species in the world that we should aim to handle in an uber tree.

==== Use cases

 . creation of accepted taxonomic trees with strict hierarchical placement rules within a shard.
 . creation of a list of taxon concepts commonly (only) from family down, known as a checklist, from one or more shards.
 these trees may have more relaxed placement rules.
 . creation of composite (uber) trees made from multiple sub trees, such as accepted taxonomic trees from multiple shards

WARNING: We should take a closer look at the needs of List compilers and Tree composers to see if the difference in the
 set or requirements leads to different solutions for each.

==== Editors

Based on the above use cases, and current editor usage, it looks like we need two different editing pathways for trees.

  . In instance editor tree editing: Where the advanced editor can create specific taxonomic concepts for accepted trees
  in accordance with some authority such as CHAH.
  . A composition editor that can compose multiple trees into an uber tree, or create a checklist. This doesn't require the
  ability to edit instances, just choose concepts, or other tree elements/sections.

Perhaps the second, compositional, editor is logically broken into an uber tree manager and a checklist editor.

==== Search

We need to clearly define the  difference between the search on names (the APNI search) and the search requirements on
trees. At the moment there is confusion because some searches in the advanced search are mix tree and name concerns.

NOTE: <NAME>. put this view forward too.

===== use cases

 . search a tree for names under a name and bring back the results displaying the apni or apc format output
   * search synonyms or accepted only
   * search based on native, naturalised, distribution or profile data.
   * further advanced filtering based on name/instance type, tags, author etc.
 . search a tree for names independent of any tree and display in APNI format - this may be an advanced search on name types
  tags, instance types, and may require knowledge of the Family.
 . Name check - a specific check against the accepted tree in a shard.

===== implementation (discussion)

Tree searches should be associated with the tree they are on because a tree may be separated from the name and instance
data it is pointing at. In the case of the uber trees they may be pointing to multiple shards.

Since trees contain the name and instance id, but not instance data a tree search may bring back a list of names that can
in turn fetch APNI or APC format data via the existing service API (much like the existing service search).

If we want to implement a closer coupled database implementation in the search we could link to multiple shard databases
to get the data. *I prefer the previous solution as it allows fully autonomous trees and lists to exist that just use
linked data.* However speed will need to be taken into account when looking at this, which means looking at if the service
APIs need improving or the solution is limited to direct database connections.

We need to carefully consider what is offered in search and how you discover what can be searched... initially of course
we are publicly offering only the APC as a cross shard search, and then moving up to NSL including AFD.

Trees that are linked to a shard, e.g. the Vascular APC tree, that have a database relationship to the name and instance
data in the shard can take advantage of joins for more complex queries.

Cross shard searching in general needs an API approach where an API (which could be just a database connection) is used
to collect data, then a map/reduce/sort approach is used to filter and sort results. The name paths and sort names will
help in collating and sorting results from multiple sources.

See https://www.anbg.gov.au/25jira/browse/NSL-2412[NSL-2312]

After discussion with <NAME> and following from user feedback and experience the use of the name tree search may
be a reflection of the way we use the "product" concept and clarification of how the sets of data can be used, and what
they should be used for.

At the moment we try and describe this in the APNI and APC product descriptions.

APNI
****
The Australian Plant Name Index (APNI) is a tool for the botanical community that deals with plant names and their usage
in the scientific literature, whether as a current name or synonym. APNI does not recommend any particular taxonomy or
nomenclature. For a listing of currently accepted scientific names for the Australian vascular flora, please use the
Australian Plant Census (APC) link above.
****

APC
****
The Australian Plant Census (APC) is a list of the accepted scientific names for the Australian vascular flora, ferns,
gymnosperms, hornworts and liverworts, both native and introduced, and includes synonyms and misapplications for these
names. The APC covers all published scientific plant names used in an Australian context in the taxonomic literature,
but excludes taxa known only from cultivation in Australia. The taxonomy and nomenclature adopted for the APC are endorsed
by the Council of Heads of Australasian Herbaria (CHAH).
****

As Greg points out though, we don't limit the search, because people are asking "within" questions from APNI. This
question comes about because scientific names intrinsically, but unreliably, describe or imply rank and hierarchy
information, except where they don't.

It seems to me that we need to explicitly combine the name and taxonomy searches and express clearly what it is the
user is asking: for example "what is in the family Fabaceae according to Maberly" or "what is in the family Fabaceae
according to APC" and then we can do useful things like "compare the family Fabaceae according to Maberly and APC"

By combining we can ask questions like "What is not in APC but is in Maberly" so long as we can emphasize the context
of the APNI/NSL dataset.

=== Change over requirements:

 . We must maintain existing links to trees (APC) that have been used prior to this change. This means any links to
 existing nodes must resolve to the same instance data and position in the tree structure. The intrinsic data should not
 change, though extraneous data may be left out (broken links, some RDF identifiers that didn't lead to real data).
 . Editing the tree should work and be possible from the point of change over.

== Concept

The concept for the new structure is to remove the need for link objects and simply copy the list of tree elements for
each version of the tree. The Workspace is then a copy of the current tree that is then altered. When the workspace is
ready it is published as the latest version of the tree by making it the current version. A copy of the current version
is then made to create the new workspace version.

We track changes in the tree by maintaining a previous link that points to the tree_element in the previous version.

Versions are grouped by a tree_version which is associated with a tree. Tree_elements are associated with a tree_version.

 Tree <- [Tree_Versions] <- [Tree_Elements]

The tree holds a pointer to the current tree and a default workspace.

This concept trades storage efficiency for simplicity. Excessive numbers of versions could create a lot of copied
tree elements, but the workspace/publish model may also lead to a more structured release of versions
(e.g. once a Day/Week/Month) instead of on the fly changes.

=== Autonomous trees

Trees should be able to be autonomous from the shards. This means that database foreign keys to names and instances are
not enforced (i.e. no direct FK relationship). This means we need to rely on the link to identify the instances. It also
means that we want to copy the data required to ask questions of the tree into the tree structure as much as possible.

Whilst we will rely on the link to reference the data in the shards we will store the instance and name id (as a Long),
which means also that we need to store the source shard for the instance and name. If a placed name later becomes
de-duplicated we may have to update the id by using the mapper (rare).

=== Data usage vs speed

Copying the tree for every version is less space efficient than the current model, but affords many benefits. At the
current size of the APC tree 35k tree_elements are required for each copy.

NOTE: these are updated usage figures after spiking and importing actual data, the old guesstimate has been removed.

After doing the spike and adding in all the additional data to make the trees autonomous we can compare actual data sizes.

In APNI:

|===
| table | total size including inexes

| tree_node
| 282MB (inc 233MB index)

| tree_link
| 1394MB (inc 693MB index)

| tree_element (144 versions)
| 13GB (inc 2.7GB index)
|===

which makes the new tree structure  ~ 8 times the size of the old one without any real optimisation.
Extrapolating we get ~90MB per version.

[source]
.table-size.sql
----
SELECT
  *,
  pg_size_pretty(total_bytes) AS total,
  pg_size_pretty(index_bytes) AS INDEX,
  pg_size_pretty(toast_bytes) AS toast,
  pg_size_pretty(table_bytes) AS TABLE
FROM (
       SELECT
         *,
         total_bytes - index_bytes - COALESCE(toast_bytes, 0) AS table_bytes
       FROM (
              SELECT
                c.oid,
                nspname                               AS table_schema,
                relname                               AS TABLE_NAME,
                c.reltuples                           AS row_estimate,
                pg_total_relation_size(c.oid)         AS total_bytes,
                pg_indexes_size(c.oid)                AS index_bytes,
                pg_total_relation_size(reltoastrelid) AS toast_bytes
              FROM pg_class c
                LEFT JOIN pg_namespace n ON n.oid = c.relnamespace
              WHERE relkind = 'r'
            ) a
     ) a;
----


The above estimate is obviously in no way accurate, but it gives us a feel for the amount of data we're looking at, and
the time costs involved in copying nodes.

We can copy all the current nodes _out of_ the database to a file and convert all the data to JSON in 0.2 seconds. Copying
tree elements to new tree elements should not take any longer (it should be quicker).

Also note that the new data structure allows us to partition and archive older versions should we need to.

Copying the 35k tree_elements to a workspace takes about 12.8 seconds:

 sql> INSERT INTO tree_element
 (tree_version_id,
  tree_element_id,
  lock_version,
  excluded,
  display_string,
  element_link,
  instance_id,
  instance_link,
  name_id,
  name_link,
  parent_version_id,
  parent_element_id,
  previous_version_id,
  previous_element_id,
  profile,
  rank_path,
  simple_name,
  tree_path,
  name_path,
  updated_at,
  updated_by)
   (SELECT<commit_msg>remove incorrect statement left in doco.<commit_after>= New tree structure
v1.0, June 2015
:imagesdir: resources/images/
:toc: left
:toclevels: 4
:toc-class: toc2
:icons: font
:iconfont-cdn: //cdnjs.cloudflare.com/ajax/libs/font-awesome/4.3.0/css/font-awesome.min.css
:stylesdir: resources/style/
:stylesheet: asciidoctor.css
:description: New tree structure documentation
:keywords: documentation, NSL, APNI, API, APC, tree
:links:
:numbered:

The current tree structure is over complicated and difficult to validate and maintain going forward. The reasons for this
are many, but basically come down to changing understanding of requirements.

I propose to scale back and simplify the structure used to store the trees and to only implement what is currently required,
then evolve the implementation as needed.

The main change in requirements is the idea of using a workspace, or draft tree, to do work. The workspace would then be
published as a new version. once a version is published it is immutable _except_ for minor typographical changes as determined
by policy.

****
This work is designed to make the tree easy to understand and reason about, and therefore

 * easier to change and maintain over time
 * improve performance
****

== Requirements

=== Major requirements:

 . The tree must store and display the parent child taxonomic relationship between names.
 . The tree must be versioned so that a citation (id) of a tree element must reproduce the tree as it was when it was
 viewed.
 . A link to an element on the tree should be able to identify the version of the tree and reproduce that version.
 . You should be able to link to a _version_ of the tree and get the current tree easily.
 . The tree must enforce strict rules about the placement of names on a tree.
 . Profile data including only Comment and Distribution data is to be stored in the tree structure.
 . Tree elements are pointers to an Instance as a representation of a Taxon Concept.
 . Tree elements can represent Accepted and Excluded items which need to be distinguished. This appears to be accepted
 and not accepted, but treated. The "Excluded" is a covering term of a number of reasons these names are not accepted
 (e.g. doubtful) but the distinction is not required. As such for now we can just indicate an element is Accepted or Not.
 . Easy to work with a version of the tree.
 . All common operations must be fast. You should be able to query the status of a name on the current tree without
 noticeable delay.
 . Editors should be able to work on a draft version of the tree without it being public, then publish it at a time of
 their choosing.
 . Versions should be released as a unit of work, collecting a set of changes together (policy).
 . The users need to be able to add a log entry describing the work done and referencing the documents that lead to the changes.
 . Multiple workspaces that can be merged over different time frames is a requirement.
 . It would be nice to be able to list and view older version of the tree and see what changed (diffing)
 . It would be nice to be able to archive older versions of the tree without breaking it.
 . we want to access the trees through RDF.

==== Uber trees

 . we must be able to create an "uber tree" from multiple sub trees.
 . The uber tree should be able to merge sub trees from multiple points - for example lichens have multiple connections
  the the fungi tree.
 . Uber tree elements need to Link back to source tree nodes if compositional.

according to https://www.environment.gov.au/science/abrs/publications/other/numbers-living-species/executive-summary[ABRS Numbers of Living Species in Australia and the World]
there are ~2million species in the world that we should aim to handle in an uber tree.

==== Use cases

 . creation of accepted taxonomic trees with strict hierarchical placement rules within a shard.
 . creation of a list of taxon concepts commonly (only) from family down, known as a checklist, from one or more shards.
 these trees may have more relaxed placement rules.
 . creation of composite (uber) trees made from multiple sub trees, such as accepted taxonomic trees from multiple shards

WARNING: We should take a closer look at the needs of List compilers and Tree composers to see if the difference in the
 set or requirements leads to different solutions for each.

==== Editors

Based on the above use cases, and current editor usage, it looks like we need two different editing pathways for trees.

  . In instance editor tree editing: Where the advanced editor can create specific taxonomic concepts for accepted trees
  in accordance with some authority such as CHAH.
  . A composition editor that can compose multiple trees into an uber tree, or create a checklist. This doesn't require the
  ability to edit instances, just choose concepts, or other tree elements/sections.

Perhaps the second, compositional, editor is logically broken into an uber tree manager and a checklist editor.

==== Search

We need to clearly define the  difference between the search on names (the APNI search) and the search requirements on
trees. At the moment there is confusion because some searches in the advanced search are mix tree and name concerns.

NOTE: <NAME>. put this view forward too.

===== use cases

 . search a tree for names under a name and bring back the results displaying the apni or apc format output
   * search synonyms or accepted only
   * search based on native, naturalised, distribution or profile data.
   * further advanced filtering based on name/instance type, tags, author etc.
 . search a tree for names independent of any tree and display in APNI format - this may be an advanced search on name types
  tags, instance types, and may require knowledge of the Family.
 . Name check - a specific check against the accepted tree in a shard.

===== implementation (discussion)

Tree searches should be associated with the tree they are on because a tree may be separated from the name and instance
data it is pointing at. In the case of the uber trees they may be pointing to multiple shards.

Since trees contain the name and instance id, but not instance data a tree search may bring back a list of names that can
in turn fetch APNI or APC format data via the existing service API (much like the existing service search).

If we want to implement a closer coupled database implementation in the search we could link to multiple shard databases
to get the data. *I prefer the previous solution as it allows fully autonomous trees and lists to exist that just use
linked data.* However speed will need to be taken into account when looking at this, which means looking at if the service
APIs need improving or the solution is limited to direct database connections.

We need to carefully consider what is offered in search and how you discover what can be searched... initially of course
we are publicly offering only the APC as a cross shard search, and then moving up to NSL including AFD.

Trees that are linked to a shard, e.g. the Vascular APC tree, that have a database relationship to the name and instance
data in the shard can take advantage of joins for more complex queries.

Cross shard searching in general needs an API approach where an API (which could be just a database connection) is used
to collect data, then a map/reduce/sort approach is used to filter and sort results. The name paths and sort names will
help in collating and sorting results from multiple sources.

See https://www.anbg.gov.au/25jira/browse/NSL-2412[NSL-2312]

After discussion with <NAME> and following from user feedback and experience the use of the name tree search may
be a reflection of the way we use the "product" concept and clarification of how the sets of data can be used, and what
they should be used for.

At the moment we try and describe this in the APNI and APC product descriptions.

APNI
****
The Australian Plant Name Index (APNI) is a tool for the botanical community that deals with plant names and their usage
in the scientific literature, whether as a current name or synonym. APNI does not recommend any particular taxonomy or
nomenclature. For a listing of currently accepted scientific names for the Australian vascular flora, please use the
Australian Plant Census (APC) link above.
****

APC
****
The Australian Plant Census (APC) is a list of the accepted scientific names for the Australian vascular flora, ferns,
gymnosperms, hornworts and liverworts, both native and introduced, and includes synonyms and misapplications for these
names. The APC covers all published scientific plant names used in an Australian context in the taxonomic literature,
but excludes taxa known only from cultivation in Australia. The taxonomy and nomenclature adopted for the APC are endorsed
by the Council of Heads of Australasian Herbaria (CHAH).
****

As Greg points out though, we don't limit the search, because people are asking "within" questions from APNI. This
question comes about because scientific names intrinsically, but unreliably, describe or imply rank and hierarchy
information, except where they don't.

It seems to me that we need to explicitly combine the name and taxonomy searches and express clearly what it is the
user is asking: for example "what is in the family Fabaceae according to Maberly" or "what is in the family Fabaceae
according to APC" and then we can do useful things like "compare the family Fabaceae according to Maberly and APC"

By combining we can ask questions like "What is not in APC but is in Maberly" so long as we can emphasize the context
of the APNI/NSL dataset.

=== Change over requirements:

 . We must maintain existing links to trees (APC) that have been used prior to this change. This means any links to
 existing nodes must resolve to the same instance data and position in the tree structure. The intrinsic data should not
 change, though extraneous data may be left out (broken links, some RDF identifiers that didn't lead to real data).
 . Editing the tree should work and be possible from the point of change over.

== Concept

The concept for the new structure is to remove the need for link objects and simply copy the list of tree elements for
each version of the tree. The Workspace is then a copy of the current tree that is then altered. When the workspace is
ready it is published as the latest version of the tree by making it the current version. A copy of the current version
is then made to create the new workspace version.

We track changes in the tree by maintaining a previous link that points to the tree_element in the previous version.

Versions are grouped by a tree_version which is associated with a tree. Tree_elements are associated with a tree_version.

 Tree <- [Tree_Versions] <- [Tree_Elements]

The tree holds a pointer to the current tree and a default workspace.

This concept trades storage efficiency for simplicity. Excessive numbers of versions could create a lot of copied
tree elements, but the workspace/publish model may also lead to a more structured release of versions
(e.g. once a Day/Week/Month) instead of on the fly changes.

=== Autonomous trees

Trees should be able to be autonomous from the shards. This means that database foreign keys to names and instances are
not enforced (i.e. no direct FK relationship). This means we need to rely on the link to identify the instances. It also
means that we want to copy the data required to ask questions of the tree into the tree structure as much as possible.

Whilst we will rely on the link to reference the data in the shards we will store the instance and name id (as a Long),
which means also that we need to store the source shard for the instance and name. If a placed name later becomes
de-duplicated we may have to update the id by using the mapper (rare).

=== Data usage vs speed

Copying the tree for every version is less space efficient than the current model, but affords many benefits. At the
current size of the APC tree 35k tree_elements are required for each copy.

NOTE: these are updated usage figures after spiking and importing actual data, the old guesstimate has been removed.

After doing the spike and adding in all the additional data to make the trees autonomous we can compare actual data sizes.

In APNI:

|===
| table | total size including inexes

| tree_node
| 282MB (inc 233MB index)

| tree_link
| 1394MB (inc 693MB index)

| tree_element (144 versions)
| 13GB (inc 2.7GB index)
|===

which makes the new tree structure  ~ 8 times the size of the old one without any real optimisation.
Extrapolating we get ~90MB per version.

[source]
.table-size.sql
----
SELECT
  *,
  pg_size_pretty(total_bytes) AS total,
  pg_size_pretty(index_bytes) AS INDEX,
  pg_size_pretty(toast_bytes) AS toast,
  pg_size_pretty(table_bytes) AS TABLE
FROM (
       SELECT
         *,
         total_bytes - index_bytes - COALESCE(toast_bytes, 0) AS table_bytes
       FROM (
              SELECT
                c.oid,
                nspname                               AS table_schema,
                relname                               AS TABLE_NAME,
                c.reltuples                           AS row_estimate,
                pg_total_relation_size(c.oid)         AS total_bytes,
                pg_indexes_size(c.oid)                AS index_bytes,
                pg_total_relation_size(reltoastrelid) AS toast_bytes
              FROM pg_class c
                LEFT JOIN pg_namespace n ON n.oid = c.relnamespace
              WHERE relkind = 'r'
            ) a
     ) a;
----


We can copy all the current nodes _out of_ the database to a file and convert all the data to JSON in 0.2 seconds. Copying
tree elements to new tree elements should not take any longer (it should be quicker).

Also note that the new data structure allows us to partition and archive older versions should we need to.

Copying the 35k tree_elements to a workspace takes about 12.8 seconds:

 sql> INSERT INTO tree_element
 (tree_version_id,
  tree_element_id,
  lock_version,
  excluded,
  display_string,
  element_link,
  instance_id,
  instance_link,
  name_id,
  name_link,
  parent_version_id,
  parent_element_id,
  previous_version_id,
  previous_element_id,
  profile,
  rank_path,
  simple_name,
  tree_path,
  name_path,
  updated_at,
  updated_by)
   (SELECT
{'fraction_non_alphanumeric': 0.03886423519622798, 'fraction_numerical': 0.003813618083483567, 'mean_word_length': 3.74268332785268, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 9, 'https://': 4, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7216052', 'n_tokens_mistral': 7309, 'n_tokens_neox': 6920, 'n_words': 4449}