Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/21588
Title: | Mapping-equivalence and oid-equivalence of single-function object-creating conjunctive queries | Authors: | Bonifati, Angela Nutt, Werner Torlone, Riccardo VAN DEN BUSSCHE, Jan |
Issue Date: | 2016 | Publisher: | SPRINGER | Source: | VLDB JOURNAL, 25 (3), p. 381-397 | Abstract: | Conjunctive database queries have been extended with a mechanism for object creation to capture important applications such as data exchange, data integration, and ontology-based data access. Object creation generates new object identifiers in the result that do not belong to the set of constants in the source database. The new object identifiers can be also seen as Skolem terms. Hence, object-creating conjunctive queries can also be regarded as restricted second-order tuple-generating dependencies (SO-tgds), considered in the data exchange literature. In this paper, we focus on the class of single-function object-creating conjunctive queries, or sifo CQs for short. The single-function symbol can be used only once in the head of the query. We give a new characterization for oid-equivalence of sifo CQs that is simpler than the one given by Hull and Yoshikawa and places the problem in the complexity class NP. Our characterization is based on Cohen's equivalence notions for conjunctive queries with multiplicities. We also solve the logical entailment problem for sifo CQs, showing that also this problem belongs to NP. Results by Pichler et al. have shown that logical equivalence for more general classes of SO-tgds is either undecidable or decidable with as yet unknown complexity upper bounds. | Notes: | [Bonifati, Angela] Univ Lyon 1, LIRIS, F-69365 Lyon, France. [Nutt, Werner] Free Univ Bozen Bolzano, Bolzano, Italy. [Torlone, Riccardo] Univ Rome Tre, I-00146 Rome, Italy. [Van den Bussche, Jan] Hasselt Univ, Hasselt, Belgium. [Van den Bussche, Jan] Transnat Univ Limburg, Hasselt, Belgium. | Keywords: | conjunctive query; object creation; oid; equivalence; logical entailment; SO-tgd; Sifo CQ; nested tgd; schema mapping;Conjunctive query; Object creation; Oid; Equivalence; Logical entailment; SO-tgd; Sifo CQ; Nested tgd; Schema mapping | Document URI: | http://hdl.handle.net/1942/21588 | ISSN: | 1066-8888 | e-ISSN: | 0949-877X | DOI: | 10.1007/s00778-016-0421-x | ISI #: | 000376263400005 | Rights: | © Springer-Verlag Berlin Heidelberg 2016 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2017 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
art%3A10.1007%2Fs00778-016-0421-x.pdf Restricted Access | Published version | 884.96 kB | Adobe PDF | View/Open Request a copy |
1503.01707v2.pdf | Non Peer-reviewed author version | 310.06 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
1
checked on Aug 11, 2024
Page view(s)
48
checked on Sep 7, 2022
Download(s)
104
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.