graph

package
v0.6.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 20, 2016 License: Apache-2.0 Imports: 11 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrQuadExists    = errors.New("quad exists")
	ErrQuadNotExist  = errors.New("quad does not exist")
	ErrInvalidAction = errors.New("invalid action")
)
View Source 
var (
	// IgnoreDuplicates specifies whether duplicate quads
	// cause an error during loading or are ignored.
	IgnoreDuplicates = false

	// IgnoreMissing specifies whether missing quads
	// cause an error during deletion or are ignored.
	IgnoreMissing = false
)
View Source 
var ErrCannotBulkLoad = errors.New("quadstore: cannot bulk load")
View Source 
var ErrDatabaseExists = errors.New("quadstore: cannot init; database already exists")

Functions

func CanNext 

func CanNext(it Iterator) bool

CanNext is a helper for checking if iterator can be Next()'ed.

func ContainsLogIn 

func ContainsLogIn(it Iterator, val Value)

func ContainsLogOut 

func ContainsLogOut(it Iterator, val Value, good bool) bool

func Height 

func Height(it Iterator, until Type) int

Height is a convienence function to measure the height of an iterator tree.

func InitQuadStore 

func InitQuadStore(name, dbpath string, opts Options) error

func IsInvalidAction 

func IsInvalidAction(err error) bool

IsInvalidAction returns whether an error is a DeltaError with the Err field equal to ErrInvalidAction.

func IsPersistent 

func IsPersistent(name string) bool

func IsQuadExist 

func IsQuadExist(err error) bool

IsQuadExist returns whether an error is a DeltaError with the Err field equal to ErrQuadExists.

func IsQuadNotExist 

func IsQuadNotExist(err error) bool

IsQuadNotExist returns whether an error is a DeltaError with the Err field equal to ErrQuadNotExist.

func NextLogIn 

func NextLogIn(it Iterator)

func NextLogOut 

func NextLogOut(it Iterator, ok bool) bool

func QuadStores 

func QuadStores() []string

func RegisterQuadStore 

func RegisterQuadStore(name string, register QuadStoreRegistration)

func RegisterWriter 

func RegisterWriter(name string, newFunc NewQuadWriterFunc)

func UpgradeQuadStore 

func UpgradeQuadStore(name, dbpath string, opts Options) error

func WriterMethods 

func WriterMethods() []string

Types

type ApplyMorphism 

type ApplyMorphism func(QuadStore, Iterator) Iterator

ApplyMorphism is a curried function that can generates a new iterator based on some prior iterator.

type BulkLoader 

type BulkLoader interface {
	// BulkLoad loads Quads from a quad.Unmarshaler in bulk to the QuadStore.
	// It returns ErrCannotBulkLoad if bulk loading is not possible. For example if
	// you cannot load in bulk to a non-empty database, and the db is non-empty.
	BulkLoad(quad.Unmarshaler) error
}

type Delta 

type Delta struct {
	ID        PrimaryKey
	Quad      quad.Quad
	Action    Procedure
	Timestamp time.Time
}

type DeltaError 

type DeltaError struct {
	Delta Delta
	Err   error
}

DeltaError records an error and the delta that caused it.

func (*DeltaError) Error 

func (e *DeltaError) Error() string

type Description 

type Description struct {
	UID       uint64         `json:",omitempty"`
	Name      string         `json:",omitempty"`
	Type      Type           `json:",omitempty"`
	Tags      []string       `json:",omitempty"`
	Size      int64          `json:",omitempty"`
	Direction quad.Direction `json:",omitempty"`
	Iterator  *Description   `json:",omitempty"`
	Iterators []Description  `json:",omitempty"`
}

type FixedIterator 

type FixedIterator interface {
	Iterator
	Add(Value)
}

FixedIterator wraps iterators that are modifiable by addition of fixed value sets.

type Handle 

type Handle struct {
	QuadStore
	QuadWriter
}

func (*Handle) Close 

func (h *Handle) Close()

type IgnoreOpts 

type IgnoreOpts struct {
	IgnoreDup, IgnoreMissing bool
}

type InitStoreFunc 

type InitStoreFunc func(string, Options) error

type IterateChain 

type IterateChain struct {
	// contains filtered or unexported fields
}

IterateChain is a chain-enabled helper to setup iterator execution.

func Iterate 

func Iterate(ctx context.Context, it Iterator) *IterateChain

Iterate is a set of helpers for iteration. Context may be used to cancel execution. Iterator will be optimized and closed after execution.

By default, iteration has no limit and includes sub-paths.

func (*IterateChain) All 

func (c *IterateChain) All() ([]Value, error)

All will return all results of an iterator.

func (*IterateChain) AllValues 

func (c *IterateChain) AllValues(qs QuadStore) ([]quad.Value, error)

AllValues is an analog of All, but it will additionally call NameOf for each graph.Value before returning the results slice.

func (*IterateChain) Each 

func (c *IterateChain) Each(fnc func(Value)) error

Each will run a provided callback for each result of the iterator.

func (*IterateChain) EachValue 

func (c *IterateChain) EachValue(qs QuadStore, fnc func(quad.Value)) error

EachValue is an analog of Each, but it will additionally call NameOf for each graph.Value before passing it to a callback.

func (*IterateChain) Limit 

func (c *IterateChain) Limit(n int) *IterateChain

Limit limits a total number of results returned.

func (*IterateChain) On 

func (c *IterateChain) On(qs QuadStore) *IterateChain

On sets a default quad store for iteration. If qs was set, it may be omitted in other functions.

func (*IterateChain) Paths 

func (c *IterateChain) Paths(enable bool) *IterateChain

Paths switches iteration over sub-paths (with it.NextPath). Defaults to true.

func (*IterateChain) Send 

func (c *IterateChain) Send(out chan<- Value) error

Send will send each result of the iterator to the provided channel.

Channel will NOT be closed when function returns.

func (*IterateChain) SendValues 

func (c *IterateChain) SendValues(qs QuadStore, out chan<- quad.Value) error

SendValues is an analog of Send, but it will additionally call NameOf for each graph.Value before sending it to a channel.

func (*IterateChain) TagEach 

func (c *IterateChain) TagEach(fnc func(map[string]Value)) error

TagEach will run a provided tag map callback for each result of the iterator.

func (*IterateChain) TagValues 

func (c *IterateChain) TagValues(qs QuadStore, fnc func(map[string]quad.Value)) error

TagValues is an analog of TagEach, but it will additionally call NameOf for each graph.Value before passing the map to a callback.

func (*IterateChain) UnOptimized 

func (c *IterateChain) UnOptimized() *IterateChain

UnOptimized disables iterator optimization.

type Iterator 

type Iterator interface {
	Tagger() *Tagger

	// Fills a tag-to-result-value map.
	TagResults(map[string]Value)

	// Returns the current result.
	Result() Value

	// Next advances the iterator to the next value, which will then be available through
	// the Result method. It returns false if no further advancement is possible, or if an
	// error was encountered during iteration.  Err should be consulted to distinguish
	// between the two cases.
	Next() bool

	// These methods are the heart and soul of the iterator, as they constitute
	// the iteration interface.
	//
	// To get the full results of iteration, do the following:
	//
	//  for graph.Next(it) {
	//  	val := it.Result()
	//  	... do things with val.
	//  	for it.NextPath() {
	//  		... find other paths to iterate
	//  	}
	//  }
	//
	// All of them should set iterator.result to be the last returned value, to
	// make results work.
	//
	// NextPath() advances iterators that may have more than one valid result,
	// from the bottom up.
	NextPath() bool

	// Contains returns whether the value is within the set held by the iterator.
	Contains(Value) bool

	// Err returns any error that was encountered by the Iterator.
	Err() error

	// Start iteration from the beginning
	Reset()

	// Create a new iterator just like this one
	Clone() Iterator

	// These methods relate to choosing the right iterator, or optimizing an
	// iterator tree
	//
	// Stats() returns the relative costs of calling the iteration methods for
	// this iterator, as well as the size. Roughly, it will take NextCost * Size
	// "cost units" to get everything out of the iterator. This is a wibbly-wobbly
	// thing, and not exact, but a useful heuristic.
	Stats() IteratorStats

	// Helpful accessor for the number of things in the iterator. The first return
	// value is the size, and the second return value is whether that number is exact,
	// or a conservative estimate.
	Size() (int64, bool)

	// Returns a string relating to what the function of the iterator is. By
	// knowing the names of the iterators, we can devise optimization strategies.
	Type() Type

	// Optimizes an iterator. Can replace the iterator, or merely move things
	// around internally. if it chooses to replace it with a better iterator,
	// returns (the new iterator, true), if not, it returns (self, false).
	Optimize() (Iterator, bool)

	// Return a slice of the subiterators for this iterator.
	SubIterators() []Iterator

	// Return a string representation of the iterator.
	Describe() Description

	// Close the iterator and do internal cleanup.
	Close() error

	// UID returns the unique identifier of the iterator.
	UID() uint64
}

type IteratorStats 

type IteratorStats struct {
	ContainsCost int64
	NextCost     int64
	Size         int64
	ExactSize    bool
	Next         int64
	Contains     int64
	ContainsNext int64
}

type Keyer 

type Keyer interface {
	Key() interface{}
}

Keyer provides a method for comparing types that are not otherwise comparable. The Key method must return a dynamic type that is comparable according to the Go language specification. The returned value must be unique for each receiver value.

type Linkage 

type Linkage struct {
	Dir   quad.Direction
	Value Value
}

Linkage is a union type representing a set of values established for a given quad direction.

type NewQuadWriterFunc 

type NewQuadWriterFunc func(QuadStore, Options) (QuadWriter, error)

type NewStoreForRequestFunc 

type NewStoreForRequestFunc func(QuadStore, Options) (QuadStore, error)

type NewStoreFunc 

type NewStoreFunc func(string, Options) (QuadStore, error)

type NoNext 

type NoNext interface {
	NoNext()
}

NoNext is an optional interface to signal that iterator should be Contain()'ed instead of Next()'ing if possible.

type Options 

type Options map[string]interface{}

func (Options) BoolKey 

func (d Options) BoolKey(key string) (bool, bool, error)

func (Options) IntKey 

func (d Options) IntKey(key string) (int, bool, error)

func (Options) StringKey 

func (d Options) StringKey(key string) (string, bool, error)

type PreFetchedValue 

type PreFetchedValue interface {
	NameOf() quad.Value
}

PreFetchedValue is an optional interface for graph.Value to indicate that quadstore has already loaded a value into memory.

type PrimaryKey 

type PrimaryKey struct {
	// contains filtered or unexported fields
}

func NewSequentialKey 

func NewSequentialKey(horizon int64) PrimaryKey

func NewUniqueKey 

func NewUniqueKey(horizon string) PrimaryKey

func (*PrimaryKey) Int 

func (p *PrimaryKey) Int() int64

func (PrimaryKey) MarshalJSON 

func (p PrimaryKey) MarshalJSON() ([]byte, error)

func (*PrimaryKey) Next 

func (p *PrimaryKey) Next() PrimaryKey

func (*PrimaryKey) String 

func (p *PrimaryKey) String() string

func (*PrimaryKey) UnmarshalJSON 

func (p *PrimaryKey) UnmarshalJSON(bytes []byte) error

type Procedure 

type Procedure int8
const (
	Add    Procedure = +1
	Delete Procedure = -1
)

The different types of actions a transaction can do.

func (Procedure) String 

func (p Procedure) String() string

type QuadStore 

type QuadStore interface {
	// The only way in is through building a transaction, which
	// is done by a replication strategy.
	ApplyDeltas([]Delta, IgnoreOpts) error

	// Given an opaque token, returns the quad for that token from the store.
	Quad(Value) quad.Quad

	// Given a direction and a token, creates an iterator of links which have
	// that node token in that directional field.
	QuadIterator(quad.Direction, Value) Iterator

	// Returns an iterator enumerating all nodes in the graph.
	NodesAllIterator() Iterator

	// Returns an iterator enumerating all links in the graph.
	QuadsAllIterator() Iterator

	// Given a node ID, return the opaque token used by the QuadStore
	// to represent that id.
	ValueOf(quad.Value) Value

	// Given an opaque token, return the node that it represents.
	NameOf(Value) quad.Value

	// Returns the number of quads currently stored.
	Size() int64

	// The last replicated transaction ID that this quadstore has verified.
	Horizon() PrimaryKey

	// Creates a fixed iterator which can compare Values
	FixedIterator() FixedIterator

	// Optimize an iterator in the context of the quad store.
	// Suppose we have a better index for the passed tree; this
	// gives the QuadStore the opportunity to replace it
	// with a more efficient iterator.
	OptimizeIterator(it Iterator) (Iterator, bool)

	// Close the quad store and clean up. (Flush to disk, cleanly
	// sever connections, etc)
	Close()

	// Convenience function for speed. Given a quad token and a direction
	// return the node token for that direction. Sometimes, a QuadStore
	// can do this without going all the way to the backing store, and
	// gives the QuadStore the opportunity to make this optimization.
	//
	// Iterators will call this. At worst, a valid implementation is
	//
	//  qs.ValueOf(qs.Quad(id).Get(dir))
	//
	QuadDirection(id Value, d quad.Direction) Value

	// Get the type of QuadStore
	//TODO replace this using reflection
	Type() string
}

func NewQuadStore 

func NewQuadStore(name, dbpath string, opts Options) (QuadStore, error)

func NewQuadStoreForRequest 

func NewQuadStoreForRequest(qs QuadStore, opts Options) (QuadStore, error)

type QuadStoreRegistration 

type QuadStoreRegistration struct {
	NewFunc           NewStoreFunc
	NewForRequestFunc NewStoreForRequestFunc
	UpgradeFunc       UpgradeStoreFunc
	InitFunc          InitStoreFunc
	IsPersistent      bool
}

type QuadWriter 

type QuadWriter interface {
	// AddQuad adds a quad to the store.
	AddQuad(quad.Quad) error

	// TODO(barakmich): Deprecate in favor of transaction.
	// AddQuadSet adds a set of quads to the store, atomically if possible.
	AddQuadSet([]quad.Quad) error

	// RemoveQuad removes a quad matching the given one  from the database,
	// if it exists. Does nothing otherwise.
	RemoveQuad(quad.Quad) error

	// ApplyTransaction applies a set of quad changes.
	ApplyTransaction(*Transaction) error

	// RemoveNode removes all quads which have the given node as subject, predicate, object, or label.
	RemoveNode(Value) error

	// Close cleans up replication and closes the writing aspect of the database.
	Close() error
}

func NewQuadWriter 

func NewQuadWriter(name string, qs QuadStore, opts Options) (QuadWriter, error)

type StatsContainer 

type StatsContainer struct {
	UID  uint64
	Type Type
	IteratorStats
	SubIts []StatsContainer
}

func DumpStats 

func DumpStats(it Iterator) StatsContainer

type Tagger 

type Tagger struct {
	// contains filtered or unexported fields
}

func (*Tagger) Add 

func (t *Tagger) Add(tag string)

Add a tag to the iterator.

func (*Tagger) AddFixed 

func (t *Tagger) AddFixed(tag string, value Value)

func (*Tagger) CopyFrom 

func (t *Tagger) CopyFrom(src Iterator)

func (*Tagger) CopyFromTagger 

func (t *Tagger) CopyFromTagger(st *Tagger)

func (*Tagger) Fixed 

func (t *Tagger) Fixed() map[string]Value

Fixed returns the fixed tags held in the tagger. The returned value must not be mutated.

func (*Tagger) Tags 

func (t *Tagger) Tags() []string

Tags returns the tags held in the tagger. The returned value must not be mutated.

type Transaction 

type Transaction struct {
	// Deltas stores the deltas in the right order
	Deltas []Delta
	// contains filtered or unexported fields
}

Transaction stores a bunch of Deltas to apply atomatically on the database.

func NewTransaction 

func NewTransaction() *Transaction

NewTransaction initialize a new transaction.

func (*Transaction) AddQuad 

func (t *Transaction) AddQuad(q quad.Quad)

AddQuad adds a new quad to the transaction if it is not already present in it. If there is a 'remove' delta for that quad, it will remove that delta from the transaction instead of actually addind the quad.

func (*Transaction) RemoveQuad 

func (t *Transaction) RemoveQuad(q quad.Quad)

RemoveQuad adds a quad to remove to the transaction. The quad will be removed from the database if it is not present in the transaction, otherwise it simply remove it from the transaction.

type Type 

type Type int

Type enumerates the set of Iterator types. 

const (
	Invalid Type = iota
	All
	And
	Or
	HasA
	LinksTo
	Comparison
	Null
	Fixed
	Not
	Optional
	Materialize
	Unique
	Limit
	Skip
	Regex
	Count
)

These are the iterator types, defined as constants

func RegisterIterator 

func RegisterIterator(name string) Type

RegisterIterator adds a new iterator type to the set of acceptable types, returning the registered Type. Calls to Register are idempotent and must be made prior to use of the iterator. The conventional approach for use is to include a call to Register in a package init() function, saving the Type to a private package var.

func (*Type) MarshalText 

func (t *Type) MarshalText() (text []byte, err error)

func (Type) String 

func (t Type) String() string

String returns a string representation of the Type.

func (*Type) UnmarshalText 

func (t *Type) UnmarshalText(text []byte) error

type UpgradeStoreFunc 

type UpgradeStoreFunc func(string, Options) error

type Value 

type Value interface {
	IsNode() bool
}

Value defines an opaque "quad store value" type. However the backend wishes to implement it, a Value is merely a token to a quad or a node that the backing store itself understands, and the base iterators pass around.

For example, in a very traditional, graphd-style graph, these are int64s (guids of the primitives). In a very direct sort of graph, these could be pointers to structs, or merely quads, or whatever works best for the backing store.

These must be comparable, or implement a Keyer interface so that they may be stored in maps.

func ToKey 

func ToKey(v Value) Value

ToKey prepares Value to be stored inside maps, calling Key() if necessary.

Source Files

View all Source files

Directories

Path Synopsis
b
Package b implements a B+tree.
 Package b implements a B+tree.
Package proto is a generated protocol buffer package.
 Package proto is a generated protocol buffer package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.