Digital Symposium Collection 2000

Queries with Incomplete Answers over Semistructured Data Yaron Kanza, Werner Nutt, and Yehoshua Sagiv   View Paper (PDF)   Return to Semistructured Data Abstract Semistructured data occur in situations where information lacks a homogenous structure and is incomplete. Yet, up to now the incompleteness of information has not been reflected by special features of query languages for semistructured data. Our goal is to investigate the pricnciples of queries that allow for incomplete answers. We do not present, however, a concrete query language. Queries over classical structured data models contain a number of variables and conditions on these variables. An answer is a binding of the variables by elements of the database such that the conditions are satisfied. In the present paper, we loosen this concept insofar as we allow also anwers that are partial, that is, not all variables in the query are bound by such an answer. Partial answers make it necessary to refine the model of query evaluation. The first modification relates to the satisfaction of conditions: under some circumstances we consider conditions involving unbound variables as satisfied. Second, in order to prevent a proliferation of answers, we only accept answers that are maximal in the sense that there are no assignments that bind more variables and satisfy the conditions of the query. Our model of query evaluation consits of two phases, a search phase and a filter phase. Semistructured databases are essentially labeled directed graphs. In the search pase, we use a query graph containing variables to match a maximal portion of the database graph. We investigate three different semantics for query graphs, which give rise to three variants of matching. For each variant, we provide algorithms and complexity results. In the filter phase, the maximal matchings resulting from the search phase are subjected to constraints, which may be weak or string. Strong constraints require all their variables to be bound, while weak constraints do not. We describe a polynomial algorithm for evaluating a special type of query with filter constraints and assess the complexity of evaluating other queries for several kinds of constraints. In the final part, we investigate the containment problem for queries consisting only of search constraints under the different semantics. References Note: References link to DBLP on the Web. [Abi97] Serge Abiteboul : Querying Semi-Structured Data. ICDT 1997 : 1-18 [AM98] Gustavo O. Arocena , Alberto O. Mendelzon : WebOQL: Restructuring Documents, Databases, and Webs. ICDE 1998 : 24-33 [AMM97] Paolo Atzeni , Giansalvatore Mecca , Paolo Merialdo : To Weave the Web. VLDB 1997 : 206-215 [AQM+97] 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) [AV97a] Serge Abiteboul , Victor Vianu : Queries and Computation on the Web. ICDT 1997 : 262-275 [AV97b] Serge Abiteboul , Victor Vianu : Regular Path Queries with Constraints. PODS 1997 : 122-133 [BDFS97] Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu : Adding Structure to Unstructured Data. ICDT 1997 : 336-350 [BDHS96] Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516 [BFW98] Peter Buneman , Wenfei Fan , Scott Weinstein : Path Constraints in Semistructured and Structured Databases. PODS 1998 : 129-138 [BG81] Philip A. Bernstein , Nathan Goodman : Power of Natural Semijoins. SIAM J. Comput. 10(4) : 751-771(1981) [Bun97] Peter Buneman : Semistructured Data. PODS 1997 : 117-121 [CAW98] Sudarshan S. Chawathe , Serge Abiteboul , Jennifer Widom : Representing and Querying Changes in Semistructured Data. ICDE 1998 : 4-13 [CM77] Ashok K. Chandra , Philip M. Merlin : Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977 : 77-90 [CMW82] Isabel F. Cruz , Alberto O. Mendelzon , Peter T. Wood : A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987 : 323-330 [FFK+98] Mary F. Fernandez , Daniela Florescu , Jaewoo Kang , Alon Y. Levy , Dan Suciu : Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998 : 414-425 [FLS98] Daniela Florescu , Alon Y. Levy , Dan Suciu : Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998 : 139-148 [FPS97] Mary F. Fernandez , Lucian Popa , Dan Suciu : A Structure-Based Approach to Querying Semi-Structured Data. DBPL 1997 : 136-159 [GL94] César A. Galindo-Legaria : Outerjoins as Disjunctions. SIGMOD Conference 1994 : 348-358 [GW97] Roy Goldman , Jennifer Widom : DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997 : 436-445 [HMV96] Masum Z. Hasan , Alberto O. Mendelzon , Dimitra Vista : Applying database Visualization to the World Wide Web. SIGMOD Record 25(4) : 45-49(1996) [KMSS97] Yakov A. Kogan , David Michaeli , Yehoshua Sagiv , Oded Shmueli : Utilizing the Multiple Facets of WWW Contents. NGITS 1997 : 0- [KMSS98] Yakov A. Kogan , David Michaeli , Yehoshua Sagiv , Oded Shmueli : Utilizing the Multiple Facets of WWW Contents. DKE 28(3) : 255-275(1998) [KS95] David Konopnicki , Oded Shmueli : W3QS: A Query System for the World-Wide Web. VLDB 1995 : 54-65 [KS97] David Konopnicki , Oded Shmueli : W3QS - A System for WWW Querying. ICDE 1997 : 586 [LSS96] Laks V. S. Lakshmanan , Fereidoon Sadri , Iyer N. Subramanian : A Declarative Language for Querying and Restructuring the WEB. RIDE-NDS 1996 : 12-21 [MAG+97] Jason McHugh , Serge Abiteboul , Roy Goldman , Dallan Quass , Jennifer Widom : Lore: A Database Management System for Semistructured Data. SIGMOD Record 26(3) : 54-66(1997) [MAM+98] Giansalvatore Mecca , Paolo Atzeni , Alessandro Masci , Paolo Merialdo , Giuseppe Sindoni : The Araneus Web-Base Management System. SIGMOD Conference 1998 : 544-546 [MM97] Alberto O. Mendelzon , Tova Milo : Formal Models of Web Queries. PODS 1997 : 134-143 [MMM97] Alberto O. Mendelzon , George A. Mihaila , Tova Milo : Querying the World Wide Web. Int. J. on Digital Libraries 1(1) : 54-67(1997) [NAM98] Svetlozar Nestorov , Serge Abiteboul , Rajeev Motwani : Extracting Schema from Semistructured Data. SIGMOD Conference 1998 : 295-306 [PGMW95] Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom : Object Exchange Across Heterogeneous Information Sources. ICDE 1995 : 251-260 [QRS+94] ... [QWG+96] Dallan Quass , Jennifer Widom , Roy Goldman , Kevin Haas , Qingshan Luo , Jason McHugh , Svetlozar Nestorov , Anand Rajaraman , Hugo Rivero , Serge Abiteboul , Jeffrey D. Ullman , Janet L. Wiener : LORE: A Lightweight Object REpository for Semistructured Data. SIGMOD Conf. 1996 : 549 [RU96] Anand Rajaraman , Jeffrey D. Ullman : Integrating Information by Outerjoins and Full Disjunctions. PODS 1996 : 238-248 BIBTEX @inproceedings{DBLP:conf/pods/KanzaNS99,   author    = {Yaron Kanza and                 Werner Nutt and                 Yehoshua Sagiv},    title     = {Queries with Incomplete Answers over Semistructured Data},    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     = {227-236},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM