Column Databases Reach Slashdot

In a typically incorrect charactization of the issue Slashdot is covering column databases: Relational database pioneer says technology is obsolete via Are Relational Databases Obsolete?. A better way to explain it, is that column databases are designed to get around the current problems with modern computer architectures such as latency in memory and hard disks as well as achieving better CPU utilization (typically databases have very little parallelism).

While it's early days yet, column databases storing something like RDF may get faster than row-oriented SQL databases. I posted about column databases storing RDF previously.

"Vertica beats all row stores on the planet -- typically by a factor of 50," he wrote. "The only engines that come closer are other column stores, which Vertica typically beats by around a factor of 10."

And from the cited blog:

In addition, it provides built-in features appropriate to the needs of 2007 customers. These include:

o Linear scalability over a shared-nothing hardware grid
o Automatic high availability
o Automatic use of materialized views
o "No knobs" -- minimum DBA requirements

Seeing as though I've just been looking into this here are a few references:

• The End of an Architectural Era (It’s Time for a Complete Rewrite) One of the links from my previous post written by Michael Stonebraker and others. It provides a deeper explanation of column databases than in the above articles.


• Decomposition Storage Model the paper that started it all (from 1985). Section 2.5 is especially relevant as it mentions how to store directed graphs and parent-child relationships.


• Database Architecture Optimized for the New Bottleneck: Memory Access


• Monet: A Next-generation DBMS Kernel for Query-intensive Applications

Update: InfoQ and artima have also picked up on the story.
Update 2: While I'm normally pretty skeptical about most things, column databases have had their own fair share of problems in the past.

Perfect Storm (of Erlang)

It would be remiss of me not to keep track one of the other contenders for scalability. The first hint was a few days ago with, "CouchDB: Thinking beyond the RDBMS":

CouchDB on first look seems like the future of database without the weight that is SQL and write consistency.

It stores document in a flat space.

There are no schemas. But you do store (and retrieve) JSON objects. Cool kids rejoice.

And all this happens using Real REST (you know, the one with PUT, DELETE and no envelopes to hide stuff), so it doesn’t matter that CouchDB is implemented in Erlang. (In fact, Erlang is a feature)

CouchDB and for even cooler kids, there's a Ruby API too.

The other bit that adds to this is the RDF JSON specification or RDFON. The first specification doesn't support nesting which means only named blank nodes are supported - which I think is a bug - naming things, especially things that don't naturally have names, can be a pain. The second was criticized as being a diversion away from N3.

I'm for a way to make it easier for programmers and web browsers to have better access to RDF data. Whether there needs to be another format to describe RDF is a bit unclear though - although being able to store it in a scalable way, perform queries and update it through REST seems like a positive. JSON is in that fuzzy area between code and data with its own drawbacks (like security).

Just to keep the pro scale-out/Hadoop/MapReduce etc. architecture going here's a recent posting on the more general issue:

Functional programming paradigms, the map/reduce pattern, and to a lesser extent distributed and parallel processing in general are subjects not widely understood by most quasi-technical management. Further, the notion of commodity machines with guarenteed lack of reliability as a means of achieving high performance and high scalability is essentially counterintuitive. Even referring newcomers to what I regard as the seminal papers on these topics (the papers written by Ghemewat, Dean et al at Google, and yes I know it all started with LISP but my management wasn't even alive in the 1970s although I was :-)), people steeped in a long tradition of "shared everything" database architectures still don't quite get it. I spend considerable amounts of time in what amounts to management de-programming: No MySQL can't do this, and Oracle can't either, except with Oracle it will cost you a lot more to find that out.

Update: Dare corrects some mistakes made in the above posting about CouchDB. The way I read the original was it wasn't saying it was replacing relational databases just offering a better solution for certain kinds of problems. Where, "thinking beyond" is not being constrained by the expected features of a database.

Known Unknowns

Blank nodes for the lay person.

JRDF 0.5.0

As mentioned this version of JRDF supports a Resource interface, datatype support, persistence (via Berkeley DB), and Java 6. It does run under Java 5 but the RDF/XML writer now uses the StAX API, so it requires Woodstox or some other JSR 173 implementation.

A few things in the works such as an Elmo like API, Globalized nodes, and MSG support.

Sourceforge download.

Better Chess

Higher Games On the 10 year anniversary of Deep Blue beating Kasparov, some thought provoking suggestions:

It is interesting in this regard to contemplate the suggestion made by Bobby Fischer, who has proposed to restore the game of chess to its intended rational purity by requiring that the major pieces be randomly placed in the back row at the start of each game (randomly, but in mirror image for black and white, with a white-square bishop and a black-square bishop, and the king between the rooks). Fischer ­Random Chess would render the mountain of memorized openings almost entirely obsolete, for humans and machines alike, since they would come into play much less than 1 percent of the time. The chess player would be thrown back onto fundamental principles; one would have to do more of the hard design work in real time.

Fischer Random Chess, or Chess 960 removes one of the reasons that I've always disliked chess (as I never really could apply myself to remember openings).

Why isn't it just as nice--or nicer--to think that we human beings might succeed in designing and building brain­children that are even more wonderful than our biologically begotten children? The match between Kasparov and Deep Blue didn't settle any great metaphysical issue, but it certainly exposed the weakness in some widespread opinions. Many people still cling, white-­knuckled, to a brittle vision of our minds as mysterious immaterial souls, or--just as romantic--as the products of brains composed of ­wonder tissue engaged in irreducible non­computational (perhaps alchemical?) processes. They often seem to think that if our brains were in fact just protein machines, we couldn't be responsible, lovable, valuable persons.

Via wonderTissue.

Beautiful Engineering

One Bridge Doesn’t Fit All

American bridge engineering largely overlooks that efficiency, economy and elegance can be mutually reinforcing ideals. This is largely because engineers are not taught outstanding examples that express these ideals.

A 2000 report by the Federal Highway Administration indicated that an average of about 2,500 new bridges are completed each year; each could be an opportunity for better design. The best will be elegant and safe while being economical to build.

The key is to require that every bridge have one engineer who makes the conceptual design, understands construction and has a strong aesthetic motivation and personal attachment to the work. This will require not only a new ethos in professional practice, but also a new focus in the way engineers are educated, one modeled on the approach of those Swiss professors, Wilhelm Ritter and Pierre Lardy.

Via Bridges and code.

A Bunch of IntelliJ Goodness

I've been languishing without perhaps the best plugin of all time for IntelliJ. I mention it to everyone I work with and they said, hey I've come across this plugin that you might be interested in. And it's, ToggleTest. A simple plugin that lets you switch between tests and production code. Never let your hands leave the keyboard again.

Other plugins from the author include the best meta-plugin hot plugin and cruise watcher.

Result

The previous issue of IEEE is avaiable to Xplore subscribers. It is an issue dedicated to TDD and agile development.

Mock Objects: Find Out Who Your Friends Are highlights the oft discussed criticisms of test driven development including: breaking encapsulation, hard to read, increased code fragility and whether it is a valuable use of developer time. Of course, these differences can be resolved in a typical XP way:

My point is that plenty of well-written code is produced without relying on mocks or Tell, Don’t Ask. On the other hand, I also encounter plenty of TDD novices who produce poor code and poor tests. Can Steve and Nat’s approach consistently help novices write better code and tests? It could be. At this point, I remain open minded and am ready to pair-program with Steve or Nat to learn more.

The second article, is about the studied effect of TDD on the quality of code, TDD: The Art of Fearless Programming. Pretty much every study showed an increased effort (15-60%) and an increase in quality (5-267%). The ratio of effort to quality is 1:2 - so it seems to pay. Example definitions of quality were "reduction in defects" or "increase in functional tests passing". In general:

All researchers seem to agree that TDD encourages better task focus and test coverage. The mere fact of more tests doesn’t necessarily mean that software quality will be better, but the increased programmer attention to test design is nevertheless encouraging. If we view testing as sampling a very large population of potential behaviors, more tests mean a more thorough sample. To the extent that each test can find an important problem that none of the others can find, the tests are useful, especially if you can run them cheaply.

Via Mock Objects

Off to See the Wizard

Microsoft comes up with a quite elegant and well integrated language extension for relational and XML data. IBM fires back 2 years later with a wizard that auto-generates beans and Java code with embedded SQL. The article also makes assertions like:

The most popular way to objectize to programmatically access and manipulate relational data has been through special APIs and wrappers that provide one or more SQL statements written as text strings.

It does seem like it does give you some benefits when writing SQL but it's simply not LINQ.

Everything You Know is Wrong

• OWL can be, as the French would say, databasesque. Using OWL to implement database like integrity constraints.


• It's time to throw away your database (a paper describing the advantages of column databases) and replace it with something more flexible and scalable (using C-Store to store RDF). And column databases mean no NULLs. The problem isn't that your data is normalized it's that it's not normalized enough (also mentioned here).


• Following a question that I had earlier this year about where is the good code to learn from, I've read about 3/4 of Beautiful Code. And while I have a hard time finding C/C++ code beautiful it certainly covers some good examples of code and the process behind writing it (including Beautiful Tests, Beautiful Concurrency and MapReduce).


• Latency Moore's curse.


• Nova links to why what you thought about genes is wrong (I've actually heard this before but hadn't come across any articles).


• Scaling laws in Biology. Humans run on 100 watts or used to. Now we have cars etc. our power requirements are now 11,000 watts (making us the biggest creatures that have ever lived). And the magical number: 4.


• The Enemies of Reason is now on Google Video.

Can't wait until they find the Astronaut Helmet

Lego giant emerges from sea "Workers at a drinks stall rescued the 2.5-metre (8-foot) tall model with a yellow head and blue torso.

"We saw something bobbing about in the sea and we decided to take it out of the water," said a stall worker. "It was a life-sized Lego toy.""

Naming

Relatively recently, UniProt (a protein sequence database) announced they were moving away from LSIDs (which are URNs) to URIs. The cons of LSIDs seem to be outweighing the pros. More generally, there seems to be much discussion as to what is more appropriate and what can and cannot be done with URIs vs URNs. And even some of LSIDs proponents are saying that using them at the moment is not a good idea.

The form of a URN is: urn:lsid:ubio.org:namebank:11815 which can be resolved using: http://lsid.tdwg.org/summary/urn:lsid:ubio.org:namebank:11815. A couple of IBM articles describe it in more detail: "Build a life sciences collaboration network with LSID" and "LSID best practices". Part of the problem seems to be that the LSID needs a resolving service, much like a web service, to return the data for a given LSID. The URI on the other hand can just use a bit of content negotiation to return either RDF data or human readable HTML. It's not a well known feature that a web client can tell a web server what data it can accept. So a Semantic Web client would say "give me RDF" and a normal web client says "give me HTML".

An alternative is using an existing standard, such as THTTP, which shows how to turn a URN into a URL by providing a REST based service. Where, requesting a URL for the urn "urn:foo:12345-54321" it becomes an HTTP request "GET /uri-res/N2L?urn:foo:12345-54321 HTTP/1.0". This is a bit like the biordf.org approach of "http://bio2rdf.org/namespace:id". Having de-referencable URIs is part of the Banff Manifesto.

Creating GUIDs is an interesting problem in a distributed environment. One of the other life science groups compared Handle, DOI, LSID and PURL (persistent URLs).

The mentioning of the Handle System brought back ideas from previous digital library work and using URNs to name RDF graphs (which I later to discovered wasn't entirely novel).

Game Changer

Wag the dog

Arguing that EC2 has no intrinsic business value, is like arguing that an electrical grid or a telephone network has no intrinsic business value. Speculation: one reason business systems can't adapt is because the assumptions about what the business used to do, are embedded deep in the code. Very deep, not easy to pull out. And not just in the code but in the physical architecture the system is running on. Business "logic" is like bindweed - by the time you've pulled it out, you've ripped out half the garden as well.

So I missed lunch with a friend earlier this year because he was stuck in an Exchange upgrade. This was at the same time I was looking into Google's architecture and it struck me that there's no real upgrade process or data conversion process that needs hand holding for their architecture. It was at that point that I thought a lot of the jobs system administrators currently do will be greatly simplified or removed with the right software. The ratio of system administrators to servers at Google has to be much smaller (i.e. more servers to people) because they need so many more servers and there just aren't that many system administrators to look after software written in the usual way.

It came up again when I got roped into a meeting with a bunch of guys that administer several clusters. I was quite happy to be quiet but it was brought up that I was looking at cluster techniques. I explained about EC2 and how you can run a server for as little as 10 cents per instance hour and experiments for $2. I think it came as a bit of a shock to them - first the cheapness (obviously) and second the availability (basically its removing the gatekeeping to resources). The second benefit is something that really removes a lot of the politics - something not to be underestimated.

More Hadoop

A couple of days late, but the OSCON apparently had a focus on Hadoop:

The freedom to take your data away rather than controlling the rights to your source code might dominate the Web 3.0 meme. Hadoop! "I got a call from David Filo (co-founder of Yahoo!) last night saying Yahoo! is really behind this."

The main focus of the attention was the Doug Cutting and Eric Baldeschwieler talk.

The whole, shared nothing programming model is certainly infectious and it seems scarily appropriate for Semantic Web data (see some of the talk for more information). Yahoo's Hadoop research cluster is now apparently up to 2x1000 nodes.

Scale Out or Drop Out

I recently came across this study done by IBM using Nutch/Lucene to compare scale-up (a single, shared memory, fast server) vs scale-out (a cluster). It showed that for the type of work performed scale-out systems outperformed scale-up systems in terms of price and performance. The IEEE article about Google's architecture in late 2002, notes that Google was spending $278,000 for 88 dual CPU 2GHz Xenons, 2 GB of RAM and each having a 80 GB hard drive. In the IBM paper, $200,000 gets you 112 blades, quad processor with 8GB of memory each with a 73GB drive as well as a shared storage system.

This scale-out approach was also recently mentioned by Tim O'Reilly's, MySQL: The Twelve Days of Scaleout.

Scale-up x Scale-out: A Case Study using Nutch/Lucene

The Nutch/Lucene search framework includes a parallel indexing operation written using the MapReduce programming model [2]. MapReduce provides a convenient way of addressing an important (though limited) class of real-life commercial applications by hiding parallelism and fault-tolerance issues from the programmers, letting them focus on the problem domain.

The query engine part consists of one or more front-ends, and one or more back-ends. Each back-end is associated with a segment of the complete data set...The front-end collects the response from all the back-ends to produce a single list of the top
documents (typically 10 overall best matches).

We see that the peak performance of the scale out solution (BladeCenter) is approximately 4 times better.

Moving Around

• A better spreadsheet, Resolver "...data and formulae you enter into cells are actually turned into code."


• How to Publish Linked Data on the Web Share structured data on the web today.


• The joys of RDF/XML and it's inability to have literals in lists. A possible solution was suggested that would also allow literals as subjects.


• An RDF DB shootout complete with TestSuite. Hopefully, JRDF's use of BDB will have better results.


• An extension to SPARQL to support federated queries.


• Radar Networks Progress Update "We're on track for a invite only launch in the fall timeframe as planned...Several of the world's big media empires have started approaching me...They are interested in the potential of the Semantic Web for adding new capabilities to their content and new services for their audiences."


• Snoggle "...a graphical, SWRL-based ontology mapper to assist in the task of OWL ontology alignment. It allows users to visualize ontologies and then draw mappings from one to another on a graphical canvas."

MapReduce by the Hour

Running Hadoop MapReduce on Amazon EC2 and Amazon S3

Apache's Hadoop project aims to solve these problems by providing a framework for running large data processing applications on clusters of commodity hardware. Combined with Amazon EC2 for running the application, and Amazon S3 for storing the data, we can run large jobs very economically. This paper describes how to use Amazon Web Services and Hadoop to run an ad hoc analysis on a large collection of web access logs that otherwise would have cost a prohibitive amount in either time or money.

It took about 5 minutes to transfer the data (which was compressed - Hadoop can read compressed input data out of the box) from S3 to to HDFS, so the whole job took less than a hour. At $0.10 per instance-hour, this works out at only $2 for the whole job, plus S3 storage and transfer costs - that's external transfer costs, because remember transfers between EC2 and S3 are free.

SPASQL

SPASQL

FeDeRate [FED] provides a mapping between RDF queries and SQL queries over conventional relational databases. SPASQL provides similar functionality, but eliminates the query rewriting phase by parsing the SPARQL [SPARQL] directly in the database server. This approach is efficient, and allows applications linked to currently deployed MySQL client libraries to execute SPARQL queries and get the results back through the conventional MySQL protocol.

This looks like a nice, pragmatic approach to solving the legacy SQL data problem. There's some interesting discussion about the mismatch between UNION in SQL and SPARQL.

JRDF Development

I've started adding datatype support to JRDF. Nothing too flash at the moment, mainly to support the RDF/XML test cases and prompted by a similar piece of work that was completed by the people at KP Lab. They also implemented an Elmo like API (with lazy collections) and added a Resource interface (which adds methods on top of both Blank Nodes and URI References and is quite similar to Jena's Resource interface) which will be integrated soon.

An interesting aspect to the datatype support is of course semantically equal types like integer and long. In the current version of JRDF they wouldn't return equal. In Jena there is "sameValueAs" that returns true if they are semantically equal. In JRDF, I originally decided to use Comparable - but then the use in ordered maps may get confusing (although it would be similar to BigDecimal but it's the exception rather than the rule). Using Comparable in this way would also be different to the implementation of datatypes in Kowari/Mulgara. So I've kept the old behaviour and added an equivalent comparison operator that is a copy of Comparable but takes in semantic similarities.

The other thing that's been cleared up is the containers and collections - a lot of (90%) was redundant due to Generics and didn't need to be there anymore. However, I did come across, "The pseudo-typedef antipattern", which pretty much says that creating a StringList (that extends ArrayList) is an anti-pattern. In JRDF collections and containers are basically Lists or Maps restricted to object nodes. Which seems to fit the anti-pattern. However, for me it does add different behaviour over the standard collections and restricting it on type does seem to make sense. I'm willing to be convinced though.

I'm also aware of some of the more weird RDF/XML edge cases that don't look like they were ever implemented correctly in JRDF or Kowari/Mulgara (like turning rdf:li into numbers even if outside of collections). I don't think it's a big use case and no one has ever raised it as a bug as far as I know.

Update: It's been pointed out to me again that implementing comparable isn't flexible enough - I should've known better of course as it's been pointed out to me many times in the past and I've used it in the past the equivComparator is a bit dumb.

The Centre of Excellence

The Pmarca Guide to Big Companies, part 2: Retaining great people

Don't create a new group or organization within your company whose job is "innovation". This takes various forms, but it happens reasonably often when a big company gets into product trouble, and it's hugely damaging.

Here's why:

First, you send the terrible message to the rest of the organization that they're not supposed to innovate.

Second, you send the terrible message to the rest of the organization that you think they're the B team.

That's a one-two punch that will seriously screw things up.

Via Dare.

When You Get What You Want But Not What You Need

I was at the eResearch 2007 conference last week and it was quite good. Although, I must say that I'm very sick of "the long tail" and mashups being mentioned.

The keynotes were quite good and I'll mentioned three but the others and the talks I went to were very good too. I wish I had've written it up last week when it was more fresh in my mind - so some of my recollections maybe a little inaccurate.

David De Roure mentioned the reuse of workflows and that automation requires machine processable descriptions. He also mentioned the CombeChem project and Semantic Grids. He made some interesting comments such as grids are inherently semantic grids, that a little semantics go a long way (it's all about linked data) and that mashups are workflows. He mentioned the very successful Taverna project.

Phil Bourne gave a scenario of someone taking the bus, reviewing a paper, contacting their friends because it contradicts their current results and by the end of the bus trip having validated their approach and written a response to the author of the paper. He used the acronym IPOL (iPod plus Laptop) but surely the iPhone would've been closer to the mark.

His main idea is that publications aren't enough, that the experimental data has to also be saved, reviewed and made part of the academic process. As someone who runs one of the protein databases and an editor of a PLoS journal he's obviously seen the benefits of this approach. It also reminded me that ontologies in biology were cool before the Semantic Web came about (although most biology ontologies aren't very good (pdf)).

He mentioned the BioLit project which tries to integrate the workflow of papers, figures, data, and literature querying and creating a positive feedback loop for academic metadata. The idea of getting the source data behind graphs that are published is a much touted application of things like ontologies and RDF.

The last thing he mentioned was creating podcasts for papers published - they should give an overview of a paper that's more indepth than an abstract but more general than the entire paper. To achieve this they've setup the SciVee.tv site (still early days for that). That sounded quite interesting - I can imagine a video explaining the key figures and facts in a multimedia presentation would be very useful. I'm not sure though that most current researchers have those skills. If it is a lot more useful it may lead to a similar situation now, where papers published before the 1980s or so don't get cited or read because they aren't online. Maybe people who are used to YouTube won't read papers because they don't have an accompanying video, although it's probably not as distinct as the pre-digital papers. It seems much more likely that papers without the original experimental data will increasingly be ignored.

The last keynote I'll talk about was by Alex Szalay. I appreciated this one the most even though he did mention the long tail. He has previously written about the exponential increase in scientific data. He wrote it with Jim Gray and he was one of the people that helped in his search (his blog has more information about that too). There's now computational x - where x is any science including things like biology, physics and astronomy. One of the key effects of this much data is that the process of analysing data and then publishing your results is changing. It's more publish the data then do the analysis and publish the analysis.

He mentioned four different types of places where the power law (long tail) occurs: projects (few big ones, many small ones), data sizes (few multi-petabytes sources, many more 10s and 100s of terrabytes and vastly more smaller ones), value added or refereed products and users of data (a few users use a lot but the vaste majority use it a little).

The main thing I liked was that he said the processing of this data is fundamentally different than what it was before. It's too difficult to move the data about when its petabytes - it's easier to move the processing to the data. It was pointed out to me later that versioning the software that processed the data now becomes a very tiny fraction of the data kept but is more often than not overlooked.

The data captured by CCD is about to or has converged with the more traditional telescopes and that the data published and searchable now is only 2 years behind the best possible results. For most astronomers it's actually better to observe the universe from the data than to use an actual telescope.

Processing, memory and CCDs are all following Moore's Law but bandwidth is not. He mentioned an approach that's very much along the lines of the Hadoop/GFS - the code moves to the data not the other way around. He also listed things that are fairly well known now: no time to get it right from the top down, data processing and management becomes the key skill in the future, taking data from different sources is highly valuable, and build it and they will come is not enough you must provide a decent interface.

He mentioned two projects: Life Under Your Feet and Virtual Observatory. Both have huge data sets and rather cool user interfaces.

Google Culture

So a perspective of Google has been going around for a little while now. The story of when an interview gets widely distributed though is more interesting. It's not like Microsoft has anything to gain from distributing this information.

Via, "RE: Life at Google - The Microsoftie Perspective".

Squirt Towers

This gives me some of my life back. The weird thing is even though you finish it you still want to play one more game.

Moving Up

I really appreciate blogs sometimes. I started Al Gore's, "The Assault on Reason", before putting it down halfway because it was depressing (which was as bad as "Sicko" and "A Crude Awakening"). Lawrence Lessig on the other hand has decided to move from the copyright brick wall to the corruption brick wall.

In one of the handful of opportunities I had to watch Gore deliver his global warming Keynote, I recognized a link in the problem that he was describing and the work that I have been doing during this past decade. After talking about the basic inability of our political system to reckon the truth about global warming, Gore observed that this was really just part of a much bigger problem. That the real problem here was (what I will call a "corruption" of) the political process. That our government can't understand basic facts when strong interests have an interest in its misunderstanding.

The answer is a kind of corruption of the political process. Or better, a "corruption" of the political process. I don't mean corruption in the simple sense of bribery. I mean "corruption" in the sense that the system is so queered by the influence of money that it can't even get an issue as simple and clear as term extension right. Politicians are starved for the resources concentrated interests can provide. In the US, listening to money is the only way to secure reelection. And so an economy of influence bends public policy away from sense, always to dollars.

Scalability, Scalability, Scalability, Scalability

Dare Obasanjo has four recent postings on the recent Google Scalability Conference.

Google Scalability Conference Trip Report: MapReduce, BigTable, and Other Distributed System Abstractions for Handling Large Datasets:

The talk was about the three pillars of Google's data storage and processing platform; GFS, BigTable and MapReduce.

A developer only has to write their specific map and reduce operations for their data sets which could run as low as 25 - 50 lines of code while the MapReduce infrastructure deals with parallelizing the task and distributing it across different machines, handling machine failures and error conditions in the data, optimizations such as moving computation close to the data to reduce I/O bandwidth consumed, providing system monitoring and making the service scalable across hundreds to thousands of machines.

Currently, almost every major product at Google uses MapReduce in some way. There are 6000 MapReduce applications checked into the Google source tree with the hundreds of new applications that utilize it being written per month. To illustrate its ease of use, a graph of new MapReduce applications checked into the Google source tree over time shows that there is a spike every summer as interns show up and create a flood of new MapReduce applications that are then checked into the Google source tree.

Google Scalability Conference Trip Report: Using MapReduce on Large Geographic Datasets:

A common pattern across a lot of Google services is creating a lot of index files that point and loading them into memory to make lookups fast. This is also done by the Google Maps team which has to handle massive amounts of data (e.g. there are over a hundred million roads in North America).

Q: Where are intermediate results from map operations stored?
A: In BigTable or GFS

Google Scalability Conference Trip Report: Lessons in Building Scalable Systems:

The most important lesson the Google Talk team learned is that you have to measure the right things. Questions like "how many active users do you have" and "how many IM messages does the system carry a day" may be good for evaluating marketshare but are not good questions from an engineering perspective if one is trying to get insight into how the system is performing.

Specifically, the biggest strain on the system actually turns out to be displaying presence information.

Giving developers access to live servers (ideally public beta servers not main production servers) will encourage them to test and try out ideas quickly. It also gives them a sense of empowerement. Developers end up making their systems easier to deploy, configure, monitor, debug and maintain when they have a better idea of the end to end process.

And finally, Google Scalability Conference Trip Report: Scaling Google for Every User, which had some interesting ideas about search engine usage.

Update: links for 2007-07-06 includes links to the Google talk on MapReduce tasks on large datasets and other goodies (scalable b-trees, hashing, etc).

Update 2: Greg Linden has a much better list of videos and commentary.

DERI at Google

The Semantic Web at Google (I found the movie here).

Starting from the end, Stefan was asked about inferencing and relationships. He basically responded that linked data is more practical and immediately useful and that the affect of Description Logics has been over estimated.

The highlight for me was the demo on how to construct user interfaces automatically (from about 20 minutes in). The algorithms are described in more detail in, Extending faceted navigation for RDF data.

They also talked a little about how Ruby was a good language for Semantic Web applications and referenced, ActiveRDF: Object-Oriented Semantic Web Programming.

The applications and tools demoed: SIOC Project, Active RDF, JeromeDL (digital library), BrowseRDF (automatically generated, facted UI) and S3B (social semantic search and browsing).

The History of Trans and Walk

Paul recently started talking about the history of trans and walk in Kowari/Mulgara. I did a bit of searching in old Tucana emails and feature requests.

I also vaguely remember trying to create an abstract class for walk and the base transitive classes (like the Exhaustive and Direct transitive closure classes). And one of the feature requests also mentions the idea of "set depth" to reduce the recursion on unbounded traversal which would also be handy for the shortest path between two nodes.

Getting up to Speed With OWL 1.1

Bijan's "Two Interesting Quotes" really got me started on understanding the new features of OWL 1.1. The addition of the RBox (to ABox and TBox), using SROIQ instead of SHOIN, is the obvious one.

The second interesting quote was from, "Describing chemical functional groups in OWL-DL for the classification of chemical compounds" which gives some clear examples using the new features of OWL 1.1 including qualified cardinality, negation and property chains. The first two are analogous to: chemical has two bonds and chemical has exactly one bond.

Property chains are another interesting feature which is highlighted in the above paper, in "The OBO to OWL mapping, GO to OWL 1.1!" and in the first paper Bijan spoke about. In one way this is a bit disappointing because the OBO work replicates what we been doing in the BioMANTA project (I hate duplication in all its forms) - we based it on the Protégé plugin. Our relationships are quite simple, mainly is-a, so OWL DL was enough. We hadn't yet encountered some of the problems such as reflexive and anti-symmetric relationships. It also links to a web page mapping OBO to OWL 1.1 and OWL DL semantics.

As noted in "Igniting the OWL 1.1 Touch Paper: The OWL API" the addition of an object model along with the OWL 1.1 specification makes it obvious what an OWL 1.1 API should look like. I haven't yet used OWL API much, except looking at how it integrates with Pellet and how closely it matched the OWL specification. The use of axioms made the addition of RBox a bit easier to understand (or misunderstand if I've got it wrong). Hopefully, punning will be made clear to me eventually too (I've been too stupid to understand it just based on the explanations and too lazy to look into it). Pellet 1.5 also introduces incremental inferencing which is hopefully as good as it sounds.

The other papers that were of interest: "Representing Phenotypes in OWL" (again making use of qualified cardinality) and "A survey of requirements for automated reasoning services for bio-ontologies in OWL".

And just to round off, I found a very good paper, "Towards a Quantitative, Platform-Independent Analysis of Knowledge Systems", about all the mistakes that can be made during modeling (errors, assumptions, etc.) and other types of failures such as language (under or over expressive), management, learning, reasoning, querying, and others.

And I know I'll need to come back to this, which lists the fragments of OWL 1.1 that can be used to keep things computable in polynomial time.

Bottom Up Semantics

A couple of recent articles on DevX have come up by Rod Coffin exploring how a bit of semantics (and Semantic Web technology) can help improve your applications ability to understand what people are trying to do. The first, Let Semantics Bring Sophistication to Your Applications introduces the concepts of ontologies and querying. The second, Use Semantic Language Tools to Better Understand User Intentions shows how using WordNet you can supplement existing applications to improve search results.

Update: DevX now has a Semantic Web Zone.

0 dollars

SCO's Linux Billions?

For the second quarter of 2007, SCO reported a total of zero dollars of revenue from its SCOsource licensing program. In the first quarter of 2007, SCO reported SCOsource licensing revenue of $34,000, which is somewhat less than the billions McBride had been expecting.

All the Web is a Stage

Google Gears' WorkerPool - Message Passing, Shared Nothing Concurrency

By now, you‘ve probably already seen Google Gears, Google's solution for dragging AJAX applications offline. The one thing that jumped out at me was their WorkerPool component. This is a very nice solution for concurrency in Javascript.
In short: if you have any long running task, you can create a WorkerPool which is basically group of Javascript processes Note: they're not threads! The workers in a WorkerPool share nothing with each other, which makes them like OS processes or Erlang's lightweight processes (actually, they're more like the latter, as they're likely to run in the same address space).

And now guess, how these workers, these processes, communicate? Yep: messages, formatted as strings. Important to remember: if you format objects with as JSON strings, you can even send objects and structures along. The handler that receives messages also gets the ID of the sender, so if the sender implements a handler too, it‘s possible to return results asynchronously.

If you‘re reminded of Erlang or the old Actor concept you‘re right. I wonder what the Google Apps will do with this new concurrency approach (well, new for Javascript… yes I‘m ignoring Javascript Rhino).

I still hope that AJAX will die a quick death, like Java Applets, just for being so damn ugly and horrible to implement. But… things like this tell me that this will probably not happen. Good ideas like Google Gears will help paint over the ugly details of a solution, and it‘s all hip now, so it's easy to ignore many of the problems.

The same idea is also being implemented in Scala with their Actors.

Linked Together

This demo shows what can be achieved with the correct use of metadata from Flickr images. If nothing else, this answers why you would bother with metadata (as if there needs to be a justification these days). By correctly annotating your content you gain an advantage in leveraging a network of data. Via, Semantically-linked Interactive Imagery: Wow! The Emergent Web in Action and the demo Blaise Aguera y Arcas: Photosynth demo.

Update: What? I've edited this entry. Weird, I'm sure it made sense at the time.

JRDF 0.4.1.1 Released

JRDF 0.4.1.1. A bug fix release for an error in the wiring. It was wiring up the join code rather than the union code when it was suppose to do union operations. Both Derby and Hadoop were removed for this release (which reduces the GUI jar by 2 MB).

Why Fahrenheit 451 is not like 1984

Ray Bradbury: Fahrenheit 451 Misinterpreted

Now, Bradbury has decided to make news about the writing of his iconographic work and what he really meant. Fahrenheit 451 is not, he says firmly, a story about government censorship. Nor was it a response to Senator Joseph McCarthy, whose investigations had already instilled fear and stifled the creativity of thousands.

This, despite the fact that reviews, critiques and essays over the decades say that is precisely what it is all about. Even Bradbury’s authorized biographer, Sam Weller, in The Bradbury Chronicles, refers to Fahrenheit 451 as a book about censorship.

Points to Ray Bradbury at Home with movies about many topics including stories and politics.

4:34

I was struck by an interview with Ayaan Hirsi Ali. In it she says a moderate version of Islam cannot exist without disregarding parts of the Koran (and without thinking, questioning and debating). I'd always assumed this was true and thought it wouldn't bother me but I was surprised when it did. About half way through the interview she was prompted to give support for her claim that Islam does promote violence. She says there is a criteria for determining whether something is true and she quoted Sura (4:34). Without dancing around the subject it says when faced with a disobedient wife: shout at her, ignore her, and finally beat her. And as far as I can tell this is not up for dispute. It's a bit hard to describe and I'm sure I'd heard it before but for some reason it finally got to me.

So like, Timothy 2, 12 this is a religious statement, without allegory, that is clearly in conflict with modern laws and morals (assuming that morals can exist outside of religion).

I guess I'd always assumed people ignore bits that don't make sense. But as someone reading Timothy said, "What do you do when you are confronted with a finding in scripture that either goes against what you've always believed or at least contradicts what you would like to believe? There are really only two choices. Understand it, accept it and conform to it or reject it and go on doing whatever you want."

The Road After

D Conference Videos of Bill and Steve. All are from brightcove. The missing intro, complete with MacIntosh dating game is on YouTube (there's also a full transcript).

Oh the Waste

Running the Numbers

This new series looks at contemporary American culture through the austere lens of statistics. Each image portrays a specific quantity of something: fifteen million sheets of office paper (five minutes of paper use); 106,000 aluminum cans (thirty seconds of can consumption) and so on. My hope is that images representing these quantities might have a different effect than the raw numbers alone, such as we find daily in articles and books. Statistics can feel abstract and anesthetizing, making it difficult to connect with and make meaning of 3.6 million SUV sales in one year, for example, or 2.3 million Americans in prison, or 426,000 cell phones retired every day. This project visually examines these vast and bizarre measures of our society, in large intricately detailed prints assembled from thousands of smaller photographs.

It also includes, ".5 feet wide by 10.5 feet tall in three horizontal panels, Depicts 125,000 one-hundred dollar bills ($12.5 million), the amount our government spends every hour on the war in Iraq."

Via, Statistical visualization.

MapReduce SPARQL

Compositional Evaluation of W3C SPARQL Algebra via Reduce/Map "Tested against older DAWG testsuite. Implemented using functional programming idioms: fold (reduce) / unfold (map)

Does that suggest parallelizable execution?"

Thanks to SPARQL's adoption of compositional semantics (algebra) it's possible. From what I can remember, while there is an implicit left to right evaluation of OPTIONAL, which does limit the top level execution, the partial results are parallelizable. Being able to execute order independent OPTIONAL while retaining the correct results for OPTIONAL is still an open question (although feasible I think).

Available from SVN here. More musings, Musings of a Semantic / Rich Web Architect: What's Next?.

One More Pragmatic Language

Pragmatic Haskell

You see, I’ve been talking to the good folks over at Pragmatic Programmers about the possibility of doing a Haskell book. All of my writing effort has been going into that book, and as I didn’t know what the consequences would be of posting potential book content to the net, I elected to keep my mouth shut.

Well, they have agreed.

Via.

Where's the Evil?

I like bats much better than bureaucrats. I live in the Managerial Age, in a world of "Admin." The greatest evil is not now done in those sordid "dens of crime" that Dickens loved to paint. It is not done even in concentration camps and labour camps. In those we see its final result. But it is conceived and ordered (moved, seconded, carried, and minuted) in clean, carpeted, warmed, and well-lighted offices, by quiet men with white collars and cut fingernails and smooth-shaven cheeks who do not need to raise their voice. Hence, naturally enough, my symbol for Hell is something like the bureaucracy of a police state or the offices of a thoroughly nasty business concern.

From, Bullying of Academics in Higher Education. An interesting review, Notes on The Screwtape Letters.

The Health Benefits of the Semantic Web

A page about the HCLS Demo given in Banff at WWW2007 Some interesting demos. Using OpenLink's Virtuoso to store and query about 350 million statements (and many more required). Part of the demo used Armed Bear Common Lisp, which is Lisp for the JVM (compiles Lisp to bytecode).

Defeasible Logic Plus Time

Temporal extensions to Defeasible Logic. Non-monotonic reasoning is about adding more information over time to reach different conclusions. Rather than adding information adding temporal extensions actually removes when this information applies.

Even the Banner Ads are More Interesting

I was reading, Sun Tells Java Plans, of which I got to the second paragraph before noticing an Apple ad (in Flash with sound). Listened to the commercial, closed the tab, I only barely care what the article was about. So who does marketing better (actually yesterday there was one with the PC guy banging his head against the banner which was better)? Of course, I could just be responding in a Pavlovian (hmm dessert) way to the background jingle.

Romulus and Remus - C# and Java

Ted Neward talks about C# and Java. Also mentions the possible .NET backlash, Scala and LINQ. There's also a very impressive demo of LINQ (about 1/4 of the way through the code demo starts) - the struggle from imperative to declarative.

An Efficient Link Store

• Another web of data store that produces a subset of RDF/XML, Astoria, is from an unlikely source, Microsoft. Instead of a proprietary Semantic Web, Danny sees it as going to town with URIs and REST.


• Silverlight was the other surprising Microsoft development, nothing beats running code - except maybe browser-based dynamic code 2000 times faster. Applets are cool again.


• Some ideas for static triple indexing "Most mature triplestores also index a 4th query element ‘graph’ or ‘context’. I intend to support this query type without expanding the index by using a trick: In my triples format the fact that the subjects are auto-generated and local to the graph means I can choose them to be sequential and effectively re-use them as graph indexes..."


• Plugged In/Invisible Worlds/Tucana/Northrop/TKS/TMex/Kowari/Mulgara podcast (links to the Talis page).


• PAGE a distributed triple store using DHT and YARS (the original). It does seem to miss the DELIS work on P2P RDF which scaled up to 64 nodes.


• Haskell and the Faith of Programming Languages Phillip Wadler gives a rather brilliant talk on programming languages. Covers Haskell, Java generics, combining different typed languages (weak, strong, very strong) as well as monads and Links.

YARS Revenge

With little fanfare the folks at DERI have announced YARS2. I know of at least 4 next generation RDF stores (you know who you are) with a few others on the drawing board. Storing data is cool again.

To save disk space for the on-disk indices, we compress the individual blocks using Huffman coding. Depending on the data values and the sorting order of the index, we achieve a compression rate of ≈ 90%. Although compression has a marginal impact on performance, we deem that the benefits of saved disk space for large index files outweighs the slight performance dip.

Figure 4 shows the correspondence between block size and lookup time, and also shows the impact of Huffman coding on the lookup performance; block sizes are measured pre-compression. The average lookup time for a data file with 100k entries (random lookups for all subjects in the index) using a 64k block size is approximately 1.1 ms for the uncompressed and 1.4 ms for the compressed data file. For 90k random lookups over a 7 GB data file with 420 million synthetically generated triples (more on that dataset in Section 7), we achieve an average seek time of 23.5 ms.

I still wonder how the DERI guys can make the claim about it being their indexing scheme especially when Kowari was open sourced before YARS or the original paper came out. Maybe it's who publishes first? See Paul's previous discussion about it in 2005 (under the title "Indexing"). I mind that this hasn't been properly attributed as I'd like Paul and any others to get the attribution they deserve. On the other hand, I'm glad that people are taking this idea and running with it.

It's good to see that text searching on literals now seems like a standard feature too. They used a sparse index to create all 6 indices. They also hint out how reasoning is going to be performed by linking to, "Unifying Reasoning and Search to Web Scale", which suggests a tradeoff over time and trust.

You Are Here, Now

• Mammal rise 'not linked' to dinos Perhaps the best part is the beautifully rendered result of evolution for the last 166 million years. Good global warming? "However, the supertree shows that the placental mammals had already split into these sub-groups by 93 million years ago, long before the space impact and at a time when dinosaurs still ruled the planet."


• Guice Talk by Google Listing all the good ways DI makes your code better - and yes testing is the main one, more OO is another, better than service locater (J2EE) etc. Not much new here, except for no XML, for people who have been doing this for a while.


• Another Google talk by the Cyc people referenced in Priming the Pump and Threshold Conditions . With many examples that will be familiar for Semantic Web proponents.


• Closures for Java JSR Scala gets a mentions as does the BGGA proposal.


• Three reasons that REST is not RPC "Being able to do state transition processing at disparate locations is hugely powerful...A single process can span machines offering differing levels of scalability, reliability and security."


• Six of One, a Half Dozen of the Other "Closures vs. objects should really be a koan". I think this was off a reddit post at some stage. Leads to a purely functional OO system in Scheme.

Just Fearful Enough

Profile of Jon Stewart

It's sort of this odd and I've always had this problem with the rationality of it. That the President says, "We are in the fight for a way of life. This is the greatest battle of our generation, and of the generations to come. "And, so what I'm going to do is you know, Iraq has to be won, or our way of life ends, and our children and our children's children all suffer. So, what I'm gonna do is send 10,000 more troops to Baghdad."

So, there's a disconnect there between — you're telling me this is fight of our generation, and you're going to increase troops by 10 percent. And that's gonna do it. I'm sure what he would like to do is send 400,000 more troops there, but he can't, because he doesn't have them. And the way to get that would be to institute a draft. And the minute you do that, suddenly the country's not so damn busy anymore. And then they really fight back, and then the whole thing falls apart. So, they have a really delicate balance to walk between keeping us relatively fearful, but not so fearful that we stop what we're doing and really examine how it is that they've been waging this.

And there was you know, this enormous amount of space and coverage to Virginia Tech, as there should have been. And I happened to catch, sort of a headline lower down, which was 200 people killed in four bomb attacks in Iraq. And I think my focus on what was happening here versus sort of this peripheral vision thing that caught my eye about, "Oh, right, there are lives--"

Planet RDF Roundup

• Research Project: Pig Given Yahoo's usage of Hadoop it's good to see them building a query layer on top of it. And it's not SQL - hence the name - it's relationally based (it uses bags and still has DISTINCT) because that scales. Hah! Some of the documentation is gold, "In a conventional database management system, SQL queries are translated into relational algebra expressions, which are in turn translated into physical evaluation plans. Pig Latin queries are already an algebra, so we're bypassing the first layer." It even has nested relations and a flatten operation (which removes the nesting). A good read at "Yahoo Pig and Google Sawzall". Notes that Google's Sawzall looks like Scala.


• REST Compile/Describe & WADL together with I finally get REST. Wow. all link to WADL. In what seems like an age ago, I remember several enterprise architects asking what the REST equivalent to WSDL was. The later has one of the best one liners to describe REST, "state machine as node graph traversed via URI". An example of how to use is give in "REST Describe first working Beta released"


• Stavanger, oil, and the Semantic Web Talks about the "Norwegian Semantic Web Days" which covered things such as the OBO foundary.

Jobs for my Dog

So I'm idly looking at the escalating real estate market and was considering ways my dog could finally make his living. So I thought back across jobs that I'd seen that could be done equally well by him:

1. A station master. While this sounds like a job requiring thumbs, really not so much. The station being mastered no longer received any trains but still took truck deliveries. Not very many though. Now, the station master is unable to load or unload these deliveries - this is done by the drivers. So the job mainly consisted of watching people drop things off and pick things up; a job for my dog.


2. Train driver. In recent memory an accident occurred that had the distinct posibility of being caused by both drivers doing things other than driving the train. The introduction of an automated systems was suggested to prevent it happening again. Driving an automated train is something that my dog could do quite well. Actually, he could do it twice as well and he wouldn't join the union. I'm not sure he'd stick to it as it would bore the heck out of him too.


3. Doorman. Now normally this would require the ability to open and close doors. But more recently, I noticed there was a guy at a building watching an automatic door open and close. Maybe he gave directions or something but the door watching seemed to be his prime activity. I've seen my dog look attentively at the front door - he's very qualified.


4. Network Administrator. Maybe the frontal lobes need to be developed further for this one but then again maybe not. The key activities undertaken for this position, that I've seen, revolved around attending meetings and playing Solitaire. I think my dog could do this job and he wouldn't even need a computer. Apparently, this is not an uncommon job amongst dogs.


5. Phone Handler (?). These are the people I've found at the front of buildings saying, "Please use that phone to contact people before going up". Usually replaced by a sign, I think an indicative paw would do as well.

Mistakes I've Made a Few

So the ghosts of implementations past have come to haunt me in recent weeks mostly around Kowari/Tucana (now Mulgara).

Firstly, there was exclude and NAF in iTQL:

> It was introduced to provide
> a limited form of negation, and one that interacts poorly with the
> open-world assumption. We also now have minus, which is well
> defined, corresponds closely to our intuitive understanding of the
> operation, and is (I am told) what was actually required.
>
> If my memory is correct we should probably at least deprecate, if
> not remove exclude entirely from mulgara.
>
> Do we agree that exclude should be removed?

Well *I* agree anyway. As you say, it doesn't do what anyone thinks
it does.

> If it should be removed, when should this occur?

Yesterday.

And now adding the Jena API to Kowari cost customers:

Another possible reason is Tucana/Kowari/Mulgara’s Jena support - originally put in to provide a migration path for companies looking to move on from research projects to scalable infrastructure - which as Jena is the defacto semweb tool of choice, people used to evaluate Kowari’s scalability. Jena’s lack of scaling hurt us several times, I can remember lots of frantic calls as some company wrote us off because of our Jena API.

I'm current still working in this area (maybe somewhat surprisingly) and Jena still dominates (all of the tools I'm currently looking at are Jena based). And I still haven't seen a Jena implementation that scales (see page 10). Maybe the decision to open source Kowari cost another round of funding too. Maybe this is why Garlick or Radar Network's triple stores are still behind closed doors.

Extending SPARQL

A few papers related to extending SPARQL, I may update this as I find more.

• Apart from, SPARQ2L and PSPARQL there's also at the ESWC 2007 conference: iSPARQL (which uses SimPack) and SPARQLeR (which supports some quite sophisticated path queries)


• SPARQL-DL: SPARQL Query for OWL-DL An enhancement of SPARQL to support DL semantics. And they note: "SPARQL-DL is a step between RDF QLs that are too unstructured w.r.t. OWL-DL and DL QLs which are not as expressive. We believe SPARQL-DL would help interoperability on the Semantic Web as it bridges this gap. As part of future work, we intend to investigate other possible extensions to SPARQL-DL including (but not limited to) aggregation operators, epistemic operators (and negation as failure), and regular expressions on OWL properties."


• SPARQL/Update Adding INSERT, MODIFY, DELETE and UPDATE to SPARQL. I'd seen this before but hadn't linked to it.

State of Origin

Same-Origin Policy Part 1: Why we’re stuck with things like XSS and XSRF/CSRF

In my experience most developers—and even many security people—don’t really know what the same-origin policy is. Worse yet, the rise of AJAX and mash-ups seems to have turned same-origin into something developers are trying to break. Complicating the issue further are the weaknesses in most browsers’ implementations of same-origin, leaving open questions about the effectiveness of the policy itself.

I was surprised that not everyone understood this recently talking to Web 2.0 gurus. Points to the very clear definition of what exactly is the same origin. See also: Subverting Ajax, which includes things like using XSS to extend the XMLHttpRequest object to capture calls and to record the data being transmitted.

Update: Just noticed that the lastest Crypto-gram highlights a similar attack overriding object creation.

Ontologies in 3D

"OntoSphere3D is a Protégé plug-in for ontologies navigation and inspection using a 3-dimensional hyper-space where information is presented on a 3D view-port enriched by several visual cues (as the colour or the size of visualized entities)."

While I'm not usually a fan of 3D interfaces this is a fairly intuitive approach. It's certainly seems better than the neighbourhood view and hyperbolic view that they talk about in their paper. They offer a "global view" (projected onto a sphere) and "tree focus".

Java 3D can be pain to install, at least it was for me, as it wouldn't detect Protégé's JRE to install into.

Lucene for the Semantic Web

Hbase

Google's [WWW] Bigtable, a distributed storage system for structured data, is a very effective mechanism for storing very large amounts of data in a distributed environment.

Just as Bigtable leverages the distributed data storage provided by the [WWW] Google File System, Hbase will provide Bigtable-like capabilities on top of Hadoop.

Data is organized into tables, rows and columns, but a query language like SQL is not supported. Instead, an Iterator-like interface is available for scanning through a row range (and of course there is an ability to retrieve a column value for a specific key).

Any particular column may have multiple values for the same row key. A secondary key can be provided to select a particular value or an Iterator can be set up to scan through the key-value pairs for that column given a specific row key.

From the Hbase/HbaseArchitecture page:

HBase uses a data model very similar to that of Bigtable. Users store data rows in labelled tables. A data row has a sortable key and an arbitrary number of columns. The table is stored sparsely, so that rows in the same table can have crazily-varying columns, if the user likes.

A column name has the form ":" where and can be any string you like. A single table enforces its set of s (called "column groups"). You can only adjust this set of groups by performing administrative operations on the table. However, you can use new strings at any write without preannouncing it. HBase stores column groups physically close on disk. So the items in a given column group should have roughly the same write/read behavior.

Writes are row-locked only. You cannot lock multiple rows at once. All row-writes are atomic by default.

All updates to the database have an associated timestamp. The HBase will store a configurable number of versions of a given cell. Clients can get data by asking for the "most recent value as of a certain time". Or, clients can fetch all available versions at once.

The example tables given are very similar to untyped relations. This has only just become part of the nightly build.

Via, Data Parallel.

RDF Path Queries

SPARQ2L: Towards Support For Subgraph Extraction Queries in RDF Databases

Many applications in analytical domains often have the need to connect the dots i.e., query about the structure of data. In bioinformatics for example, it is typical to want to query about interactions between proteins. The aim of such queries is to extract relationships between entities i.e. paths from a data graph. Often, such queries will specify certain constraints that qualifying results must satisfy e.g. paths involving a set of mandatory nodes. Unfortunately, most present day Semantic Web query languages including the current draft of the anticipated recommendation SPARQL, lack the ability to express queries about arbitrary path structures in data.

Implemented using Java and Berkley DB and the memory store Brahms. Also mentions PSPARQL (part of Exmo), which in February reached version complete status.

The Killer Demo

What a relief there's a demo that can turn someone onto the “semantic” Web, this has obviously been a long time coming. As long as you believe the hype, the way you get the Semantic Web is one A-list blogger at a time.

Other comments: "Scoble Gets the Semantic Web", "Scoble Gets the Semantic Web", "Nova Spivack sees to it that Robert Scoble finally gets the Semantic Web", "You say Tomato...", "Describing the Semantic Data Web (Take 2)" and "QOTD : Scobleized".

A New SQL

ETech '07 Summary - Part 2 - MegaData.

Here's the thing, we need a new kind of data store, a new kind of SQL, something that does for storing and querying large amounts of data what SQL did for normalized data.

Sure you can store a lot of data in a relational database, but when I say large, I mean really large; a billion or more records. I know we need this because I keep seeing people build it.

All this talk about making SPARQL behave like SQL maybe for nothing if people realize that's not what they need after all.

The back of the envelope scalability for an RDF store would be potentially 100s of billions of statements.

The key requirements highlighted are: distributed, joinless (no referential integrity at the store level), denormalized and transactionless.

I was aware of this because a comment linked to one of my previous posts about Kowari scalability (which I must of snuck through at some stage). Kowari got up to 10,000 triples/second later on its life.

What no MOOSE?

I promised myself I wasn't going to do this again, but I have one more, one more reason why the option of even having DISTINCT/LOOSE/CHOOSE in SPARQL is a bad idea. Part of this is stimulated because once more I'm sitting next to people trying to make the Semantic Web work and from my perspective SPARQL is letting them down.

It's not a new reason, it's one I wrote in 2004 which offers a pretty good reason why having this as an optional feature doesn't make sense for RDF:

"The other issue with the SPARQL is the lack of an implicit distinct. In my understanding of SQL, DISTINCT is optional because if your queries work on normalized data and joins are based on distinct keys then the returned results cannot be duplicated. If your query works on rows with repeated values on the same column then you apply DISTINCT.

In RDF's data model there isn't really this problem of duplicated data and normalization. SPARQL has the idea of matching statements in the graph. From my understanding, RDF's data model doesn't support the idea of multiple subject, predicates and/or objects with the same values.

In other words, it only seems valid that if a query matches one result in the graph it should return that one unique result not repeated multiple results."

This is on top of the other reasons I came up in "Bagging SPARQL". This could actually be seen as further discussion from the the initial response I got. Among other things, it was said that duplicates could arise by querying multiple graphs. I'd argue that forced distinct values provide the context to effectively count (or perform other aggregate values) across these multiple graphs.

It's three years on and they couldn't even allows users to declaratively count the number of statements in this mystical, future web of data.

Patterns In Software - Part 4

Patterns of Software: Tales from the Software Community (freely available in PDF). The chapter I'll be covering this time is: "The Failure of Pattern Languages".

So it begins with the punch that the last few chapters have been building up to:

Alexander’s story does not end with the publication of A Pattern Language in 1977. It went on and still goes on. And Alexander did not sit still after he wrote the patterns. Like any scientist he tried them out.

And they did not work.

The reason, quoted by Gabriel is that other processes other than architecture play a more fundamental role. That a building is not just the process of slapping together a bunch of very well thought out patterns based on emperical evidence. It's the result of many other processes like finance, zoning, construction, etc.

...one problem with the building process is lump-sum development. In such development few resources are brought to bear on the problems of repair and piecemeal growth. Instead, a large sum of money is dedicated to building a large artifact, and that artifact is allowed to deteriorate somewhat, and anything that is found lacking in the design or construction is ignored or minimally addressed until it is feasible to abandon the building and construct a replacement.

Gabriel gives an example from a previous chapter about how these processes can destroy the otherwise good qualities of development. For example, the process of getting a mortgage and paying it off directly influences the types of buildings built and used. Generally, you invest a large amount of money in a property, so large, that you usually can't afford to make piecemeal modifications because you can barely afford paying it off. This is okay as long as people are jumping from house to house. This avoids fixing up the problems there maybe with these houses until things get really bad and they are knocked down and rebuilt. Perhaps losing what was wrong with them in the first place.

So if you retain these old processes you still get the old results. Now it's clear in software that this is also the case - a nicely architected and controlled software project does not necessarily lead to high quality software. How often have you worked on a software project that you knew was going to be re-written in a few years anyway?

Gabriel suggest that the answer lies in good code and coders not in the typical separation of analysis, design and implementation:

And isn’t the old-style software methodology to put design in the hands of analysts and designers and to put coding in the hands of lowly coders, sometimes offshore coders who can be paid the lowest wages to do the least important work?

Methodologists who insist on separating analysis and design from coding are missing the essential feature of design: The design is in the code, not in a document or in a diagram. Half a programmer’s time is spent exploring the code, not in typing it in or changing it. When you look at the code you see its design, and that’s most of what you’re looking at, and it’s mostly while coding that you’re designing.

And finally, that the typical software patterns are not following Christopher Alexander's original concept of a pattern language:

When I look at software patterns and pattern languages, I don’t see the quality without a name in them, either. Recall that Alexander said that both the patterns themselves and the pattern language have the quality. In many cases today the pattern languages are written quickly, sort of like students doing homework problems. I heard one neophyte pattern writer say that when writing patterns he just writes what he knows and can write four or five patterns at a sitting.

The answer is to build software piecemeal, incrementally, partially designed and reflecting - much more like a Turkish rug and that's the next chapter, "The Bead Game, Rugs, and Beauty".

Defenders of the Web

Tim Berners Lee goes postal on spam "So how are you going to stop the Semantic Web being poisoned?"

TBL, the GLB, replied:

Well, everybody who's building the semantic web pretty much that I know are building systems take data from lots of places, but take data with an awareness of where those places are. So for example, suppose you're getting Geotags and the OS runs a service, lots of people in this country might trust the OS to say this point has a church with a spire - other people might say it's a great church to go to, other people might say it's a heathen church to go to... those are the other sources of data...

There was no let up from the press:

"But that was the basis for Google, and Google got poisoned... "

Shadbolt and Hendler stepped in to shield Sir Tim, but he was seething at the impertinence:

I remember a conference, we were discussing the Semantic Web, and someone asked what do you think is the worst thing that can happen and all the pencils come out. I know you two have been asking about "Woargh - I know the one about... what about the bad guys? Won't we be phished" There's a temptation to give readers about all the terrible things out there OK, and all the ways the web can become less usable.

At this point, your reporter wanted to remind Sir Tim that of all the problems the web has, a hostile press is not one of them. In fact, you can't pick up a newspaper or magazine without reading about how it's ushering in a New Age of Enlightenment. Time magazine gave "Person Of The Year" to every web user in America - or at least every one who looked at the mirror Time placed on its front cover.

He continued, cryptically:

Yes you'll find a bank that's less usable - ... I've never been phished.

So the Greatest Living Briton has never been phished, which is a relief. His answer to the Semantic Web didn't inspire much confidence for the rest of us: it would be used within the firewall, amongst trusted groups, "areas where one is much less worrying about the bad guys"."

Testing and AJAX

Two completely unrelated areas of interest.

The first is Unitils which automates a number of testing tasks. It includes:
* Equality assertion through reflection, with options like ignoring Java default/null values and ignoring order of collections.
* Support for database testing involving test data management with DbUnit, automatic maintenance of unit test databases and automatic constraints disabling
* Hibernate integration features such as session management and testing the mapping with the database
* Integration with Spring, involving ApplicationContext management and injection of spring managed beans
* Integration with EasyMock and injection of mocks into other objects

The cookbook offer concrete examples to do things like mock object injection and the like.

The second is Slingshot: Desktop Apps via Rails, "Slingshot looks like it wraps up a Rails app and packages it in such a way that the user is opening up a Site Specific Browser that accesses your world". It's seen as an alternative to the Firefox 3 or Apollo.

Just One More Layer of Abstraction

" Open Source, Open data, Process Models" has Sean McGrath linking to "Open Data matters more than Open Source" which is a comment on "Open Source is Dead".

Sean writes:

Traditionally, reference implementations (i.e. traditional source code) has been the way to do this. "Running code" is the final arbiter.

Maybe this is as good as it gets? Unfortunately, a fully blown word processor runs to many, many thousands of lines of code and the semantic devil is buried way down in the details...

Dave writes:

Until we can convince (or force) web sites to embrace and standardize on Open Data formats — XML, JSON, or even CSV, as appropriate — we will be in some ways even more locked in than we were in the bad old desktop days.

Dare writes:

Similarly, how much value do you think there is to be had from a snapshot of the source code for eBay or Facebook being made available? This is one area where Open Source offers no solution to the problem of vendor lock-in. In addition, the fact that we are increasingly moving to a Web-based world means that Open Source will be less and less effective as a mechanism for preventing vendor-lockin in the software industry. This is why Open Source is dead, as it will cease to be relevant in a world where most consumers of software actually use services as opposed to installing and maintaining software that is "distributed" to them.

The point the Sean is making is that even if we achieve what Dave is suggesting we still haven't solved the semantic problem. Making it explicit and non-proprietary is not found in XML, JSON or CSV - these just aren't descriptive enough. And having running code is all fine but it's not generic enough - it will be tied to Java or C# or whatever.

The answer is of course both, but both a data format that is descriptive enough (like RDF/OWL) and open source stores that have the ability to process large quantities of it (because you will have vaste quantities of your own data in the future and you won't want one company to own it).