Mapping-equivalence and oid-equivalence of single-function object-creating conjunctive queries
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. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Data IntegrationObjectSimilar Papers 제목 키워드 기반
Discovering Generalizable Spatial Goal Representations via Graph-based Active Reward Learning
In this work, we consider one-shot imitation learning for object rearrangement tasks, where an AI agent needs to watch a single expert demonstration and learn to perform the same task in different environments. To achiev…
AI AgentImitation LearningObject RearrangementLexical Perspective on Wordnet to Wordnet Mapping
The paper presents a feature-based model of equivalence targeted at (manual) sense linking between Princeton WordNet and plWordNet. The model incorporates insights from lexicographic and translation theories on bilingual…
Machine TranslationTranslationFunctional Equivalence and Path Connectivity of Reducible Hyperbolic Tangent Networks
Understanding the learning process of artificial neural networks requires clarifying the structure of the parameter space within which learning takes place. A neural network parameter's functional equivalence class is th…
D-VAL: An automatic functional equivalence validation tool for planning domain models
This paper introduces an approach to validate the functional equivalence of planning domain models. Validating the functional equivalence of planning domain models is the problem of formally confirming that two planning …
Functional Equivalence with NARS
This study explores the concept of functional equivalence within the framework of the Non-Axiomatic Reasoning System (NARS), specifically through OpenNARS for Applications (ONA). Functional equivalence allows organisms t…
Decision Making