Digital Symposium Collection 2000

Using LDAP Directory Caches Sophie Cluet, Olga Kapitskaia, and Divesh Srivastava   View Paper (PDF)   Return to Novel Data Abstract LDAP (Lightweight Directory Access Protocol) directories have recently proliferated with the growth of the Internet, and are being used in a wide variety of network-based applications to store data such as personal profiles, address books, and network and service policies. These systems provide a means for managing heterogeneity in a way far superior to what conventional relational or object-oriented databases can offer. To achieve fast performance for declarative query answering, it is desirable to use client caching based on semantic information (instead of individual directory entries). We formally consider the problem of reusing cached LDAP directory entries for answering declarative LDAP queries. A semantic LDAP directory cache contains directory entries, which are semantically described by a set of query templates. We show that, for conjunctive queries and LDAP directory caches with positive templates, the complexity of cache-answerability is NP-complete in the size of the query. For this case, we design a sound and complete algorithm for cache-answerability based on a suite of query transformations that capture the semantics of LDAP queries. We demonstrate the practicality of this algorithm for real applications with a performance evaluation, based on sample queries from a directory enabled application at AT&T Labs. When the query templates in the cache contain negation, we show that the complexity of cache-answerability of conjunctive LDAP queries is co-NP complete in the size of the schema and query templates in the semantic description of the cache. Finally, we identify natural restrictions on the nature of the semantic descriptions for polynomial-time cache-answerability. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Dallan Quass , Jason McHugh , Jennifer Widom , Janet L. Wiener : The Lorel Query Language for Semistructured Data. Int. J. on Digital Libraries 1(1) : 68-88(1997) [2] Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516 [3] Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan : Semantic Data Caching and Replacement. VLDB 1996 : 330-341 [4] Prasad Deshpande , Karthikeyan Ramasamy , Amit Shukla , Jeffrey F. Naughton : Caching Multidimensional Queries Using Chunks. SIGMOD Conference 1998 : 259-270 [5] Mary F. Fernandez , Daniela Florescu , Alon Y. Levy , Dan Suciu : A Query Language for a Web-Site Management System. SIGMOD Record 26(3) : 4-11(1997) [6] Michael J. Franklin : Client Data Caching: A Foundation for High Performance Object Oriented Database Systems. Kluwer 1996, ISBN 0-7923-9701-0 [7] M. R. Garey , David S. Johnson : Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7 [8] ... [9] ... [10] ... [11] H. V. Jagadish , Laks V. S. Lakshmanan , Tova Milo , Divesh Srivastava , Dimitra Vista : Querying Network Directories. SIGMOD Conference 1999 : 133-144 [12] Arthur M. Keller , Julie Basu : A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB Journal 5(1) : 35-47(1996) [13] Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104 [14] Nick Roussopoulos , Chung-Min Chen , Stephen Kelley , Alex Delis , Yannis Papakonstantinou : The ADMS Project: View R Us. Data Engineering Bulletin 18(2) : 19-28(1995) [15] Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy : Answering Queries with Aggregation Using Views. VLDB 1996 : 318-329 BIBTEX @inproceedings{DBLP:conf/pods/CluetKS99,   author    = {Sophie Cluet and                 Olga Kapitskaia and                 Divesh Srivastava},    title     = {Using LDAP Directory Caches},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {273-284},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM