1,721,035 research outputs found
Relaxed Notions of Schema Mapping Equivalence Revisited
No full textRecently, two relaxed notions of equivalence of schema mappings
have been introduced, which provide more potential of optimizing
schema mappings than logical equivalence: data exchange (DE)
equivalence and conjunctive query (CQ) equivalence. In this work,
we systematically investigate these notions of equivalence for mappings consisting of s-t tgds and target egds and/or target tgds. We
prove that both CQ- and DE-equivalence are undecidable and so are
some important optimization tasks (like detecting if some dependency
is redundant). However, we also identify an important difference
between the two notions of equivalence: CQ-equivalence remains undecidable even if the schema mappings consist of s-t tgds and target dependencies in the form of key dependencies only. In contrast, DE-equivalence is decidable for schema mappings with s-t tgds and target dependencies in the form of functional and inclusion
dependencies with terminating chase property
The Complexity of Evaluating Tuple Generating Dependencies
No full textDependencies have played an important role in database design for
many years. More recently, they have also turned out to be central
to data integration and data exchange. In this work we concentrate
on tuple generating dependencies (tgds) which enforce the presence
of certain tuples in a database instance if certain other tuples
are already present. Previous complexity results in data integration
and data exchange mainly referred to the data complexity. In this
work, we study the query complexity and combined complexity of
a fundamental problem related to tgds, namely checking if a given
tgd is satisfied by a database instance. We also address an important
variant of this problem which deals with updates (by inserts or
deletes) of a database: Here we have to check if all previously satisfied tgds are still satisfied after an update. We show that the query complexity and combined complexity of these problems are much
higher than the data complexity. However, we also prove sufficient
conditions on the tgds to reduce this high complexity
Function Symbols in Tuple-Generating Dependencies
No full textTuple-generating dependencies -- for short tgds -- have been a staple of database research throughout most of its history. Yet one of the central aspects of tgds, namely the role of existential quantifiers, has not seen much investigation so far. When studying dependencies, existential quantifiers and -- in their Skolemized form -- function symbols are often viewed as two ways to express the same concept. But in fact, tgds are quite restrictive in the way that functional terms can occur.
In this paper, we investigate the role of function symbols in dependency formalisms that go beyond tgds. Among them is the powerful class of SO tgds and the intermediate class of nested tgds. In addition, we employ Henkin quantifiers -- a well-known concept in the area of logic -- and introduce Henkin tgds to gain a more fine-grained understanding of the role of function symbols in dependencies.
For members of these families of dependency classes, we investigate their expressive power, that is, when one dependency class is equivalently representable in another class of dependencies. In addition, we analyze the computability of query answering under many of the well-known syntactical decidability criteria for tgds as well as the complexity of model checking
Semantic acyclicity under constraints
Full text linkA conjunctive query (CQ) is semantically acyclic if it is equivalent to an acyclic one. Semantic acyclicity has been studied in the constraint-free case, and deciding whether a query enjoys this property is NP-complete. However, in case the database is subject to constraints such as tuple-generating dependencies (tgds) that can express, e.g., inclusion dependencies, or equality-generating dependencies (egds) that capture, e.g., functional dependencies, a CQ may turn out to be semantically acyclic under the constraints while not semantically acyclic in general. This opens avenues to new query optimization techniques. In this paper we initiate and develop the theory of semantic acyclicity under constraints. More precisely, we study the following natural problem: Given a CQ and a set of constraints, is the query semantically acyclic under the constraints, or, in other words, is the query equivalent to an acyclic one over all those databases that satisfy the set of constraints? We show that, contrary to what one might expect, decidability of CQ containment is a necessary but not sufficient condition for the decidability of semantic acyclicity. In particular, we show that semantic acyclicity is undecidable in presence of full tgds (i.e., Datalog rules). In view of this fact, we focus on the main classes of tgds for which CQ containment is decidable, and do not capture the class of full tgds, namely guarded, non-recursive and sticky tgds. For these classes we show that semantic acyclicity is decidable, and its complexity coincides with the complexity of CQ containment. In the case of egds, we show that semantic acyclicity is undecidable even over unary and binary predicates. When restricted to keys the problem becomes decidable (NP-complete) over such schemas. We finally consider the problem of evaluating a semantically acyclic query over a database that satisfies a set of constraints. For guarded tgds the evaluation problem is tractable. © Association Computing for Machiner
On directly mapping relational databases to property graphs
Full text link\u3cp\u3eMuch of the data found in practice resides in relational DBs. However, many contemporary analytical tasks are performed on graphs. Property graphs are currently one of the most prevalent data models for graph data management in industry. Therefore, a key challenge is to understand the fundamental relationships between relational databases and property graph databases. This paper reports our ongoing work towards understanding these relationships by proposing R2PG-DM, a direct mapping of relational databases to property graphs. Given a relational database schema and instance, a direct mapping generates a corresponding property graph instance. The semantics of our mapping is defined using Datalog. Our work is inspired by existing approaches for direct mappings of relational databases into earlier graph data models. Future work is to study our mapping with respect to fundamental properties such as information and query preservation.\u3c/p\u3
Default Negation for Non-Guarded Existential Rules
No full textThe problem of query answering under the well-founded and stable model semantics for normal existential rules, that is, existential rules enriched with default negation, has recently attracted a lot of interest from the database and KR communities. In particular, it has been thoroughly studied for classes of normal existential rules that are based on restrictions that guarantee the tree-likeness of the underlying models; a prime example of such a restriction is guardedness. However, little is known about classes of existential rules that significantly deviate from the above paradigm. A prominent example of such a formalism is the class of existential rules that is based on the notion of stickiness, which enforces restrictions on the forms of joins in the rule-bodies. It is the precise aim of the current work to extend sticky existential rules with default negation, and perform an in-depth analysis of the complexity of conjunctive query answering under the well-founded and stable model semantics. We show that an effective way for bridging the gap between stickiness and the well-founded semantics exists, and we provide data and combined complexity results. However, there is no way to reconcile stickiness and the stable model semantics. The reason for this surprising negative result should be found in the fact that sticky existential rules are powerful enough for expressing cartesian products, a construct that forms a prime example of non-guardedness
Efficient Evaluation and Approximation of Well-designed Pattern Trees
No full textConjunctive queries (CQs) fail to provide an answer when the pattern described by the query does not exactly match the data. CQs might thus be too restrictive as a querying mechanism when data is semistructured or incomplete. The semantic web therefore provides a formalism - known as well-designed pattern trees (WDPTs) - that tackles this problem: WDPTs allow us to match patterns over the data, if available, but do not fail to give an answer otherwise. Here we abstract away the specifics of semantic web applications and study WDPTs over arbitrary relational schemas. Our language properly subsumes the class of CQs. Hence, WDPT evaluation is intractable. We identify structural proper ties of WDPTs that lead to tractability of various variants of the evaluation problem. For checking if a WDPT is equivalent to one in our tractable class, we prove 2EXPTIME-membership. As a corollary, we obtain fixed-parameter tractability of (variants of) the evaluation problem. Our techniques also allow us to develop a theory of approximations for WDPTs
On directly mapping relational databases to property graphs
No full textMuch of the data found in practice resides in relational DBs. However, many contemporary analytical tasks are performed on graphs. Property graphs are currently one of the most prevalent data models for graph data management in industry. Therefore, a key challenge is to understand the fundamental relationships between relational databases and property graph databases. This paper reports our ongoing work towards understanding these relationships by proposing R2PG-DM, a direct mapping of relational databases to property graphs. Given a relational database schema and instance, a direct mapping generates a corresponding property graph instance. The semantics of our mapping is defined using Datalog. Our work is inspired by existing approaches for direct mappings of relational databases into earlier graph data models. Future work is to study our mapping with respect to fundamental properties such as information and query preservation.</p
- …
