ArsDigita Archives

Bookmarks Design Document

by Cynthia Kiser

I. Essentials:

II. Introduction:

One of the most annoying things about having ready access to many personal computers is that something you need inevitably ends up trapped on the other machine. In encouraging users to store more of their useful information on an ACS web service, we can increase it's usefulness and hopefully increase "site stickiness". The ability to view other people's bookmarks and to make some or all of one's own bookmarks publically visible can encourage community sharing of knowledge.

This application allows the user to add individual bookmarks by hand or upload their entire Netscape bookmark file - IE users are offered a tool that they can use to convert their directory of individual shortcuts to a Netscape-style bookmarks file. Once the bookmarks (and folders) are entered into the system, users can move bookmarks within the folder structure. One can test individual or multiple links to see if they are still responding and delete dead or unwanted bookmarks. By default bookmarks are public - a person may mark individual bookmarks or entire folders of bookmarks as private.

To facilitate collaboration within communities, bookmarks default to public and users can view all the public bookmarks for the site - by individual user or sorted by popularity. The most poular domains are also listed.

Limitations of the current system:

  • Cannot sort bookmarks within folders - the order in which the bookmarks appear is dependent on the order in which they are uploaded.
  • If one rearranges the order of bookmarks within your local Netscape bookmark file, they are not recognized as the same and this induces multiple copies of hte same bookmark within that folder. We could solve this by only allowing single copies of each bookmark mapped to the user's personal bookmark tree, however this is less of improvement than the imposition of a different limitation
  • There isn't any group scoping - bookmarks are public or private.

III. Historical Considerations

There are notes in the data model indicating that originally a bookmark folder was a tree built by Oracle's connect by function - but I think this was changed before the original application release because it would be too slow to build if the bookmark file got reasonably complex.

IV. Competitive Analysis

  • Sorting bookmarks and folders - will require a sort key and API to rearrange those sort keys
  • Allowing bookmark of FTP sites - would not let me add manually because `site was unreachable' - probably did not answer to port 80 in the check.
  • Rating of bookmark usefulness would increase community usefulness but we don't expect to build that in until we have someone more actively using bookmarks
  • Possibly add group delete feature and move delete link up to index.tcl

V. Design trade offs

As discussed in the data model section, the sort key scheme used for bookmarks is an adaptation of the one originally employed for bboards. Each level of hierarchy adds 3 digits to the sort key and the keys are sorted alphanumerically give one the sort order within a level. The benefit of this scheme is that sorting these keys alphanumerically allows one to rapidly generate an arbitrarily deep hierarchy without significantly increasing the time it takes to construct. If the nested hierarchy were to be implemented by an Oracle connect by this would rapidly become unweildly to pull out of the database.

The drawback of this scheme is that it is difficult to do anything except append something to the tail end of that level of the hierarchy. Re-sorting bookmarks within a folder involves recalculating all the sort keys from the point of insertion onwards. That is not so bad - except if one of the affected entries is not a bookmark but a folder. Then all of the entries within that folder (bookmarks or subfolders) will have to have the last 3 digits of their sort key updated to reflect the new position of their parent folder. That still does not sound so bad - but what about subfolders within that folder? then we have to update 3 digits within the parent sort key. And so on. That is why despite the desirability of sorting bookmarks within folders that feature has not been implemented.

VI. Data Model

Bookmarks data model is basically 2 tables - one for the URLs, bm_urls and one mapping urls to the user's bookmark page, bm_list. bm_urls stores the url, domain (for quick calculation of popularity of specific domains), info about their content (keywords and desctriptions to use for searching), the date the status of the bookmark was last checked, and the date it was last reached.

For a bookmark to be included on a user's bookmark page, a row is written to bm_list mapping the url to the user and indicating its position in the hierarchy of their bookmark tree. Folders are designated with folder_p and can either be shown open or closed; the fact that the display state of the folder is stored in the database means that it persists across browser sessions - good if you want to come back and see things as you left it - except of course if someone else was browsing your bookmarks and left open one of the folders you usually leave closed!!! To supress the visiblity of bookmarks within closed folders, those bookmark records have their in_closed_p column marked `t'.

Sorting of bookmarks into folders is handled by a scheme that stores the sort order in a string calculated at insertion time that alphanumerically sorts in the correct fashion. For each level of hierarchy, one adds an additional 3 digits to the sort key, thus the level of nesting of a url/folder entry can be found from length(parent_sort_key || local_sort_key)/3. Since one only wants to increment the last triple of the sort key in order to add a new entry to a folder, the original author chose to save the the actual sort key in 2 columns, the parent and local sort keys. New sublevels are created by concatenating the parent_sort_key and local_sort_key and using that as the parent key for the entries at the next lower level. PL/SQL functions have been provided that calculate the next sort key in a sequence - we need this because the 3 character string that is the sort_key contains each of 0-9, A-Z, a-z.

Bookmarks can be public or private (private_p = 't'). To deal with public bookmarks that are within folders that are marked private the hidden flag is `t' if a public bookmark is within a private folder (to be clarified).

In the first iterations of this application, there were indices defined on composite keys - this actually slowed matters down considerably. These have been replaced by indices on all columns with foreign key constraints - e.g. index the parent_id in bm_list.

VII. Legal transactions

  • Add: Each link is checked to see if we already have a copy in links table, if not, insert a row into bm_urls, then insert a row in user's bookmarks table.
  • Delete: Just deletes the row in user's bm_list - do we check for orphans and clean out bm_urls? Don't think so.
  • Move a bookmark: Append it to the end of the folder that the user asked us to put it in (take the sort key of the parent folder as the parent_sort_key, and grab the next value in the pseudo-sequence from the new_sort_key PL/SQL function
  • Open and close a folder: Close marks a folder close_p, and all of the children recursively in_close_p? Open marks a folder and its children close_p and in_close_p false, respectively.
  • Mark individual bookmarks as private: Sets private_p = 't'. Mark entire folders private marks the folder and all its children private so that one can use the hidden_p to be able to override this.


PL/SQL functions for sorting:

  • Function for finding a new sort key: new_sort_key (Takes a local sort key and increments it by one. )
  • Helper function for the new sort key: inc_char_for_sort_key (Increments old_char from 0-9, A-Z, a-z. Sets carry_p to 1 if incrementing from z to 0.)
  • Insert trigger bm_list_sort_key_i_tr (Calculates local and parent sort keys for new insert.)
  • Updating is a little harder because we are using information from the table that is changing in order to make the changes. So we need to define a package to store the IDs that have been changed bm_list_pkg and a row level trigger to file the package bm_list_sort_key_u_tr. Then we need a trigger to fix up the sort keys bm_fixup_sort_key. This fixes up parent_sort_key and local_sort_key for a bookmark. If the bookmark was a folder, this trigger recursively updates the children. And finally we need a statement level trigger to run after updates fixup sort keys. bm_list_after_u_tr


  • When bookmarks are uploaded individually, we check to see if the link is working; if the server does not respond the link cannot be added. Because it would be time prohibitive to do the same for bulk uploads, links are not checked when uploaded in bulk from a Netscape style bookmarks file.
  • This module has very little administrative interface. The site-wide administrator can look look at some site-wide stats, check links. Link checking also parses keywords and descriptions out of the document head and adds that information to the database to facilitate searching.

X. Configuration parameters

Except for the parameter that limits the size of the bookmark file that may be uploaded, all of the configuration parameters for this application are cosmetic: system owner, system name, html tags for indicating private and dead links, folder and file colors.

XI. Acceptance tests

  • Add one bookmark manually by URL only
  • Create a new folder and a subfolder
  • Edit the bookmark by
    • changing its name
    • changing its location to the new folder
    • making it private
  • Make the folder private and check if its contents are marked as private, too
  • Click on a folder and subfolder to open/close them
  • Delete (through edit) the folder, thereby deleting the bookmarks as well
  • Import bookmarks from a Netscape bookmarks file
  • View the Javascript version
  • Check validity the links and delete some dead links

XII. Future Improvements/Areas of Likely Change

  • Enhanced sorting functionality that doesn't significantly increase sort times
  • Pre-build a portal that will show most popular links
  • Link checking looks broken. If there are a reasonable number of bookmarks, the page looks like it does not return. If left alone, it will finish. The last run we tested on the bookmarks stored at ran for 40 minutes before returning a page. This is one time that we really need to stream stuff out to the user as we move through the page.
  • There was also a bug that was related to how AOLserver 3.0 was sending the http requests that made some servers not respond even though they were up and running. This is fixed in the current stable version (AOLserver 3.0 + aD patch 5).

XIII. Authors:

  • System creators: Dave Hill and Aure Prochazka
  • System owner: Cynthia Kiser
  • Documentation author: Cynthia Kiser