Back to Search
Start Over
Querying Incomplete Information in Semistructured Data
- Source :
- Journal of Computer and System Sciences. 64:655-693
- Publication Year :
- 2002
- Publisher :
- Elsevier BV, 2002.
-
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 reflected 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 satisfied. 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 refine the model of query evaluation. The first modification relates to the satisfaction of constraints: in some circumstances we consider constraints 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 constraints of the query. Our model of query evaluation consists of two phases, a search phase and a filter 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 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 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 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.
- Subjects :
- Theoretical computer science
Computer Networks and Communications
Applied Mathematics
InformationSystems_DATABASEMANAGEMENT
Directed graph
Query language
Query optimization
Theoretical Computer Science
Spatial query
Query expansion
Computational Theory and Mathematics
Web query classification
Sargable
Computer Science::Databases
Boolean conjunctive query
Mathematics
Subjects
Details
- ISSN :
- 00220000
- Volume :
- 64
- Database :
- OpenAIRE
- Journal :
- Journal of Computer and System Sciences
- Accession number :
- edsair.doi.dedup.....67055b885627c3944982998fe69dd588
- Full Text :
- https://doi.org/10.1006/jcss.2001.1811