Since the 1980s the 8086 architecture has dominated micro-processors and so too has the relational model. The x86 series has papered over the cracks with larger and larger chips adding huge caches and requiring smarter compilers, with the relational model seeing ever larger RDBMSs systems and ORMs.
Even with an ORM like Hibernate in place, to create a working data driven solution is cumbersome. We must define a database schema, along the way explicitly defining the bits and bytes of parent/child relationships, then an XML mapping file and finally plain old objects. As new features are added all of these definitions must be kept in synch.
For say a basic web store we may only require a few tables, say products, categories, orders and customers. But what if you wanted to extend the web store to have features like the online retailer Amazon, e.g. multiple sellers, recommendations, etc.?
Answer: serious table and relationship proliferation.
Enter an alternative model: the Associative model of data, a dynamic model where data is defined simply as items and links:
/// Associative data value
type Value =
/// Item value
| Item of string
/// Link of source value, verb and target value
| Link of Value * string * Value
The following is a minimal implementation of an Associative repository using F#:
/// Naive Associative Model implementation
type Repository () =
let mutable items = []
let mutable links = []
let invalidOp s = new System.InvalidOperationException(s) |> raise
let obtainItem value =
let valueOf = function Item v -> v | Link _ -> invalidOp ""
match items |> List.tryFind (valueOf >> (=) value) with
| Some item -> item
| None ->
let item = Item(value)
items <- item :: items
item
let createLink (source,verb,target) =
let link = Link(source,verb,target)
links <- link :: links
link
let matchLink f = function
| Link(s,v,t) as link -> f (s,v,t)
| Item _ -> invalidOp ""
let filterLinks f = links |> List.filter (matchLink f)
let chooseLinks f = links |> List.choose (matchLink f)
let pickLink f = links |> List.pick (matchLink f)
let rec toString = function
| Item value -> value
| Link (s,v,t) -> toString s + " " + v + " " + toString t
let rec createEntity (source:Value) =
{ new IEntity with
member this.Add (verb,target) =
createEntity(createLink(source,verb,obtainItem target))
member this.Value verb =
fun (s,v,t) -> if s = source && v = verb then Some(t) else None
|> pickLink |> createEntity
member this.Links verb =
filterLinks (fun (s,v,t) -> s = source && v = verb)
|> Seq.map createEntity
member this.Values' verb =
fun (s,v,t) -> if t = source && v = verb then Some(s) else None
|> chooseLinks |> Seq.map createEntity
member this.ToString() = toString source
}
/// Gets or creates item
member this.ObtainItem (value:string) =
createEntity(obtainItem value)
/// Encapsulates associative data entity
and IEntity =
/// Adds link with specified verb and target
abstract Add : string * string -> IEntity
/// Returns all links from this entity matching the specified verb
abstract Links : string -> IEntity seq
/// Returns first value matching the specified verb
abstract Value : string -> IEntity
/// Returns all values to this entity matching the specified verb
abstract Values' : string -> IEntity seq
/// Returns a string that represents this instance
abstract ToString : unit -> string
Add some operator overloads to help prettify the code:
// Dynamic lookup operator oveload
let (?) (source:IEntity) (verb:string) = source.Value(verb)
// Addition operator overload
let (+) (source:IEntity) (verb:string,target:string) = source.Add(verb, target)
Now we can build the flight example from Wikipedia:
let r = Repository()
let flight = r.ObtainItem("Flight BA111")
let trip =
flight +
("arrives at", "London Heathrow") +
("on","Dec 12") +
("at","10:25")
do System.Diagnostics.Debug.WriteLine trip
Or a fragment of a web store:
open System.Diagnostics
do let category1 = "F# Books"
let product1 = "Functional Programming with examples in F# and C#"
let item1 = r.ObtainItem(product1)
item1 + ("author","Tomas Petricek") |> ignore
item1 + ("sold by","Amazon") + ("price","27.99") |> ignore
item1 + ("sold by","Paperback World") + ("price", "25.99") |> ignore
item1 + ("category", category1) |> ignore
let product2 = "Expert F#"
let item2 = r.ObtainItem(product2)
item2 + ("author", "Don Syme") |> ignore
item2 + ("sold by","Amazon") + ("price","27.99") |> ignore
item2 + ("sold by","Hardback World") + ("price","27.99") |> ignore
item2 + ("category", category1) |> ignore
let user1 = r.ObtainItem("Phil")
user1 + ("viewed", product1) |> ignore
user1 + ("viewed", product2) |> ignore
let ShowItemInfo (item:IEntity) =
item.Links("sold by") |> Seq.iter (fun seller ->
Debug.WriteLine seller
Debug.WriteLine seller?price
)
ShowItemInfo item1
ShowItemInfo item2
let amazon = r.ObtainItem("Amazon")
amazon.Values'("sold by") |> Seq.iter Debug.WriteLine
To serialize the data to XML simply add the following members to the repository:
/// Writes data to specified XmlWriter instance
member this.WriteTo (writer:XmlWriter) =
let rec traverse = function
| Item value as item ->
writer.WriteStartElement("Item")
writer.WriteAttributeString("Value", value)
filterLinks (fun (s,_,_) -> s = item)
|> Seq.iter traverse
writer.WriteEndElement()
| Link(source,verb,target) as link ->
writer.WriteStartElement("Link")
writer.WriteAttributeString("Verb",verb)
writer.WriteAttributeString("Target",toString target)
filterLinks (fun (s,_,_) -> s = link)
|> Seq.iter traverse
writer.WriteEndElement()
writer.WriteStartElement("Repository")
items |> Seq.iter traverse
writer.WriteEndElement()
/// Reads data from specified XmlReader instance
member this.ReadFrom (reader:XmlReader) =
reader.ReadStartElement("Repository")
let mutable xs = []
while reader.Read() do
match reader.NodeType, reader.Name with
| XmlNodeType.Element, "Item" ->
let value = reader.GetAttribute("Value")
let item = obtainItem(value)
xs <- item :: xs
| XmlNodeType.Element, "Link" ->
let source = xs.Head
let verb = reader.GetAttribute("Verb")
let target = reader.GetAttribute("Target")
let link = createLink(source,verb,obtainItem target)
xs <- link :: xs
| XmlNodeType.EndElement, "Item"
| XmlNodeType.EndElement, "Link" ->
xs <- xs.Tail
| _ -> ()
done
The implementation presented is purely for interest; there are many improvements and optimizations that could be made for a production system.
Finally, a Java implementation of the Associative model exists called Sentences, and is free.
016cc208-a8d9-4bdf-85b5-bc985a3b4258|1|5.0