View source for Phylotastic/Datastore

=Datastore subgroup=
The datastore subgroup is keeping notes on a [https://docs.google.com/document/d/1zj601OUQWqh5I-5weo9v3qjlzhNWeh1hunTYGBKfeLA/edit google doc]. The rest of this page is pre-hackathon notes about potential approaches.

[[Image:rdf_model.png|800px]]

= About =

Information on various options that could be used as datastores to host the trees underlying the phylotastic service that prunes trees.

= Requirements = 

A place to document requirements for a phylotastic data store.

=== Ontology ===

Should the datastore include ontology support? This would allow for flexible markup of node attributes, as well as flexible attribution of source trees.

=== Nodes and edges ===

Will the use of the data store require nodes and edges store in separate tables (if SQL used)?

= Datastores =

== RDMBS  ==

=== Options for trees/hierarchies in RDMBS === 

This documentation copied from [http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database  options for storing hierarchical data in a relational database]

* [http://en.wikipedia.org/wiki/Adjacency_list Adjacency List]:
** Columns: ID, ParentID
** Easy to implement.
** Cheap node moves, inserts, and deletes.
** Expensive to find level (can store as a computed column), ancestry & descendants (Bridge Hierarchy combined with level column can solve), path (Lineage Column can solve).
** Use Common Table Expressions in those databases that support them to traverse.
* [http://en.wikipedia.org/wiki/Nested_set_model Nested Set] (a.k.a Modified Preorder Tree Traversal)
**First described by Joe Celko - covered in depth in his book Trees and Hierarchies in SQL for Smarties
** Columns: Left, Right
** Cheap level, ancestry, descendants
** Compared to Adjacency List, moves, inserts, deletes more expensive.
** Requires a specific sort order (e.g. created). So sorting all descendants in a different order requires additional work.
* [https://communities.bmc.com/communities/docs/DOC-9902 Nested Intervals]
** Combination of Nested Sets and Materialized Path where left/right columns are floating point decimals instead of integers and encode the path information. In the later development of this idea nested intervals gave rise to [http://vadimtropashko.files.wordpress.com/2011/07/ch5.pdf matrix encoding].
* [http://www.informationweek.com/news/219400252 Bridge Table] (a.k.a. [http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html Closure Table]: some good ideas about how to use triggers for maintaining this approach)
** Columns: ancestor, descendant
** Stands apart from table it describes.
** Can include some nodes in more than one hierarchy.
** Cheap ancestry and descendants (albeit not in what order)
** For complete knowledge of a hierarchy needs to be combined with another option.
* [http://evolt.org/node/4047/ Flat Table]
** A modification of the Adjacency List that adds a Level and Rank (e.g. ordering) column to each record.
** Expensive move and delete
** Cheap ancestry and descendants
** Good Use: threaded discussion - forums / blog comments
* [http://www.ferdychristant.com/blog//articles/DOMM-7QJPM7 Lineage Column] (a.k.a. [https://communities.bmc.com/communities/docs/DOC-9902 Materialized Path], Path Enumeration)
** Column: lineage (e.g. /parent/child/grandchild/etc...)
** Limit to how deep the hierarchy can be.
** Descendants cheap (e.g. LEFT(lineage, #) = '/enumerated/path')
** Ancestry tricky (database specific queries)

=== RDBMS ===

{| class="wikitable" style="text-align: left"
! Feature
! MySQL
! PostgreSQL
|-
| Max allowed packet (a limit on the list of species for trimming the tree)
| By default this is 1 MB but can be increased
| 
|-
| Forced Referential integreity
| Yes ([http://www.sitepoint.com/mysql-innodb-table-pros-cons/ with InnoDB tables] but these generally are slower than [http://www.kavoir.com/2009/09/mysql-engines-innodb-vs-myisam-a-comparison-of-pros-and-cons.html MyISAM tables])
| Yes
|-
| Stored procedures
| Yes (> [http://dev.mysql.com/doc/refman/5.0/en/stored-routines.html MySQL 5.0]) However does not accept arrays (ie List of leaf nodes) as variables in stored procedures.
| Yes
|}

=== Schema ===

The following schema support storing trees.

{| class="wikitable" style="text-align: left"
! Schema
! Supported RDBMS
! Ontology Support
|-
|[http://www.biosql.org/wiki/Extensions BioSQL::Phylo]
| PostgreSQL
| Yes
|-
|[http://www.ensembl.org/info/docs/api/compara/compara_schema.html EnsembleCompara]
|PostgreSQL, MySQL
|No, but it is possible with [https://github.com/jestill/iplant-treerec/blob/master/schema/tr_schema_mysql.sql schema extensions] that add [http://gmod.org/wiki/Chado_CV_Module Chado controlled vocabulary tables].
|-
|[http://gmod.org/wiki/Chado_Phylogeny_Module Chado::Phylogeny ]
|PostgreSQL, MySQL
|Yes (OBO, OWL with conversion to OBO)
|}

=== Additional Information ===

* [http://vadimtropashko.wordpress.com/2008/08/09/one-more-nested-intervals-vs-adjacency-list-comparison/ Good overview table of adjacency lists vs. Nested intervals]
* [http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ Managing Hierarchical Data in MySQL]
* [http://www.sitepoint.com/hierarchical-data-database/ Storing Hierarchical Data in a Database]
* [http://www.slideshare.net/billkarwin/models-for-hierarchical-data Slideshare .. Models for Hierarchical data]
* [http://troels.arvin.dk/db/rdbms/links/#hierarchical More links on hierarchical data in SQL]

== NOSQL ==

Examples of [http://www.mongodb.org/display/DOCS/Trees+in+MongoDB storing trees in MongoDB].

== Hadoop ==

=== HBASE === 

HBase is an open-source, distributed, versioned, column-oriented store modeled after Google's Bigtable: A Distributed Storage System for Structured Data by Chang et al. Just as Bigtable leverages the distributed data storage provided by the Google File System, HBase provides Bigtable-like capabilities on top of Hadoop and HDFS.

* [https://hbase.apache.org/ Apache HBase Home]

=== Tolomatic ===

[https://github.com/phylotastic/tolomatic Rutger's documentation on using MapReduce]

=== Additional Information ===

* [http://gigaom.com/2010/08/01/meet-big-data-equivalent-of-the-lamp-stack/ Meet the Big Data Equivalent of the LAMP Stack]

[[Category:Phylotastic]]