Loading...
Please wait, while we are loading the content...
Similar Documents
Semantics and Algorithms for Queries with Incomplete Answers over Semistructured Data
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kanza, Yaron Nutt, Werner Sagiv, Yehoshua |
| Copyright Year | 1999 |
| Abstract | Semistructured data occur in situations where information lacks a homogeneous structure and is incomplete. Yet, up to now the incompleteness of information has not been re ected by special features of query languages. Our goal is to investigate the principles 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 constraints on these variables. An answer is a binding of the variables by elements of the database such that the constraints are satis ed. In the present paper, we loosen this concept in so far as we allow also answers that are partial, that is, not all variables in the query are bound by such an answer. Partial answers make it necessary to re ne the model of query evaluation. The rst modi cation relates to the satisfaction of constraints: under some circumstances we consider constraints involving unbound variables as satis ed. 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 constraints of the query. Our model of query evaluation consists of two phases, a search phase and a lter phase. Semistructured databases are essentially labeled directed graphs. In the search phase, we use a query graph containing variables to match a maximal portion of the database graph. We investigate three di erent semantics for query graphs, which give rise to three variants of matching. For each variant, we provide algorithms and complexity results. In the lter phase, the maximal matchings resulting from the search phase are subjected to constraints, which may be weak or strong. 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 queries with lter constraints, and assess the complexity of evaluating other queries for several kinds of constraints. In the nal part, we investigate the containment problem for queries consisting only of search constraints under the di erent semantics. Institute for Computer Science, The Hebrew University, Jerusalem 91904, Israel, yarok@cs.huji.ac.il German Research Center for Arti cial Intelligence GmbH, Stuhlsatzenhausweg 3, 66123 Saarbr ucken, Germany nutt@dfki.de |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.dblab.ntua.gr/~dwq/p27.pdf |
| Alternate Webpage(s) | http://www.dbnet.ece.ntua.gr/~dwq/p27.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
