Loading...
Please wait, while we are loading the content...
Similar Documents
On the Complexity of Query Answering under Matching Dependencies for Entity Resolution
| Content Provider | CiteSeerX |
|---|---|
| Author | Bertossi, Leopoldo Gardezi, Jaffer |
| Abstract | Abstract. Matching Dependencies (MDs) are a relatively recent proposal for declarative entity resolution. They are rules that specify, given the similarities satisfied by values in a database, what values should be considered duplicates, and have to be matched. On the basis of a chase-like procedure for MD enforcement, we can obtain clean (duplicate-free) instances; actually possibly several of them. The resolved answers to queries are those that are invariant under the resulting class of resolved instances. In previous work we identified some tractable cases (i.e. for certain classes of queries and MDs) of resolved query answering. In this paper we further investigate the complexity of this problem, identifying some intractable cases. For a special case we obtain a dichotomy complexity result. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Chase-like Procedure Recent Proposal Tractable Case Resolved Answer Declarative Entity Resolution Query Answering Certain Class Entity Resolution Matching Dependency Dichotomy Complexity Result Intractable Case Md Enforcement Resolved Instance |
| Content Type | Text |
| Resource Type | Article |
