Two Java Collection Utilities

Lately I stumbled upon two iteresting Java libraries which add search capabilities to Java collections: one adding SQL search and another adding XPath search syntax to an existing collection. I think it's cool - you can take a collection of Java objects and treat it in a high level way! I suppose they are implemented using introspection.

The first one is called JoSQL (http://josql.sourceforge.net/index.html) and can be used like this:

try {
    Query q = new Query ();
    q.parse(
        "SELECT *" +
        "FROM java.lang.String " +
        "WHERE length <= :stringSize " +
        "AND toString LIKE '%e%' " +
        "ORDER BY length DESC");

    q.setVariable ("stringSize", "5");
    List<String> names = new ArrayList<String>();
    String[] n = {
        "alpha", "beta", "gamma", "delta", "epsilon", "zeta", "pi", "chi"
    };
    Collections.addAll(names, n);

    QueryResults qres = q.execute(names);
    List res = qres.getResults();
}
catch(Exception e) ...

Here I got { "beta", "delta", "epsilon" } as result. The only problem I can see as far is that the library doesn't use generics. The other one is the somehow unintuitive way it's treating the "SELECT *" query. Nomally the JoSQL library treats a collection of Java objects as a table which columns are formed by the values returned by the class' methods. However, in case of a "SELECT *" query, we won't get all of the object's attributes, but just the whole object as it is. On the other side, it's the equivalent, isn't it.

The second one is called jXPath (http://commons.apache.org/jxpath/), and is part of the Apache project. You can use it like that:

    JXPathContext context = JXPathContext.newContext(employees);

    Employee emp =
       (Employee)context.getValue("/employees[name='Susan' and age=27]");

Pretty nifty, isn't it? But while SQL query syntax seemed obvious to me, the XPath search expressions seems plain ugly and non-intuitive. I don't know both SQL and X-Path very good, but I find myself always forgetting pretty everything about XPath while SQL gets stuck. Maybe because XPath is too low-level an too much a hack?

You can read in many blogs that the above libraries are pretty the same, but in reality, the XPath query syntax is better for hierarchical data, somehow like that:

    Employee emp =
        (Employee)context.getValue("/departments/employees[name='Johnny']");

I assume you can do the equivalent in JoSQL, but you'd like to use joins, an that isn't that convenient for simple hierarchical structures like that above. So, in the end, maybe the XPath isn't so bad after all?

Some distributed computing news: cuddly elephans, pigs, nymphs and couch computing

As I did some distributed computing research in my previous life, and then tried to get involved with Google, I'm still somehow interested in the subject. If you are into distributed computing, you'd know that Google is using a distributed C++ system called MapReduce* for indexing of the crawled webpages. It happens that there's an open-source Java implemenation of Google's system (based on published Google's research papers) called Hadoop . Up to now I didn't know about any serious usage of Hadoop in big distributed systems, but as it comes, I learned that Yahoo! is using Hadoop internally** for spam detection!

Yahoo's researchers have also designed a new language called PIG Latin (?!)*** for distributed programming on the Hadoop platform. The idea is rather an interesting one: they pointed out that the existing way of writing programs for the mapper and reducer part of a distributed application is too low-level and not reusable, but somehow familiar to programmers. In contrast, a declarative language like SQL poses some problems, so the paradigm there is completely diffrent:

At the same time, the transformations carried out in each step are fairly high-level, e.g.,filltering, grouping, and aggregation, much like in SQL. The use of such high-level primitives renders low-level manipulations (as required in map-reduce) unnecessary.
...
To experienced system programmers, this method is much more appealing than encoding their task as an SQL query, and then coercing the system to choose the desired plan through optimizer hints.

So it provides a middle ground, where we can avoid SQL and write down the computation steps, but can do that at higher level!

Unsuprisingly, Microsoft already has a proprietary distributed computing platform called Dryad, which tries to do something like this as well, but is using C# and LINQ (i.e. an SQL-like query language):

DryadLINQ generates Dryad computations from the LINQ Language-Integrated Query extensions to C#.

But I don't know how much this is a research project and if it's really used internally. On the other side, Microsoft recently aquired a search company called Powerset, which is using Hadoop at its core, and as the gossip runs, should be used to bring Microsoft's LiveSearch up to speed.

Facebook, in their turn, are using Hadoop, but added a Business Intelligence tool called Hive (now released as open source!) on top of it. It uses an SQL-like query language, as BI-users understand it best. Beneath the surface Hive leverages Hadoop and translates SQL-like imperatives into MapReduce jobs.


Not bad, cuddly elephant! It seems everyone is loving you!


Accidentally, when speaking about SQL and non-SQL: there's a non-SQL database by Apache called Couch DB. It is written in Erlang (we reported already**** ;-)) and implements a distributed document database. It's designed for lock-free concurrency using Erlang's "share-nothing" philosophy. To my mind it resembles Linus' Thorvalds git source configuration system, as it holds all the versions of documents determining the "winner" to be visible in defined views. Hear, hear! Erlang's alive, distributing and kicking!

Another thing worth noticing is that's not only SQL anymore, there are attempts to do things differently, athough others are sticking with the ol 'n reliable. Paradigm change on its way? It's interesting times I think.

PS (6 Okt. 2009): Look, look, now even the Big Blue has jumped the wagon too! They offer the M2 enterprise data analysis platform, based on Hadoop and using PIG. See: http://www.sdtimes.com/link/33808. So it seems Hadoop is definitely mainstream and business analyst thingie now, and as such it has lost much of its appeal, as far as I'm concerned.

---
* Jeffrey Dean, Sanjay Ghemawat: "MapReduce: Simplified Data Processing on Large Clusters", OSDI 2004, http://labs.google.com/papers/mapreduce.html
** unfortunately it's a two-parts video: http://developer.yahoo.net/blogs/hadoop/2009/03/using_hadoop_to_fight_spam_-_part_1.html
*** Christopher Olston et al: "Pig Latin: A Not-So-Foreign Language for Data Processing", SIGMOD 2008, http://www.cs.cmu.edu/~olston/publications/sigmod08.pdf
**** http://ib-krajewski.blogspot.com/2007/08/erlangs-change-of-fortunes.html

What can you learn from the bad guys?

Really, is there something you can learn from them? Confucius said some time ago: "I'm always glad to meet another voyager: if it's a pleasant man, I can learn what I can do better, if it's an unpleasant man, I can learn what I shouldn't do!". But can we learn something in apositive sense? In order to be able to answer this, let us return to the realm of IT.

What do the really bad IT-guys do? They break in into systems! They use a host of techniques, and one which is particularly interesting is the "SQL injection" (I personally prefer the more colourful - if slightly incorrect - name "SQL hijacking"). Let's explain it using an SQL example. If we build an SQL query string like this:

query = "SELECT * FROM users WHERE name = ' " + userName + ' ";

Now, if we supply an user name string like, say "dummy' or name not null --", the resulting SQL query looks like*:

SELECT * FROM users WHERE name = 'dummy' or name not null --'

And this will get you the list of all users in the system! If the submitted username is like "xxx'; DROP TABLE users; --" the attacker can even get nasty on the database! Simple but effective!

So what, you'd say, how many bad guys will have direct access to my SQL database? Well, you'd be surprised! If you have a Web application which accesses an SQL database the following scenario is conceiveable. The bad guy invokes your SQL database indirectly requesting an URL in the form:

your.site.de/your_app/ListUsersAction.do?ID=11;UPDATE+USER+SET+TYPE="admin"+WHERE+ID=23

which, when appended to the "SELECT * FROM users WHERE id=" string will grant the attacker the admin privileges! Or, when he requests the URL in the form:

your.site.de/your_app/ListUsersAction.do?ID=11;GO+EXEC+cmdshell('format+C')

the disaster is looming! I don't want to discuss this in detail, as it's not a hack instruction page, but I hope you've got the general idea: this a real problem for the Web application development. Well, that's all very bad behaviour and all, but the question is: why should we learn anything about this?

Recently I was charged with extension of a J2EE web application for one of my clients.They were using a proprietary custom tag JSP library**, whose sources were not available (unfortunately, in a big company that's not so unusual). The custom tag library was rather nice, but as the code was gone, it was not extensible. For example, I couldn't specify the onClick attribute for the custom button tag:

<somelib:button action="someapp/SomeAction.do" image="..." ... ⁄>

Can you see it? Think, think... Yes! Let us try some JSP/Javascript injection:

<somelib:button action="someapp/SomeAction.do \" onClick=\"alert('Gotcha!'); \" " image="..." ... ⁄>

which produces, when iterpreted to HTML, a wonderful:

... url="someapp/SomeAction.do" onClick="alert('Gotcha!')" image="..."

The reason why this is working*** ist the fact that \" isn't interpreted as the end of string sign, as it is escaped with a "\" ! So we have a kind of double bottom here - on one level we have a regular string, which, when interpreted, is transformed into something different sematically - it's the second bottom. Isn't it beautiful? On one level (tags) we have a senseless string, which on the lower level (HTML) gets injected into a page code and starts living its own life! Like a seed coming to life after a hibernation phase. Since then I used this technique in several other places, and it never ceases to amaze me. Look at that: <somelib:help key="start_task" tooltip="Help \" align=\"right\" "/>.

So now we can answer the title question: from the bad guys, we can learn how to extend a non-extensible JSP custom tag library! And yes, Confucius was right: we can learn from every person. Indeed.

---
* here "--" comments out the last apostrofe, but we might as well add some ineffective condition like "and name='yyy" to balance the apostrophes.
** for those of you not doing J2EE: a custom tag is a sort of macro generating HTML code when interpreded on the server side
*** this works on Tomcat, and as Tomcat is the reference implementation of a Servlet container... guess what.

shell as a "modern" programming language

I don't know how many of you is reading ACCU's Overload magazine, but I do. In the last issue* we find an article by Thomas Guest with the flippant title: "He Sells Shell Scripts to Intersect Sets", which demonstrates implementation of the set-theoretic operations (i.e. union, intersection, difference, etc) in UNIX shell language. As interesting pastime as these techniques are, I was struck by the final words of the article:

"For me, it’s not just what the shell tools can do, it’s the example they set. Look again at some of the recipes presented in this article and you’ll see container operations without explicit loops. You’ll see flexible and generic algorithms. You’ll see functional programming. You’ll see programs which can parallel-process data without a thread or a mutex in sight; no chance of shared memory corruption or race conditions here.

.....the intent shines through as clearly as ever: we have a compact suite of orthogonal tools, each with its own responsibility, which cooperate using simple interfaces. We would do well to emulate this model in our own software designs."

The second part of the quote was not new to me: in fact I've heard it uncountable many (pun intended) times from my distinguished colleague Stefan Z.: set of simple tools which can be combined through a common set of interfaces. You've probably read this many times before. But what I really liked, is the mercilessly pointed out (timeless?) modernity of the shell: its high level programming model, its extensibility, its focusing on concepts and hiding details away. This stands in sharp contrast to the self proclaimed "modern" programming languages of the day: Java and C# (or is this already Python?), which rather don't excel in this regard.

We so often take these features of shell programming for granted, that it must be sometimes pointed out to make us think about it. These features are not given as a matter of course! After day-to-day struggle with low level aspects of the "modern" programming languages it sometimes pays off to turn your attention to shell and contemplate it's design once again (and dream of a better world ;-).

If you are Java programmer, read it. You'll like it. It's a lesson in abstraction.

---
* Overload 80, August 2007: http://accu.org/index.php/journals/c78/

Reprise:

Speaking about set operations: relational databases are built around a set algebra (as relations are sets in, ehm, set theory), so the shell file operations could be in principle implemented with SQL! If only we could turn the Apache logs from the abovementioned article into realtional tables...

Well, why not! Look at SQLite - an embeddable, zero-configuration, C-language database (it's used in GoogleGears for example). This database has one pretty nifty feature known as "virtual tables"*: you only have to write some callback methods which will be called by the SQLite database engine to read data which are stored in different formats. For example you could treat the filesystem as a database table(s), i.e. fire SQL queries on it! So, leaving out all technical details, it's possible with the help of virtual tables to scan our logfile using SQL! I guess it's rather cool.

---
* http://www.sqlite.org/cvstrac/wiki?p=VirtualTables