Hackszine.com: SQL Archives

Archive: SQL

April 8, 2008

Relational database using jQuery and HTML tables

Here's a novel use for the HTML <TABLE> tag: storing client side database tables. Nick Kallen came up with a slick hack that uses the jQuery syntax to perform simple selects and joins on HTML tables. By using CSS3 selectors, you can easily target fields which match or contain your search terms, and Nick's jQuery-based API provides a simple query language, similar to a rudimentary SQL:

Today I was thinking aloud about Tree Regular Expressions and how they might make a nice query language for document databases like CouchDB. Someone pointed out that CSS3 selectors might make a great concrete syntax for this. One thing lead to another and I thought, why not build a relational database in HTML? So I did. I even got inner joins working.
Let's start with a few tables:
<table class="users">
  <tr>
    <td class="id">1</td>
    <td class="first_name">amy</td>
    <td class="last_name">bobamy</td>
  </tr> 
  ...
</table>
<table class="photos">
  <tr>
    <td class="id">1</td>
    <td class="user_id">1</td>
    <td class="url">http://www.example.com/foo.png</td>
  </tr> 
</table>
Now we can express some queries:
$('.users')
  .where('.id:eq(1)')
  .select('*')
This is equivalent to SELECT * FROM users WHERE id = 1
$('.users')
  .where('.id:eq(1)')
  .select('.id, .name')
This is equivalent to SELECT id, name FROM users WHERE id = 1

How cool is that? Check out Nick's blog post for an example of text search and an inner join. The API in his jquery.db.js is quite straightforward and only about 50 lines of code. Adding a sort function shouldn't be too difficult.

I'm pretty much convinced now that jQuery is black magic.

Building a relational database using jQuery and <TABLE> tags
Download the jquery.db.js library

March 2, 2008

Point polygon intersection in SQL

update: As readers noted, it's not the 0 degrees longitude that's the problem, it's at 180 degrees where you could encounter issues. I've also escaped the gt and lt symbols. Sorry about that.

I spent the weekend participating in the F1 Website Challenge, a coding marathon in which competing teams each produce a mythical man-month's worth of web site for a worthy non-profit organization—all in the space of 24 hours.

One of the challenges my team faced during development was finding an efficient way for detecting a particular service region for a given address. Our client, Metro Meals on Wheels, has a number of different regions in which they deliver meals, with each region being served by a particular Meals on Wheels organization. These regions are defined by non-overlapping complex polygons. It's not as simple as a normal vendor search, where you return the nearest location to the requested address. Instead you need to search a database of polygons to find the particular one which intersects the address location.

One of my teammates, Mark Seemann, ended up providing a fairly elegant solution to the problem, and was able to implement it in a simple SQL query. To find out if a point intersects a polygon, it's as simple as drawing a vector from the point and seeing how many line segments of the polygon it crosses. If the number is even, it's outside the polygon. If it's odd, you have an intersection.

So let's say you have a polygon database which has a row for each line segment of a polygon. You can quickly pull all segments that intersect a vector pointing directly east of your geocoded location like this:

SELECT poly_id, segment_id
    FROM segments
    WHERE ( lnga > thelng OR lngb > thelng )
          AND ( (lata > thelat AND latb < thelat )
              OR (latb > thelat AND lata < thelat ) )

That will return you a list of all line segments that you would cross if you walked directly east from the location at [thelat,thelng] (yes, this assumes you don't cross 180 degrees longitude). To determine the polygon (or polygons) that intersect our address, it's as simple as grouping by poly and returning all rows that have an odd number of matches:

SELECT poly_id, COUNT(segment_id) AS segment_count
    FROM segments
    WHERE ( lnga > thelng OR lngb > thelng )
          AND ( (lata > thelat AND latb < thelat )
              OR (latb > thelat AND lata < thelat ) )
          AND segment_count%2 = 1
    GROUP BY poly_id

Of course, the world isn't flat, though I've treated it this way for simplicity. If you wanted this to work for all cases, you'd need to limit your search to a particular distance and translate the coordinates so that the search didn't cross 180 degrees longitude.