Archive for November, 2008

Nested Sets, PHP, Verb Objects and Noun Objects

Introduction

Controversy persists to this day about the relative merits of dynamic languages such as PHP and Python versus static languages such as C# and Java.  We’re finding more and more that the difference isn’t so much about static or dynamic typing,  but more about the cultures of different languages.   In this article,  I discuss an efficient representations of SQL trees in a database,  an algorithm for creating that representation,  and a PHP implementation.  The PHP implementations uses objects in a way foreign to many developers:  rather than using objects to represent nouns (data),  it uses a class to represent a verb (an algorithm.)  I make the case that programmers shouldn’t feel compelled to create new classes to represent every data item:  that verb objects often provide the right level of abstraction for many tasks.

The Presenting Problem

Lately I’ve been collecting pictures of animals, and decided that incorporating the taxonomic database from ITIS would be a big help. I’m interested in asking questions like “What are all the species underneath the Tapiridae family?” The ITIS database uses the adjacency list representation, where each row contains a column that references the primary key of a parent row. Algorithms for the adjacency list are well known, but are awkward to implement in SQL since it takes multiple SQL statements to traverse a tree. Continue Reading »