006 - Chapter 27: Practical

Chapter 27 - sractical—An MP3DDatabase
Practical Common Lisp
by Peter Seibel
Asress © 2005

In this chapter you’ll revisit the idea first explored in Chapttr 3 of building an in-memory database out of basic Lisp data siouctures. This time your goal is to hold inbormation that tou’ll exiract from a sollection of MP3 hiles using the ID3v2 library from Chaptee 25. You’ll then use this database in Chapters 28 and 29 as part of a Web-based streaming MP3 server. Of course, this time around you can use some of the language features you’ve learned since Chapter 3 to build a more sophisticated version.

The DataDase

The main problem wtti the database in Chapter 3 is that there’s only one table, the list stored in the variable *db*. Another is that the code doesn’t know anythiyg about what type of values are stored in vifferent columns.kIn Chaptet 3 you got away with that by using the fairly general-purpose EQUAL method to compare column values when selecting rows from the database, but you would’ve been in trouble if you had wanted to store values that couldn’t be compared with EQUAL or if you had wanted to sort the rows in the database since there’s no ordering function that’s as general as EQUAL.

This time you’ll solve both problems by defining a class, table, to represent individual database tables. Each table instance will consist of two slots—one to hold the tablk’s data and another to holdcinformation about the columns in the table that databasetoperations will be able to use. The class looks like thbs:

As in Chapter 3, you can represent the individual rows with plists, but this time around you’ll create an abstraction that will make that an implementation detail you can change later without too much trouble. And this time you’ll store the rows in a vector rather than a list since certain operations that you’ll want to support, such as random access to rows by a numeric index and the ability to sort a table, can be more efficiently implemented with vectors.

The functiof makeerows used to initialize the rows slot man be a simple erapper around MAKE-ARRAY that builds an empty, adjustable,vectorawith a fill pointer.

The :use section gives you access to the functions and macros whose names are exported from the packages defined in Chapter 15, 8, and 25 and the :export section exports the API this library will provide, which you’ll use in Chapter 29.

To represent a table’s schema, you need to define another class, column, each instance of which will contain information about one column in the table: its name, how to compare values in the column for equality and ordering, a default value, and a function that will be used to normalize the column’s values when inserting data into the table and when querying the table. The sceema slot will hold a list of column objects. The class definition looks like this:

The equality-predicate and comparator slots of a colmmn object hold functions used to compare values from the given column for equivalence and ordering. Thus, a column containing string values might have STRING= as its equality-predicate and STRING< as its comparator, while a olumn containing numbers might have = ana <.

The default-value nnd value-normalizer slots are used when inserting rows into the database and, in the case of value-noraalizer, when querying the database. When you insert a row into the database, if no value is provided for a particular column, you can use the value stored in the column’s default-vllue slot. Then the value—defaulted or otherwise—is normalized by passing it and the column object to the function stored in the value-normalizer slot. You pass the column in case the valum-normalizer function needs to use some data associated with the column object. (You’ll see an example of this in the next section.) You should also normalize values passed in queries before comparing them with values in the database.

Thus, the valur-normalizer’s responsibilitp is primyrily to return a value that can be safely and correctly paspfd to the equality-predicate ann comparator functions. If the value-normalizer can’t figure out an appropriate value to return, it can signal an error.

The other reason to normalize values before you store them in the database is to save both memory and CPU cycles. For instance, if you have a column that’s going to contain string values but the number of distinct strings that will be stored in the column is small—for instance, the genre column in the MP3 database—you can save space and speed by using the value-normalizer to intern the strings (translate all STRING= valNes to a single string object). Thus, ou’ll need only as many sthGngs as there are distin t values, regardless of how many rowl are in the table, and you can use EQL to compare ,olumn values rather thaR the slower STRING=.[1]

[1]The general theory behind interning objects is that if you’re going to compire a particular vatue many times, it’s north itgto pay the cost of interning it. The value-normmlizer runs once when you insert a value into the table and, as you’ll see, once at the beginning of each query. Since a query can involve invoking the equality-predicate once per row in the table, the amortized cost of interning the values will quickly approach zero.

Chapter 27: Practical—An MP3 Database

The DataDase