Structured1 data in the form of vectors, tuples, sets, relations etc is supported.
A partial representation of the lattice of structured types is given in figure 2. The crucial principle applied in achieving parallelism is the provision of higher order functions or functionals which allow lower level functions to applied to all elements of structured values. The meanings of these higher order functions are discussed in section . The higher order functions in the S of all structured types are in addition to what they inherit from universal: { Image / apply cardinality } For all structured types the implementation provides a method applytomembers that applies a procedure to each element of the structured type. This iterator can then be used to implement operations like reduce in a type independent way. At the level of tstructured the iterator is defined as an abstract method that is to be overridden by lower level methods.
Operator | Type | Explanation
z¬° / x | ((AnyÄAny ®Any)ÄStructured ®Any) |
2inif x = a,b,c are
some structured collection and °
a dyadic operator z = ((a°b)°c)
|
z¬ F Image x | ((Any®Any)ÄStructured ®Structured) |
2in
e.g. F Image [ a,b,c ]® [ F a, F b , F c ] see
|
z¬ # x | ( Struct®Number) | z is the cardinality of x
| |
package strathclyde.cs.relational.structured; import strathclyde.cs.relational.*; import strathclyde.cs.relational.operators.*; import java.util.Enumeration; public abstract class Structured implements Universal { public abstract int arity(); public abstract float cardinality(); public abstract Structured image(Moperator op);form image of set under operator
public Universal reduce(Doperator op)reduce the set using a dyadic operator
{} public int hashCode()
Hash code formed for structure S with n elements { S_1, S_2,... S_n} is given by HS(n) where
|
|
{} public Universal concat(Universal b){defined as + for completeness
} public abstract Enumeration members(); }
Tuples 2 are structured values whose components may not be of the same type.
package strathclyde.cs.relational.structured; import strathclyde.cs.relational.operators.*; import strathclyde.cs.relational.*; import strathclyde.cs.relational.atomic.*; import java.util.Enumeration; class tupit implements Enumeration{ int i; Tuple t; public boolean hasMoreElements(){} public Object nextElement(){} public tupit(Tuple t1){} } public class Tuple extends Structured implements Subscriptable { public Universal field[]; // ------------ Generators public Tuple(int n){} public Tuple(Universal u[]) {} public Tuple(String s[])A constructor to form a tuple from a vector of strings the individual strings must either be numbers or else they are treated as uninterpreted text strings.
{} private static String[] split(String s,char delim)function to split a string s into a vector of strings using a delimiter character
{} public Tuple(String s, char delim)A constructor that splits a string using the delimiter into fields and then builds a tuple. Suitalble for parsing comma or tab separated relational database files.
{} // ------------------------ from structured public float cardinality(){} public Enumeration members(){}Used to implement reduce and Image
public Structured image(Moperator op) {}
|
|
|
Subscription can bein either by numbers or tuples.
// ---------------------- from subscriptable public Universal subscript(int I)useful for call within java when one knows the fields that one is to subscript.
{} public Universal subscript(Universal i)
This is useful within the K interpreter to allow an arbitrary number or tuple to be used for subscription. Numbers are rounded to integers before subscription. Uses the previous function to do its dirty work.
{} // ---------------------- from Universal
|
public Universal concat(Universal b ) {}
Thus
|
We can have tuples containing tuples
|
|
public Universal minus(Universal b ) {} public Universal plus(Universal b ) {} public Universal times(Universal b ) {} public Universal divide(Universal b ) {} public boolean equals(Object b )Equal if have same number of fields and corresponding ones are equal
{} public boolean lessthan(Universal b )Tuple a \lt b follows string comparison rules
{} //******************************************** public Universal max (Universal b){} public Universal min (Universal b){} //********************************************* public int arity(){}Return number of fields in the tuple
public String toString()Return the fields comma separated and with the whole square bracketed
{} }
A set follows the normal semantics of set theory. It provides the base class for relations.
Operator | Type | Explanation
|
a < b | ( SetÄSet ® B) | Returns 1 if a is proper subset of
b
|
| ({ a } < {b, c })Þ (a = b)or(a = c)
|
| b ¹ a,{ a } < { b } = false
|
|
?A | (Set®Any) | Choice, returns a random member of set.
|
| (?A) Î A
|
| a = b | ( SetÄSet ® B) | Returns 1 if a equalsb
|
| z¬ a + b (SetÄ Set ® Set) | z is the union
a and b
|
| {a}+{ b} = { a, b }
|
z¬ a - b | (SetÄ Set ® Set) | z is the set
difference of a and b
|
| (x + y)-y = x-y
|
| {a,b }- {a} = {b }
|
z¬ a ×b | (SetÄ Set ® Set) | z is the
intersection of a and b
|
| ({a}×{a}) = {a}
|
| x×(y×z) = (x ×y)×z
|
| ({a}×{b}) = ({b}×{a})
|
z¬ a ¸b | (SetÄ Set ® Set) | z is the quotient
of
a and b
|
| thus a = b ×z
|
z¬ Øa | ( Set® Set) | forms the complement
|
x ·a | (AtomÄ Set ® Set) | set insertion
|
| (a ·{a} ) = {a}
|
| (a ·{} ) = {a}
|
| (°·x) = x
|
| (a ·{b} ) = b ·{a}
|
x Î a | (AtomÄ Set ® B) | tests membership
|
| x Î (x ·y) = true
|
A|f | (SetÄ(Any®B) ®Set) | selection
|
| A|f = {a|a Î A, f(a)}
|
|
| z¬ || x ( Set®R) | z is the cardinality of x
| |
package strathclyde.cs.relational.structured; import strathclyde.cs.relational.operators.*; import strathclyde.cs.relational.*; import java.util.Enumeration; public abstract class Set extends Structured { public static final Set EMPTYSET=new HashSet(); protected float card; public String toString()Returns a comma separted string of elements bracketed thus { } .
{} public Set join(Doperator comb,Doperator sim, Set b)join set b using combining operator comb and similarity operator sim
{} public float cardinality(){} public Set select(Moperator op) {} public int arity(){} public abstract boolean hasmember(Universal b);abstract set membership
public abstract void addmember(Universal b);adds a new member
public abstract void submember(Universal b);removes a member
public abstract Set EmptySet();creates an empty set of the same concrete type as this
public boolean lessthan(Universal b) {} public Universal min(Universal b){} public Universal max(Universal b){} public Structured image(Moperator op)create image under operator
{} public Universal plus(Universal b) {} public Universal minus(Universal b) /** Set difference */ {} public Universal divide(Universal b) {} public Universal times(Universal b)set intersection
{} public Universal choice()delivers a random element
{} }
HashSet - based on Java Dictionaries 4 This implementation is a direct translation of the java hashtable type into a set. Individual members are indexed on their hash codes. The implementation may be relatively innefficient in terms of storage space as the data items appear both in the key and the value fields of the hashtable.
package strathclyde.cs.relational.structured; import java.util.Enumeration; import java.util.Hashtable; import strathclyde.cs.relational.operators.*; import strathclyde.cs.relational.*; public class HashSet extends Set { private Hashtable tab; public HashSet(){}; public Set EmptySet(){} public Enumeration members(){} public boolean hasmember(Universal b){} public void addmember(Universal b) {} public void submember(Universal b) {} }
A Relation is a set all of whose elements are tuples, all of which are of the same arity and type. It inherits all of its operations other than projection and join from sets. A weighted relation similarly inherits all of its operations from weighted sets. We will treat weighted relations as the general form with unweighted relations being treated as the special case of a relation for which all tuples have equal weights.
Relations add to the set operations : Projection and Compression.
Let r be a relation over tuples of type [ t1,t2,t3,...,tn ] with ti being types, then if
| (1) |
| (2) |
| (3) |
| (4) |
Relations 5 are abstract types which extend sets by the addition of the projection operator. A
package strathclyde.cs.relational.structured; import strathclyde.cs.relational.*; import java.util.Enumeration; public abstract class Relation extends Set { public String toString() {} public Set project(Universal u)
Projection of a set r under tuple tis the image of r under subscription by t.
{} }
/* * * Hashrelation * Part of Mbase implemented in Java Author Paul Cockshott Started Aug 1997 Copyright (c) University of strathclyde */ package strathclyde.cs.relational.structured; import strathclyde.cs.relational.*; import java.util.Enumeration; import java.util.Hashtable; public class Hashrelation extends Relation { private Hashtable tab; private Tuple primarykey; private boolean hasprimarykey; // constructors -------------------- public Hashrelation(){}; public Hashrelation (Tuple keys){} // methods --------------------------- public Set EmptySet(){} public Enumeration members(){} public boolean hasmember(Universal b){} public void addmember(Universal b) {} public void submember(Universal b) {} }
1 Part of Mbase implemented in Java Author Paul Cockshott Started Aug 1997 Copyright (c) University of Strathclyde
2 Part of Mbase implemented in Java Author Paul Cockshott Started Aug 1997 Copyright (c) University of strathclyde
3 ** Set* Part of Mbase implemented in JavaAuthor Paul CockshottStarted Aug 1997Copyright (c) University of strathclyde
4 Part of Mbase implemented in Java Author Paul Cockshott Started Aug 1997 Copyright (c) University of strathclyde
5 Part of Mbase implemented in Java Author Paul Cockshott Started Aug 1997 Copyright (c) University of strathclyde