{"id":464,"date":"2011-09-01T08:03:55","date_gmt":"2011-09-01T12:03:55","guid":{"rendered":"http:\/\/www.openbible.info\/blog\/?p=464"},"modified":"2016-01-31T20:52:16","modified_gmt":"2016-02-01T00:52:16","slug":"bible-annotation-modeling-and-querying-in-mysql-and-couchdb","status":"publish","type":"post","link":"https:\/\/www.openbible.info\/blog\/2011\/09\/bible-annotation-modeling-and-querying-in-mysql-and-couchdb\/","title":{"rendered":"Bible Annotation Modeling and Querying in MySQL and CouchDB"},"content":{"rendered":"

If you\u2019re storing people\u2019s Bible annotations (notes, bookmarks, highlights, etc.) digitally, you want to be able to retrieve them later. Let\u2019s look at some strategies for how to store and look up these annotations.<\/p>\n

Know What You\u2019re Modeling<\/h3>\n

First you need to understand the shape of the data. I don\u2019t have access to a large repository of Bible annotations, but the Twitter and Facebook Bible citations from the Realtime Bible Search<\/a> section of this website provide a good approximation of how people cite the Bible. (Quite a few Facebook posts appear to involve people responding to their daily devotions.) These tweets and posts are public, and private annotations may take on a slightly different form, but the general shape of the data should be similar: nearly all (99%) refer to a chapter or less.<\/p>\n

\"Large<\/a><\/p>\n

Compare Bible Gateway reading habits<\/a>, which are much heavier on chapter-level usage, but 98% of accesses still involve a chapter or less.<\/p>\n

The Numbers<\/h3>\n

The data consists of about 35 million total references.<\/p>\n\n\n\n\n\n\n\n\n
Percent of Total<\/th>\nDescription<\/th>\nExample<\/th>\n<\/tr>\n
73.5<\/td>\nSingle verse<\/td>\nJohn 3:16<\/td>\n<\/tr>\n
17.1<\/td>\nVerse range in a single chapter<\/td>\nJohn 3:16-17<\/td>\n<\/tr>\n
8.4<\/td>\nExactly one chapter<\/td>\nJohn 3<\/td>\n<\/tr>\n
0.7<\/td>\nTwo or more chapters (at chapter boundaries)<\/td>\nJohn 3-4<\/td>\n<\/tr>\n
0.1<\/td>\nVerses spanning two chapters (not at chapter boundaries)<\/td>\nJohn 3:16-4:2<\/td>\n<\/tr>\n
0.1<\/td>\nVerses spanning three or more chapters (not at chapter boundaries)<\/td>\nJohn 3:16-5:2<\/td>\n<\/tr>\n<\/table>\n

About 92.9% of posts or tweets cited only one verse or verse range; 7.1% mentioned more than one verse range. Of the latter, 77% cited exactly two verse ranges; the highest had 323 independent verse ranges. Of Facebook posts, 9.1% contained multiple verse ranges, compared to 4.2% of tweets. When there were multiple ranges, 43% of the time they referred to verses in different books from the other ranges; 39% referred to verses in the same book (but not in the same chapter); and 18% referred to verses in the same chapter. (This distribution is a unusual\u2014normally close verses stick together.)<\/p>\n

The data, oddly, doesn\u2019t contain any references that span multiple books. Less than 0.01% of passage accesses span multiple books on Bible Gateway, which is probably a useful upper bound for this type of data.<\/p>\n

Key Points<\/h4>\n
    \n
  1. Nearly all citations involve verses in the same chapter; only 1% involve verses in multiple chapters.<\/li>\n
  2. Of the 1% spanning two or more chapters, most refer to exact chapter boundaries.<\/li>\n
  3. Multiple-book references are even more unusual (under 0.01%) but have outsize effects: an annotation that references Genesis 1 to Revelation 22 would be relevant for every verse in the Bible.<\/li>\n
  4. Around 7% of notes contained multiple independent ranges of verses\u2014the more text you allow for an annotation, the more likely someone is to mention multiple verses.<\/li>\n<\/ol>\n

    Download<\/h4>\n

    Download the raw social data<\/a> (1.4 MB zip) under the usual CC-Attribution license.<\/p>\n

    Data Modeling<\/h3>\n

    A Bible annotation consists of arbitrary content (a highlight might have one kind of content, while a proper note might have a title, body, attachments, etc., but modeling the content itself isn’t the point of this piece) tied to one or more Bible references:<\/p>\n

      \n
    1. A single verse (John 3:16).<\/li>\n
    2. A single range (John 3:16-17).<\/li>\n
    3. Multiple verses or ranges (John 3:16, John 3:18-19)<\/li>\n<\/ol>\n

      The Relational Model<\/h3>\n

      One user can have many rows of annotations, and one annotation can have many rows of verses that it refers to. To model a Bible annotation relationally, we set up three tables that look something like this:<\/p>\n

      users<\/h4>\n\n\n\n
      user_id<\/th>\nname<\/th>\n<\/tr>\n
      1<\/td>\n\u2026<\/td>\n<\/tr>\n<\/table>\n

      annotations<\/h4>\n\n\n\n\n\n
      user_id<\/th>\nannotation_id<\/th>\ncontent<\/th>\n<\/tr>\n
      1<\/td>\n101<\/td>\n\u2026<\/td>\n<\/tr>\n
      1<\/td>\n102<\/td>\n\u2026<\/td>\n<\/tr>\n
      1<\/td>\n103<\/td>\n\u2026<\/td>\n<\/tr>\n<\/table>\n

      annotation_verses<\/h4>\n

      The verse references here are integers to allow for easy range searches: 43 = John (the 43rd book in the typical Protestant Bible); 003 = the third chapter; the last three digits = the verse number.<\/p>\n

      I like using this approach over others (sequential integer or separate columns for book, chapter, and verse) because it limits the need for a lookup table. (You just need to know that 43 = John, and then you can find any verse or range of verses in that book.) It also lets you find all the annotations for a particular chapter without having to know how many verses are in the chapter. (The longest chapter in the Bible has 176 verses, so you know that all the verses in John 3, for example, fall between 43003001 and 43003176.) This main disadvantage is that you don\u2019t necessarily know how many verses you\u2019re selecting until after you\u2019ve selected them. And using individual columns, unlike here, does allow you to run group by<\/code> queries to get easy counts.<\/p>\n\n\n\n\n\n\n
      annotation_id<\/th>\nstart_verse<\/th>\nend_verse<\/th>\n<\/tr>\n
      101<\/td>\n43003016<\/td>\n43003016<\/td>\n<\/tr>\n
      102<\/td>\n43003016<\/td>\n43003017<\/td>\n<\/tr>\n
      103<\/td>\n43003016<\/td>\n43003016<\/td>\n<\/tr>\n
      103<\/td>\n43003019<\/td>\n43003020<\/td>\n<\/tr>\n<\/table>\n

      Querying<\/h3>\n

      In a Bible application, the usual mode of accessing annotations is by passage: if you\u2019re looking at John 3:16-18, you want to see all your annotations that apply to that passage.<\/p>\n

      Querying MySQL<\/h3>\n

      In SQL terms:<\/p>\n

      select distinct(annotations.annotation_id)
      \nfrom annotations, annotation_verses
      \nwhere annotation_verses.start_verse <= 43003018 and
      \nannotation_verses.end_verse >= 43003016 and
      \nannotations.user_id = 1 and
      \nannotations.annotation_id = annotation_verses.annotation_id
      \norder by annotation_verses.start_verse asc, annotation_verses.end_verse desc<\/code><\/p>\n

      The quirkiest part of the SQL is the first part of the \u201cwhere\u201d clause, which at first glance looks backward: why is the last verse in the start_verse<\/code> field and the first verse in the end_verse<\/code> field? Because the start_verse<\/code> and end_verse<\/code> can span any range of verses, you need to make sure that you get any range that overlaps the verses you\u2019re looking for: in other words, the start_verse<\/code> is before the end of the range, and the end_verse<\/code> is after the start.<\/p>\n

      Visually, you can think of each start_verse<\/code> and end_verse<\/code> pair as a line: if the line overlaps the shaded area you\u2019re looking for, then it\u2019s a relevant annotation. If not, it\u2019s not relevant. There are six cases:<\/p>\n

      \"Start<\/p>\n

      The other trick in the SQL is the sort order: you generally want to see annotations in canonical order, starting with the longest range first. In other words, you start with an annotation about John 3, then to a section inside John 3, then to individual verses. In this way, you move from the broadest annotations to the narrowest annotations. You may want to switch up this order, but it makes a good default.<\/p>\n

      The relational approach works pretty well. If you worry about the performance implications of the SQL join, you can always put the user_id<\/code> in annotation_verses<\/code> or use a view or something.<\/p>\n

      Querying CouchDB<\/h3>\n

      CouchDB<\/a> is one of the oldest entrants in the NoSQL space and distinguishes itself by being both a key-value store and queryable using map-reduce: the usual way to access more than one document in a single query is to write Javascript to output the data you want. It lets you create complex keys to query by, so you might think that you can generate a key like [start_verse,end_verse]<\/code> and query it like this: ?startkey=[0,43003016]&endkey=[43003018,99999999]<\/code><\/p>\n

      But no. Views are one-dimensional, meaning that CouchDB doesn\u2019t even look at the second element in the key if the first one matches the query. For example, an annotation with both a start and end verse of 19001001<\/code> matches the above query, which isn\u2019t useful for this purpose.<\/p>\n

      I can think of two ways to get around this limitation, both of which have drawbacks.<\/p>\n

      GeoCouch<\/h4>\n

      CouchDB has a plugin called GeoCouch that lets you query geographic data, which actually maps well to this data model. (I didn\u2019t come up with this approach on my own: see Efficient Time-based Range Queries in CouchDB using GeoCouch<\/a> for the background.)<\/p>\n

      The basic idea is to treat each start_verse,end_verse<\/code> pair as a point on a two-dimensional grid. Here\u2019s the above social data plotted this way:<\/p>\n

      \"A<\/p>\n

      The line bisects the grid diagonally since an end_verse<\/code> never precedes a start_verse<\/code>: the diagonal line where start_verse = end_verse<\/code> indicates the lower bound of any reference. Here are some points indicating where ranges fall on the plot:<\/p>\n

      \"This<\/p>\n

      To find all the annotations relevant to John 3:16-18, we draw a region starting in the upper left and continuing to the point 43003018,43003016<\/code>:<\/p>\n

      \"This<\/p>\n

      GeoCouch allows exactly this kind of bounding-box query: ?bbox=0,43003016,43003018,99999999<\/code><\/p>\n

      You can even support multiple users in this scheme: just give everyone their own, independent box. I might occupy 1×1 (with an annotation at 1.43003016,1.43003016<\/code>), while you might occupy 2×2 (with an annotation at 2.43003016,2.43003016<\/code>); queries for our annotations would never overlap. Each whole number to the left of the decimal acts as a namespace.<\/p>\n

      The drawbacks:<\/p>\n

        \n
      1. The results aren\u2019t sorted in a useful way. You\u2019ll need to do sorting on the client side or in a show function<\/a>.<\/li>\n
      2. You don\u2019t get pagination.<\/li>\n<\/ol>\n

        Repetition at Intervals<\/h4>\n

        Given the shape of the data, which is overwhelmingly chapter-bound (and lookups, which at least on Bible Gateway are chapter-based), you could simply repeat chapter-spanning annotations at the beginning of every chapter. In the worst case annotation (Genesis 1-Revelation 22), you end up with about 1200 repetitions.<\/p>\n

        For example, in the Genesis-Revelation case, for John 3 you might create a key like [43000000.01001001,66022021]<\/code> so that it sorts at the beginning of the chapter\u2014and if you have multiple annotations with different start verses, they stay sorted properly.<\/p>\n

        To get annotations for John 3:16-18, you\u2019d query for ?startkey=[43003000]&endkey=[43003018,{}]<\/code><\/p>\n

        The drawbacks:<\/p>\n

          \n
        1. You have to filter out all the irrelevant annotations: if you have a lot of annotations about John 3:14, you have to skip through them all before you get to the ones about John 3:16.<\/li>\n
        2. You have to filter out duplicates when the range you\u2019re querying for spans multiple chapters.<\/li>\n
        3. You\u2019re repeating yourself, though given how rarely a multi-chapter span (let alone a multi-book span) happens in the wild, it might not matter that much.<\/li>\n<\/ol>\n

          Other CouchDB Approaches<\/h4>\n

          Both these approaches assume that you want to make only one query to retrieve the data. If you\u2019re willing to make multiple queries, you could create different list functions and query them in parallel: for example, you could have one for single-chapter annotations and one for multi-chapter annotations. See interval trees<\/a> and geohashes<\/a> for additional ideas. You could also introduce a separate query layer, such as elasticsearch<\/a>, to sit on top of CouchDB<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

          If you\u2019re storing people\u2019s Bible annotations (notes, bookmarks, highlights, etc.) digitally, you want to be able to retrieve them later. Let\u2019s look at some strategies for how to store and look up these annotations. Know What You\u2019re Modeling First you need to understand the shape of the data. I don\u2019t have access to a large […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[18,12,9],"tags":[],"_links":{"self":[{"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/posts\/464"}],"collection":[{"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/comments?post=464"}],"version-history":[{"count":54,"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/posts\/464\/revisions"}],"predecessor-version":[{"id":1134,"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/posts\/464\/revisions\/1134"}],"wp:attachment":[{"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/media?parent=464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/categories?post=464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.openbible.info\/blog\/wp-json\/wp\/v2\/tags?post=464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}