Querying network directories

ABSTRACT

Heirarchically structured 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 scale and heterogeneity, while allowing for conceptual unity and autonomy across multiple directory servers in the network, in a way for superior to what conventional relational or object-oriented databases offer. Yet, in deployed systems today, much of the data is modeled in an ad hoc manner, and many of the more sophisticated “queries” involve navigational access. In this paper, we develop the core of a formal data model for network directories, and propose a sequence of efficiently computable query languages with increasing expressive power. The directory data model can naturally represent rich forms of heterogeneity exhibited in the real world. Answers to queries expressible in our query languages can exhibit the same kinds of heterogeneity. We present external memory algorithms for the evaluation of queries posed in our directory query languages, and prove the efficiency of each algorithm in terms of its I/O complexity. Our data model and query languages share the flexibility and utility of the recent proposals for semi-structured data models, while at the same time effectively addressing the specific needs of network directory applications, which we demonstrate by means of a representative real-life example.

REFERENCES

• 1: Directory enabled networks ad hoc working group. http://w ww.mu rchiso.com/den/.
• 2: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel query language for semistructured data. Journal on Digital Libraries, 1(1), 1996.
• 3: N. Anerousis, R. Gopalakrishnan, C. R. Kalmanek, A. E. Kaplan, W. T. Marshall, P. P. Mishra, P. Z. Onufryk, K. K. Ramakrishnan, and C. J. Sreenan. TOPS: An architecture for telephony over packet networks. IEEE Journal on Selected Areas in Cc, mmunications, 17(1):91-108, 1999.
• 4: Gustavo O. Arocena , Alberto O. Mendelzon , George A. Mihaila, Applications of a Web query language, Selected papers from the sixth international conference on World Wide Web, p.1305-1316, September 1997, Santa Clara, California, United States
• 5: Catriel Beeri , Tova Milo, Schemas for Integration and Translation of Structured and Semi-structured Data, Proceeding of the 7th International Conference on Database Theory, p.296-313, January 10-12, 1999
• 6: Alexander Borgida , Ronald J. Brachman , Deborah L. McGuinness , Lori Alperin Resnick, CLASSIC: a structural data model for objects, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.58-67, June 1989, Portland, Oregon, United States
• 7: Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu, Adding Structure to Unstructured Data, Proceedings of the 6th International Conference on Database Theory, p.336-350, January 08-10, 1997
• 8: Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
• 9: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, What can knowledge representation do for semi-structured data?, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.205-210, July 1998, Madison, Wisconsin, United States
• 10: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• 11: Cisco. Directory enabled networks. Available from ht tp: / / www.cisco, corn / warp / pub lic /734/den/.
• 12: Mariano P. Consens , Alberto O. Mendelzon, GraphLog: a visual formalism for real life recursion, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.404-416, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298591]
• 13: Mariano Consens , Alberto Mendelzon, Hy+: a Hygraph-based query and visualization system, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.511-516, May 25-28, 1993, Washington, D.C., United States
• 14: Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for a Web-site management system, ACM SIGMOD Record, v.26 n.3, p.4-11, Sept. 1997 [doi>10.1145/262762.262763]
• 15: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 16: T. Howes. The string representation of LDAP search filters. Request for Comments 2254. Available from ftp://ds.internic.net/rfc/rfc2254.txt, Dec. 1997.
• 17: Tim Howes , Mark Smith, LDAP: programming directory-enabled applications with lightweight directory access protocol, Macmillan Publishing Co., Inc., Indianapolis, IN, 1997
• 18: Innosoft.Innosoft's LDAP world implemerttation survey. Available from http://www.criticalangle.com/dir/lisurvey.html.
• 19: Guy Jacobson , Balachander Krishnamurthy , Divesh Srivastava , Dan Suciu, Focusing search in hierarchical structures with directory sets, Proceedings of the seventh international conference on Information and knowledge management, p.1-9, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288635]
• 20: H. V. Jagadish , Mark A. Jones , Divesh Srivastava , Dimitra Vista, Flexible list management in a directory, Proceedings of the seventh international conference on Information and knowledge management, p.10-19, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288636]
• 21: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 22: P. Mockapetris. Domain names: Concepts and l'acilities. Request for Comments 882. Available from ftp: //ds.internic.net/rfc/rfc882.t xt, 1983.
• 23: S. Nestorov, S. Abiteboul, and R. Motwani. Inferring structure in semistructured data. In Proceedings of t,~e Workshop on Management of Semi-structured Data, 1997.
• 24: Kenneth A. Ross , Divesh Srivastava , Damianos Chatziantoniou, Complex Aggregation at Multiple Granularities, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.263-277, March 23-27, 1998
• 25: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 26: M. Wahl, A. CouIbeck, T. Howes, and S. Kille. Lightweight directory access protocol (v3): Attribute syntax definitions. Request for Comments 2252. Available from ftp://ds.internic.net/rfc/rfc2252.txt, Dec. 1997.
• 27: M. Wahl, T. Howes, and S. Kille. Lightweight directory access protocol (v3). Request for Comments 2251. Available from ftp://ds.internic.net/rfc/rfc2251.txt, Dec. 1997.
• 28: M. Wahl, S. Kille, and T. Howes. Lightweight directory access protocol (v3): UTF-8 string representation of distinguished names. Request for Comments 2:253. Available from ftp://ds.internic.net/rfc/rfc2253.txt, Dec. 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data dictionary/directory

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models; Schema and subschema
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Languages, Management, Performance, Theory