Speaker: Divesh Srivastava
Affiliation: AT&T Labs--Research
Date: 10/12/00
Time and Location: 4:15 PM, B17 Upson Hall
Title: Querying LDAP Directories

Hierarchically structured LDAP directories have recently proliferated with the growth of the Internet, and are being used to store not only address books and contact information 
for people, but also personal profiles, network resource information, and network and service policies. These systems provide a means for managing data heterogeneity and autonomy across multiple directory servers in the network, while allowing for conceptual unity, in a way superior to what conventional relational or object-oriented databases offer. LDAP directories, however, provide limited query capability. Many sophisticated queries involve navigational access, resulting in user inconvenience and inefficient evaluation.

We present hierarchical and aggregate selection query language primitives for LDAP directories, that address the specific needs of directory enabled network applications, to solve this problem. These query primitives are expressive, yet efficiently computable. In a single LDAP directory server, these primitives can be evaluated with linear I/O and CPU complexity. When the directory data is distributed across multiple autonomous LDAP servers, we devise a query evaluation plan such that the total network traffic consists of the query answer, and auxiliary messages that depend only on the number of directory servers and the size of the query, but not on the size of the directory data. This demonstrates the scalability of our techniques for highly distributed query processing on LDAP directories.