Entity hierarchy for the STREAM system

There are a number of components in the implementation of our system: operators implement relational algebra operations such as joins and projections, queues hold tuples between operators, and synopses materialize collections of tuples. Each of these is a subclass of a generic Entity class. Each entity has a table of attribute-values pairs called its Control Table (CT for short), and each entity exports an interface to query and update its CT.

This file is automatically generated from the entity-descriptors.xml file used by the system to construct entities.

entity (abstract)

Extends

Parameters

Name	Data Type	Description
publishes-state	string	Does this entity publish its state to the state stream? To avoid a feedback loop, entities should not publish state to the state stream if they are themselves part of a query which contains the state stream in its FROM clause. Anything but "no" means "yes".
comments	string	A space for any comments the developer (or compiler) has about the entity. Ignored by the system.
monitor	integer	Should this entity publish monitoring properties to the EntityUpdate stream?
query	integer	The ID of the query (if any) that this entity is associated with.

Abstract supertype of all entity types.

schema

Extends

entity

Parameters

Name	Data Type	Description
column-type	string array	type of the column - one of "INTEGER", "FLOAT", "BYTE", "CHAR"
column-len	integer array	length of column - This is required only if column is of type "CHAR"
column-count	integer	The number of columns in this schema
catalog-description	string	A human-readable version of the schema

A schema describes the format of data received from an input stream.

queue (abstract)

Extends

entity

Parameters

Name	Data Type	Description
schema	schema	The schema for tuples in this queue.
tuple-flow	integer	Used by the rate of tuple flow monitor

Queues are used to pass tuples between operators.

object-queue (abstract)

Extends

queue

Parameters

Name

Data Type

Description

Abstract supertype of all arbitrary-sized-object queue types. Note that this queue does not support the StrTuple enqueue/dequeue interface.

var-len-obj-queue

Extends

object-queue

Parameters

Name

Data Type

Description

Object queues that can be used to pass arbitrary variable size objects between operators. The queue is implemented as a single page grabbed from the memory manager. Note that this queue does not support the StrTuple enqueue/dequeue interface.

interface-output-queue

Extends

object-queue

Parameters

Name

Data Type

Description

Object queue used by the programmable interface to get the results The operator InterfaceOutputOperator writes to it

fixed-len-obj-queue

Extends

object-queue

Parameters

Name	Data Type	Description
object-size	integer	The (fixed) size of objects that are transferred in this queue.

Object queues that can be used to pass arbitrary fixed size objects between operators. The queue is implemented as a single page grabbed from the memory manager. Note that this queue does not support the StrTuple enqueue/dequeue interface.

stream-queue

Extends

fixed-len-obj-queue

Parameters

Name	Data Type	Description
stream-name	string	The name of the stream handled by this stream queue.

A queue that is used to receive the raw output of a stream. Tuples from the network manager are added copied into a stream queue for that stream.

simple-queue

Extends

queue

Parameters

Name	Data Type	Description
memory	integer	The number of tuples that can be stored at one time in this queue.

A simple implementation of a queue. Uses an array in the heap to store contents currently. We will make the implementation page-based soon. Not thread safe.

multiplier-queue

Extends

simple-queue

Parameters

Name	Data Type	Description
stream-name	string	The name of the stream handled by this multiplier queue.
source	entity	The relation-shepherd or stream-shepherd providing tuples to this queue

Wraps a simple queue. Does not add any functionality to simple queues. Multiplier queues are the source of tuple references (aka StrTuples), and not the actual tuples, from the Stream Shepherd.

synopsis (abstract)

Extends

entity

Parameters

Name

Data Type

Description

Synopses store intermediate data generated executing the query plan.

tuple-synopsis (abstract)

Extends

synopsis

Parameters

Name	Data Type	Description
schema	schema	The schema for tuples in this synopsis

Interface for all synopses which are bags of tuples.

unmaterialized-synopsis

Extends

tuple-synopsis

Parameters

Name

Data Type

Description

A tuple-synopsis that does not materialize itself. It simply does allocate memory for the tuple data so that the tuple can exist in queues, but does not keep a reference to the page or any state regarding its content. As a result, all operations other than insertTuple() are no-ops.

shared-tuple-synopsis-store (abstract)

Extends

tuple-synopsis

Parameters

Name

Data Type

Description

Shared relational store.

shared-window-synopsis-store

Extends

tuple-synopsis

Parameters

Name

Data Type

Description

Shared relational store.

shared-rand-synopsis-store

Extends

tuple-synopsis

Parameters

Name

Data Type

Description

Shared store for multiple time-based, tuple-based, and now windows.

shared-time-synopsis-stub

Extends

tuple-synopsis

Parameters

Name	Data Type	Description
store	shared-window-synopsis-store	The shared store.
owner	string	"true" if this stub is the owner, "false" otherwise

Stub to access shared store for multiple time-based, tuple-based, and now windows. Each stub corresponds to a specific window.

shared-tuple-synopsis-stub

Extends

tuple-synopsis

Parameters

Name	Data Type	Description
store	shared-tuple-synopsis-store	The shared store.
owner	string	"true" if this stub is the owner, "false" otherwise

Stub to access shared relational store, including shared window stores.

partition-synopsis-store

Extends

tuple-synopsis

Parameters

Name	Data Type	Description
partition-by	string	The columns to partition this synopsis by, each in the form "[StreamID:offset:type:length]" where type is one of i=INTEGER, f=FLOAT, c=CHAR

Shared partitioned synopsis (shared in the sense that it has a writer and multiple readers - not multiple partitioned window specifications)

partition-synopsis-stub

Extends

tuple-synopsis

Parameters

Name	Data Type	Description
store	shared-tuple-synopsis-store	The shared store.
owner	string	"true" if this stub is the owner, "false" otherwise

Stub for access shared partition store

partition-wrapper

Extends

tuple-synopsis

Parameters

Name	Data Type	Description
store	shared-tuple-synopsis-store	The shared store.
owner	string	"true" if this stub is the owner, "false" otherwise

Stub for access shared partition store

propeller (abstract)

Extends

entity

Parameters

Name	Data Type	Description
child-propeller	propeller	The child propeller which will be invoked after this propeller is invoked.

Abstract supertype of all propeller types.

join-propeller

Extends

propeller

Parameters

Name	Data Type	Description
stream-num	integer	The index of the stream/queue corresponding to the local synopsis.
predicate	string	The predicate is a single predicate representing a join condition and is parsed by the propeller. A conjunction of join predicates is registered by using this attribute multiple times.
store	tuple-synopsis	The synopsis store to access each input relation.
stub	tuple-synopsis	The synopsis stub to access each synopsis store.
schema	schema
selectivity-estimated-predicate	string	We estimate the selectivity of this predicate at run-time via sampling. The predicate is a single predicate representing a join condition and is parsed by the propeller.

Joins incoming tuples with a local synopsis.

output-propeller

Extends

propeller

Parameters

Name	Data Type	Description
input-schema	schema array	An array of schemas, one for each of the inputs to the propeller join.
numstreams	integer	Number of input streams.
output-store	tuple-synopsis	The synopsis store where the output relation is materialized.
output-queue	queue

Outputs the result of an n-way join into its output queue.

operator (abstract)

Extends

entity

Parameters

Name

Data Type

Description

Abstract supertype of all operator types.

unary-operator (abstract)

Extends

operator

Parameters

Name	Data Type	Description
input-queue	queue	The queue that this operator reads tuples from
output-queue	queue	The queue where this queue sends its output

An operator with exactly one input and one output

binary-operator (abstract)

Extends

operator

Parameters

Name	Data Type	Description
left-input-queue	queue	The first queue that this operator reads tuples from
right-input-queue	queue	The second queue that this operator reads tuples from
output-queue	queue	The queue where this queue sends its output

An operator with exactly two inputs and one output

terminal-operator (abstract)

Extends

operator

Parameters

Name	Data Type	Description
cql	string	The CQL for the query that generated this terminal operator
input-queue	queue	The queue that this operator reads tuples from

Terminal operators sit at the top of query plans and have an input, but no outputs within the system.

seq-window

Extends

unary-operator

Parameters

Name	Data Type	Description
part-store	synopsis array	The partition stores used.
output-queue	queue array	An array of output queues, one for each window specification.
shared-store	synopsis	The shared store used.
type	string	Used only when creating a new window: the type of the new window
size	integer	Used only when creating a new window: the size of the new window
window-output-queue	queue	Used only when creating a new window: the output queue for tuples in the new window
partition-by	string	if this is a PARTITION window, the columns to partition by

A sequential window operator implements one or more time or tuple-based windows. You can register new time or tuple-based windows dynamically with this operator. To register a new window you need to specify: 1. the window type in ROWS (tuple), RANGE (time), NOW (now) (done using the "type" attribute) 2. the window size (done using the "size" attribute): - number of tuples for ROWS - number of seconds for RANGE 3. the ouptut queue for the +/- tuples in the window (done using the "window-output-queue" attribute) The type, size, and window-output-queue attributes must be in this order in the XML fragment describing a new window to be added to the sequential window operator.

shared-rel-op

Extends

operator

Parameters

Name	Data Type	Description
output-queue	queue array	An array of output queues, one for each operator sharing this relation.
shared-store	synopsis	The shared store used.
relation-output-queue	queue	The output queue registered dynamically for tuples for a client operator.
input-queue	stream-queue	The input queue from the Network Manager.

This operator materializes a relation that is streamed to it as input. The relation can be shared among multiple client operators, each of which registers a queue with this operator at run-time. This class is the relational equivalent of the SeqWindow operator.

printer

Extends

terminal-operator

Parameters

Name

Data Type

Description

A printer operator writes its tuples to standard output -- for testing purposes only.

interface-output

Extends

operator

Parameters

Name	Data Type	Description
input-queue	queue
output-queue	object-queue

This output operator is used by the programmable interface to the DSMS.

stream-glue

Extends

unary-operator

Parameters

Name	Data Type	Description
cqlview-stream-name	string	Name of the derived stream.

Connects the output from a stream CQLVIEW to the input of a shared window operator. This operator simply forwards each input tuple to the input queue of the shared window operator for that (derived) stream. The derived stream has to be explicitly registered before the CQLVIEW is registered.

rel-glue

Extends

unary-operator

Parameters

Name	Data Type	Description
cqlview-relation-name	string	Name of the derived relation.

Connects the output from a relational CQLVIEW to the input of a shared relation operator. This operator simply forwards each input tuple to the input queue of the shared relation operator for that (derived) relation. The derived relation has to be explicitly registered before the CQLVIEW is registered.

output

Extends

terminal-operator

Parameters

Name	Data Type	Description
hostname	string	Hostname where the client is listening.
port	integer	Port where the client is listening.
column-names	string	The column names for the client to display. The list should be comma-delimited, such as "R.name,R.num,S.name,S.num". This is an optional property.

An output operator sends tuples to a client over the network.

plan-shepherd

Extends

operator

Parameters

Name	Data Type	Description
tuple-size	integer	The (fixed) size of tuples in the underlying stream.
input-queue	stream-queue

The Plan Shepherd operator reads tuples from the "QueryPlan" stream which it gets from the StreamQueue for the "QueryPlan" stream. These tuples represent query plans. The plan shepherd enters these plans into the global query network.

command-shepherd

Extends

operator

Parameters

Name	Data Type	Description
input-queue	stream-queue

One stop shop for commands sent to the DSMS.

stream-shepherd

Extends

operator

Parameters

Name	Data Type	Description
output-queue	queue array
tuple-size	integer	The (fixed) size of tuples in the underlying stream.
add-multiplier-queue	queue	Add the specified queue to the operator's output queue set.
remove-multiplier-queue	queue	Remove the specified queue from the operator's output queue set.
input-queue	stream-queue

The Stream Shepherd operator for a stream S reads tuples of S from the StreamQueue of S, stores each tuple in a synopsis, creates a reference (StrTuple) to the tuple, and copies the reference into each of the output queues.

relation-shepherd

Extends

operator

Parameters

Name	Data Type	Description
output-queue	queue array
tuple-size	integer	The (fixed) size of tuples in the underlying stream.
add-multiplier-queue	queue	Add the specified queue to the operator's output queue set.
remove-multiplier-queue	queue	Remove the specified queue from the operator's output queue set.
input-queue	stream-queue

The Relation Shepherd operator The relational dual of stream-shepherd. for a relation R reads tuples of R from the StreamQueue of R, stores each tuple in a synopsis, creates a reference (StrTuple) to the tuple, and copies the reference into each of the output queues.

select

Extends

unary-operator

Parameters

Name	Data Type	Description
filter-cond	string array	A single predicate representing a filter condition.
predicate	string	The predicate is a SQL-style condition which is parsed by the operator.

Outputs a subset of its input tuples based on a filter predicate.

project

Extends

unary-operator

Parameters

Name	Data Type	Description
project-list	string	A list of attributes to project, each in the form "[StreamID:offset:type:length]" where type is one of i=INTEGER, f=FLOAT, c=CHAR

Implements projection.

binary-join

Extends

binary-operator

Parameters

Name	Data Type	Description
synopsis-store	tuple-synopsis array	The synopsis store to access each input relation. Note: the order of the synopses must exactly match the order of the queues.
join-cond	string array	A single predicate representing a join condition.
predicate	string	The predicate is a single predicate representing a join condition and is parsed by the operator. A conjunction of join predicates is registered by using this attribute multiple times.
output-store	tuple-synopsis	The join operator puts its output tuples into this relational synopsis.
join-selectivity	integer	Join selectivity

An operator which performs a join over two streams or relations.

n-way-propeller-join

Extends

operator

Parameters

Name	Data Type	Description
synopsis-store	tuple-synopsis array	The synopsis store to access each input relation. Note: the order of the synopses must exactly match the order of the queues.
synopsis-stub	tuple-synopsis array	The synopsis stub to access each input synopsis store.
input-queue	queue array	The input queues.
propeller	propeller array	One propeller per input queue to handle tuples that arrive in that queue.
numstreams	integer	Number of input streams.
output-queue	queue
output-propeller	propeller
runtime-profiling	integer	Set to true is we want to use run-time profiling to estimate, e.g., the selectivity of join predicates. Has to be turned on explicitly. False (i.e., 0) by default.
profiling-startup-interval	integer	To avoid start-up descrepancies during profiling, we can set the "profiling-startup-interval" to some non-zero. This setting will ensure that profiling will be started only after "profiling-startup-interval" tuples have been seen since the "runtime-profiling" was set to true. Default value is 1000 which will usually be much smaller than the window sizes.
selectivity-sampling-interval	integer	The default interval in number of tuples at which sampling must be done for estimating join selectivity. Ideally we would want to vary the sampling interval dynamically, on a per-stream basis, etc.
arrival-rate-sampling-interval	integer	The default interval in number of tuples at which sampling must be done for estimating the arrival rate. Ideally we would want to vary the sampling interval dynamically, on a per-stream basis, etc.
sample-window-size	integer	The last "sample-window-size" samples are stored.
profile-output-queue	queue	The collected statistics are output in this queue. The Optimizer is the consumer of this queue.

An n-way symmetric join.

antisemijoin

Extends

binary-operator

Parameters

Name	Data Type	Description
synopsis-store	tuple-synopsis array	The synopsis store to access each input relation. Note: the order of the synopses must exactly match the order of the queues.
join-cond	string array	A single predicate representing a join condition.
predicate	string	The predicate is a single predicate representing a join condition and is parsed by the operator. A conjunction of join predicates is registered by using this attribute multiple times.

An anti-semijoin operator

union

Extends

binary-operator

Parameters

Name

Data Type

Description

An implementation of a bag union

plan-shepherd

Extends

operator

Parameters

Name	Data Type	Description
input-queue	queue
tuple-size	integer

Processes plans that arrive in the "QueryPlan" stream.

command-shepherd

Extends

operator

Parameters

Name	Data Type	Description
input-queue	queue

Processes commands that arrive in the "command-stream" stream.

aggregate

Extends

unary-operator

Parameters

Name	Data Type	Description
aggregate-list	string	A list of columns (in "[StreamID:offset:type:length]" format) that are aggregated by this operator.
aggregate-ops	string	A list of aggregation operations over the aggregate-list columns, where 1=AVG, 2=MIN, 3=MAX, 4=COUNT, 5=SUM
group-by	string	A list of columns that are used to group tuples
input-store	tuple-synopsis	The synopsis where input is stored (if necessary)
output-store	tuple-synopsis	The synopsis where output from this operator is stored.

Implements grouped aggregation.

duplicate-eliminate

Extends

unary-operator

Parameters

Name

Data Type

Description

Duplicate elimination operator.

x-stream (abstract)

Extends

unary-operator

Parameters

Name

Data Type

Description

Parent of i-stream, r-stream, and d-stream

i-stream

Extends

x-stream

Parameters

Name

Data Type

Description

Implements ISTREAM semantics. Sends inserts while dropping deletes.

r-stream

Extends

x-stream

Parameters

Name

Data Type

Description

Implements RSTREAM semantics. Sends snapshot of its relation at every instant.

d-stream

Extends

x-stream

Parameters

Name

Data Type

Description

Implements DSTREAM semantics. Sends deletes while dropping inserts.

relation-materializer

Extends

unary-operator

Parameters

Name	Data Type	Description
shared-store	synopsis	The synopsis where tuples of the materialization are stored.

Materializes the relation that is specified by tuples read from its input queue.