Negative Databases
Demo
Papers
Software
People
Museum
Links
Negative Database Prototype Software
This is the repository for Negative Database research software created at UNM.
| Development Dates | Description | Version | Download |
| Online Algorithm | |||
| Nov, 2006 - June, 2007 | Negative Relational Algebra, cited in [ETAF07]. | v.53 | negdb-v.53.tar.gz |
| Mar, 2006 - Nov, 2006 | Hard-to-reverse singleton NDB, cited in [EAHJF06],[EAHJF07]. | v.35 | negdb-v.35.tar.gz |
| July, 2005 - Mar, 2006 | Faster C version: Patricia Tries; 64-bit support; empty_DB per spec; compiler directives for NPG variations. | v.19.1 | negdb-v.19.1.tar.gz |
| Dec, 2004 - June, 2005 | Stable C version (primarily used for [EAFH05]) — the initial 'online' demo. | v.07 | negdb-v.07.tar.gz |
| Dec, 2003 - Nov, 2004 | Perl prototype (cited in [EAFH04]) — provides the query and clean/morph functions for the 'batch' demo. | v.43 | updatedb10.pl |
| Batch Algorithm | |||
| Dec, 2003 - July, 2004 | Perl prototype (based on [EFH04]) — the current 'batch' demo. | v.40 | prefixalg7.pl |
History
Prototype development in Perl began December 2003 as proof-of-concept of Fernando Esponda's Negative Database algorithms as originally presented in [EFH04]. By July 2004, the batch processing prototype, along with an online query, became available on the Negative Database website.The first implementation of the online algorithms specified in [EAFH04] was written in Perl in tandem with that paper. As suggested by [EAFH04], a first cut at a cleanup function was later added to the prototype and to the website. A reimplementation of the online algorithms in C for higher performance that began in December 2004 was used by the website 'online' demo in April 2005, and was the primary source for the experimental results in [EAFH05]. During the summer of 2005, the C version gained an order of magnitude speedup with the addition of the Patricia Trie as the negative database internal data structure.
In 2006, we added two more ways to create new negative databases: highly likely 'empty' databases using a well-known random SAT formula; and, the hard-to-reverse 'singleton' negative database that represents a single record as described in [EAHJF06],[EAHJF07].
Next, we expanded the practicality of negative databases and their range of application with the definition of a relational algebra for negative databases that was implemented and cited in [ETAF07].
This project boldly goes on through mid-2008.
Negative Database software is released under the GNU General Public License (GPL).
Fernando Esponda at fernando.esponda@itam.mx