Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















Querying Network Directories

H. V. Jagadish, Laks V. S. Lakshmanan, Tova Milo, Divesh Srivastava, and Dimitra Vista

  View Paper (PDF)  

Return to Languages and Models

Abstract
Hierarchically 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 far 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 exibility 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

Note: References link to DBLP on the Web.

[1]
...
[2]
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)
[3]
...
[4]
...
[5]
Catriel Beeri , Tova Milo : Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999 : 296-313
[6]
Alexander Borgida , Ronald J. Brachman , Deborah L. McGuinness , Lori Alperin Resnick : CLASSIC: A Structural Data Model for Objects. SIGMOD Conference 1989 : 58-67
[7]
Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu : Adding Structure to Unstructured Data. ICDT 1997 : 336-350
[8]
Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516
[9]
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini : What can Knowledge Representation do for Semi-Structured Data? AAAI/IAAI 1998 : 205-210
[10]
Luca Cardelli , Peter Wegner : On Understanding Types, Data Abstraction, and Polymorphism. Computing Surveys 17(4) : 471-522(1985)
[11]
...
[12]
Mariano P. Consens , Alberto O. Mendelzon : GraphLog: a Visual Formalism for Real Life Recursion. PODS 1990 : 404-416
[13]
Mariano P. Consens , Alberto O. Mendelzon : Hy+: A Hygraph-based Query and Visualization System. SIGMOD Conference 1993 : 511-516
[14]
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)
[15]
Roy Goldman , Jennifer Widom : DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997 : 436-445
[16]
...
[17]
...
[18]
...
[19]
Guy Jacobson , Balachander Krishnamurthy , Divesh Srivastava , Dan Suciu : Focusing Search in Hierarchical Structures with Directory Sets. CIKM 1998 : 1-9
[20]
H. V. Jagadish , Mark A. Jones , Divesh Srivastava , Dimitra Vista : Flexible List Management in a Directory. CIKM 1998 : 10-19
[21]
Edward M. McCreight : A Space-Economical Suffix Tree Construction Algorithm. JACM 23(2) : 262-272(1976)
[22]
...
[23]
Svetlozar Nestorov , Serge Abiteboul , Rajeev Motwani : Infering Structure in Semistructured Data. SIGMOD Record 26(4) : 39-43(1997)
[24]
Kenneth A. Ross , Divesh Srivastava , Damianos Chatziantoniou : Complex Aggregation at Multiple Granularities. EDBT 1998 : 263-277
[25]
Jeffrey D. Ullman : Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
[26]
...
[27]
...
[28]
...

Referenced by

  1. H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava : What can Hierarchies do for Data Warehouses? VLDB 1999 : 530-541
  2. Sophie Cluet , Olga Kapitskaia , Divesh Srivastava : Using LDAP Directory Caches. PODS 1999 : 273-284

BIBTEX

@inproceedings{DBLP:conf/sigmod/JagadishLMSV99,
  author    = {H. V. Jagadish and
                Laks V. S. Lakshmanan and
                Tova Milo and
                Divesh Srivastava and
                Dimitra Vista},
   editor    = {Alex Delis and
                Christos Faloutsos and
                Shahram Ghandeharizadeh},
   title     = {Querying Network Directories},
   booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference
                on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,
                USA},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-084-8},
   pages     = {133-144},
   crossref  = {DBLP:conf/sigmod/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM