README
¶
Origins
Origins is an open source bi-temporal database for storing and retrieving facts about the state of things. It supports "time-travel" queries, aggregate views, and change detection.
- This project is in an alpha stage of development.
- Interested in working on a temporal database written in Go? Get in touch!
- For more information consult the documentation.
- Learn how you can contribute.
Docker
Run in-memory Origins HTTP service.
docker run -p 49110:49110 dbhi/origins http
Use the BoltDB storage engine with a volume.
docker run \
-p 49110:49110 \
-v <host-dir>:/data \
dbhi/origins http \
--storage=boltdb \
--path=/data/origins.boltdb
Development
Environment
Install Go
brew on OS X.
brew install go
Otherwise follow these instructions.
Install Go dependencies
make install
Testing
Ensure the test dependencies are installed:
make test-install
Then run:
make test
Building
To the build the origins command in ./cmd/origins locally, simply run:
make build
To build binaries for each platform, ensure the build dependencies are installed:
make build-install
Then run:
make build
Documentation
¶
Overview ¶
Origins is an open source bi-temporal database for storing and retrieving facts about the state of things. It supports "time-travel" queries, aggregate views, and change detection.
The primary interface is the CLI which can be installed by running:
go get -u github.com/chop-dbhi/origins/cmd/origins
This package defines some of the primitive structures and algorithms for manipulating, reading, and writing facts and is used to build higher level client APIs.
Fact sorting is done using the Timsort algorithm which is hybrid algorithm of merge sort and insertion sort. This is chosen because facts are generally partially sorted by entity since facts are derived from higher level objects.
For comparison, comparators for the default Quicksort algorithm are implemented for benchmarking purposes.
Wikipedia: https://en.wikipedia.org/wiki/Timsort Comparison to quicksort: http://stackoverflow.com/a/19587279/407954
Index ¶
- Constants
- Variables
- func AEVTComparator(f1, f2 *Fact) bool
- func AVETComparator(f1, f2 *Fact) bool
- func AttributeComparator(f1, f2 *Fact) bool
- func Copy(it Iterator, w Writer) (int, error)
- func Decompressor(r io.Reader, f string) (io.Reader, error)
- func DetectFileCompression(n string) string
- func DetectFileFormat(n string) string
- func EAVTComparator(f1, f2 *Fact) bool
- func EntityComparator(f1, f2 *Fact) bool
- func Exists(iter Iterator, predicate func(*Fact) bool) bool
- func IdentComparator(id1, id2 *Ident) bool
- func Init(name string, opts *storage.Options) (storage.Engine, error)
- func Map(iter Iterator, proc func(*Fact) error) error
- func MapFacts(iter FactsIterator, proc func(facts Facts) error) error
- func Read(it Iterator, buf Facts) (int, error)
- func Sort(facts Facts, comp Comparator)
- func TimeComparator(f1, f2 *Fact) bool
- func Timsort(facts Facts, comp Comparator)
- func TransactionComparator(f1, f2 *Fact) bool
- func Transactions(iter Iterator) ([]uint64, error)
- func VAETComparator(f1, f2 *Fact) bool
- func ValueComparator(f1, f2 *Fact) bool
- type Buffer
- type CSVReader
- type CSVWriter
- type Comparator
- type Fact
- type Facts
- type FactsIterator
- type Flusher
- type Ident
- type Identifier
- type Idents
- type Iterator
- type Operation
- type UniversalReader
- type Writer
Constants ¶
const ( AttrsDomain = "origins.attrs" TypesDomain = "origins.types" MacrosDomain = "origins.macros" DomainsDomain = "origins.domains" TransactionsDomain = "origins.transactions" CardinalitiesDomain = "origins.cardinalities" )
const Version = "0.1"
Variables ¶
var ( ErrHeaderRequired = errors.New("A header is required with field names.") ErrRequiredFields = errors.New("The entity, attribute, and value fields are required.") )
var StorageEngines = map[string]storage.Initializer{ "bolt": boltdb.Init, "boltdb": boltdb.Init, "mem": memory.Init, "memory": memory.Init, }
Registered storage engines with their initializers. Aliases are supported as separate entries.
Functions ¶
func AEVTComparator ¶
AEVTComparator compares two facts using an attribute-entity-value-time sort.
func AVETComparator ¶
AVETComparator compares two facts using an attribute-value-entity-time sort.
func AttributeComparator ¶
AttributeComparator compares two attribute identities.
func Copy ¶
Copy reads all facts from the reader and copies them to the writer. The number of facts written is returned and an error if present.
func Decompressor ¶
Decompressor returns a reader that wraps the input reader for decompression.
func DetectFileCompression ¶
DetectFileCompression detects the file compression type based on the filename.
func DetectFileFormat ¶
DetectFileFormat detects the file format based on the filename.
func EAVTComparator ¶
EAVTComparator compares two facts using an entity-attribute-value-time sort.
func EntityComparator ¶
EntityComparator compares two entity identities.
func Exists ¶
Exists takes an iterator and predicate function and returns true if the predicate matches.
func IdentComparator ¶
IdentComparator compares to identities.
func Sort ¶
func Sort(facts Facts, comp Comparator)
Sort performs an in-place sort of the facts using the built-in sort method.
func Timsort ¶
func Timsort(facts Facts, comp Comparator)
Timsort performs an in-place sort of the facts using the Timsort algorithm.
func TransactionComparator ¶
TransactionComparator compares two value identities.
func Transactions ¶
Transactions extract a unique set of transaction IDs from the iterator.
func VAETComparator ¶
VAETComparator compares two facts using an value-attribute-entity-time sort.
func ValueComparator ¶
ValueComparator compares two value identities.
Types ¶
type Buffer ¶
type Buffer struct {
// contains filtered or unexported fields
}
Buffer holds a slice of facts. The buffer dynamically grows as facts are written to it. The position is maintained across reads.
func (*Buffer) Reset ¶
func (b *Buffer) Reset()
Reset resets the buffer so it has not content. This is equivalent to calling b.Truncate(0).
type CSVReader ¶
type CSVReader struct {
// contains filtered or unexported fields
}
func NewCSVReader ¶
type CSVWriter ¶
type CSVWriter struct {
// contains filtered or unexported fields
}
func NewCSVWriter ¶
type Comparator ¶
Comparator is a function type that compares two facts for the purposes of sorting. It returns true if the first fact should come before the second fact.
type Fact ¶
type Fact struct {
// Denotes whether the fact is asserted or retracted.
Operation Operation
// The domain the fact applies to. The motivation is to enable asserting
// facts about entities in different domains. This model decouples content
// from context to support auxillary information.
Domain string
// The entity, attribute, and value of the fact. Also referred to as a
// "triple", these make up the content of the fact. The entity and attribute
// must have a domain associated with it. If not specified, they default to
// the fact domain. If a value has a domain specified, it will be interpreted
// as a reference to an entity, otherwise it will be treated as a literal.
Entity *Ident
Attribute *Ident
Value *Ident
// The time the fact is true in the world. Also known as the "valid time",
// this can be set if the fact is true at an earlier or later time than
// when it was added.
Time time.Time
// Transaction that processed this fact. The transaction serves as the
// temporal component of the fact. Time-travel queries rely on the
// transaction time to filter out facts not applicable in the specified
// time range.
Transaction uint64
}
Fact is the fundamental unit of the information model. It is an immutable declaration of something that is true.
func First ¶
First takes an iterator and predicate function and returns the first fact that matches the predicate.
func (*Fact) MarshalJSON ¶
type Facts ¶
type Facts []*Fact
Facts is a slice of facts.
func Reflect ¶
Reflect takes a value and returns a set of partially defined facts containing attribute and value components. Currently, struct values or pointers to struct values are supported. Struct fields with a primitive type are included (support for pointers coming soon). The `origins` tag can be used to specify an alternate identity name, an attribute domain name or omit the field all together.
type FactsIterator ¶
type Flusher ¶
type Flusher interface {
Flush() error
}
Flusher is an interface that defines the Flush method. Types that are buffered and require being *flushed* at the end of processing implement this method.
type Ident ¶
Ident models an identity of something. For entities and attributes a domain is required. For values, if the domain is ommitted, the identity is considered a literal value.
func ParseIdent ¶
ParseIdent parses a fully qualified identity string, validates the contents and returns an identity value.
type Identifier ¶
type Identifier interface {
Ident() *Ident
}
Identifier defines the Ident method that returns and Ident value. Types that implement will used during reflection to be properly represented as facts.
type Idents ¶
type Idents []*Ident
Idents is a slice of idents.
func Attributes ¶
Attributes extract a unique set of attribute identities from the iterator.
type Iterator ¶
type Iterator interface {
// Next returns the next available fact in the stream.
Next() *Fact
// Err returns an error if one occurred while iterating facts.
Err() error
}
Iterator is an interface that reads from an underlying stream of facts and makes facts available through the Next() method. The usage of the this interface is as follows:
// The fact will be nil if the underlying stream is exhaused
// or an error occurred.
for f := it.Next(); f != nil {
// Do something with the fact
}
if err := it.Err(); err != nil {
// Handle the error.
}
type Operation ¶
type Operation int8
Operation denotes the validity of a fact. A fact can be asserted in which case it is deemed valid and true or retracted which denotes the fact is no longer valid or true. A fact may be retracted without being asserted first. This denotes some fact is known not to be true without necessarily knowing what is true.
func ParseOperation ¶
ParseOperation normalizes the string operation denoting an assertion or retraction of a fact.
func (Operation) MarshalJSON ¶
type UniversalReader ¶
type UniversalReader struct {
// contains filtered or unexported fields
}
UniversalReader wraps an io.Reader and replaces carriage returns with newlines.
func NewUniversalReader ¶
func NewUniversalReader(r io.Reader) *UniversalReader
NewUniversalReader returns a UniversalReader that wraps the passed io.Reader.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
cmd
|
|
|
Package dal is a generated protocol buffer package.
|
Package dal is a generated protocol buffer package. |
|
The schema package defines types for representing the optional schema support in Origins.
|
The schema package defines types for representing the optional schema support in Origins. |
|
The storage package defines a key-value based storage engine interface.
|
The storage package defines a key-value based storage engine interface. |
|
boltdb
The boltdb package implements a storage engine for BoltDB.
|
The boltdb package implements a storage engine for BoltDB. |
|
memory
The memory package implements an in-memory storage storage.
|
The memory package implements an in-memory storage storage. |
|
The transactor package contains the APIs for writing facts to storage.
|
The transactor package contains the APIs for writing facts to storage. |