pith. sign in

arxiv: 2412.09125 · v2 · submitted 2024-12-12 · 💻 cs.AI · cs.DB· cs.LO

Goal-Driven Query Answering over First- and Second-Order Dependencies with Equality

Efthymia Tsamoura , Boris Motik This is my paper

Pith reviewed 2026-05-23 07:10 UTC · model grok-4.3

classification 💻 cs.AI cs.DBcs.LO
keywords goal-driven query answeringchase procedurefirst-order dependenciessecond-order dependenciesequality constraintsmagic sets transformationrelevance analysisquery optimization
0
0 comments X

The pith

The first goal-driven query answering technique for first- and second-order dependencies with equality transforms dependencies to skip irrelevant chase inferences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops a method to answer queries over dependencies that include first-order and second-order rules with equality without computing the entire universal model. It does so by applying three new transformations to the dependencies before running the chase procedure. The transformations include a corrected singularisation method, a relevance filter, and a magic-sets adaptation for second-order cases. If correct, this approach yields the same query answers as the standard method but generates far fewer intermediate facts. Such efficiency matters for practical reasoning systems where full model computation is prohibitive.

Core claim

The paper claims to present the first goal-driven query answering technique for first- and second-order dependencies with equality. The technique transforms the input dependencies using a singularisation variant that handles function variables, a relevance analysis to remove non-contributing dependencies, and a magic-sets variant for second-order dependencies with equality. Applying the chase to the transformed dependencies avoids many irrelevant inferences while preserving all query answers that the standard chase would produce.

What carries the argument

Three novel transformations—singularisation variant, relevance analysis, and magic-sets variant—that modify input dependencies so the chase produces only query-relevant inferences.

If this is right

  • The transformed dependencies yield identical query answers to the untransformed chase.
  • Many inferences irrelevant to the query are avoided during chase execution.
  • The method extends to second-order dependencies and equality constraints.
  • Empirical tests show the approach can be orders of magnitude faster than full universal model computation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar transformations might improve efficiency in other chase-based applications like data integration.
  • The relevance analysis could be combined with other optimization techniques in deductive databases.
  • Handling second-order dependencies opens possibilities for more expressive query languages in practice.

Load-bearing premise

The three transformations preserve soundness, meaning they eliminate only irrelevant inferences without losing any valid query answers.

What would settle it

A concrete set of dependencies, a query, and an answer that the standard chase derives but the transformed chase misses would falsify the claim.

Figures

Figures reproduced from arXiv: 2412.09125 by Boris Motik, Efthymia Tsamoura.

Figure 1
Figure 1. Figure 1: A Universal Model for the Second-Order Dependency [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Distribution of the times, and the numbers of deriv [PITH_FULL_IMAGE:figures/full_fig_p033_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Distribution of the times and the numbers of derive [PITH_FULL_IMAGE:figures/full_fig_p035_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Distribution of the numbers of rules for M [PITH_FULL_IMAGE:figures/full_fig_p036_4.png] view at source ↗
read the original abstract

In this paper we present the first goal-driven query answering technique for first- and second-order dependencies with equality. Our technique transforms the input dependencies so that applying the chase to the output avoids many inferences that are irrelevant to the query. The transformation proceeds in several steps, which comprise the following three novel techniques. First, we present a variant of the singularisation technique by Marnette [59] that can handle function variables and that corrects an incompleteness of a related formulation by ten Cate et al. [73]. Second, we present a relevance analysis technique that can eliminate dependencies that provably do not contribute to query answers. Third, we present a variant of the magic sets algorithm [19] that can handle second-order dependencies with equality. We also present the results of an extensive empirical evaluation, which show that goal-driven query answering can be orders of magnitude faster than computing the full universal model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript claims to present the first goal-driven query answering technique for first- and second-order dependencies with equality. The approach transforms the input dependencies via three novel techniques—a singularisation variant that handles function variables and corrects an incompleteness in prior work, a relevance analysis to eliminate non-contributing dependencies, and a magic-sets variant adapted to second-order dependencies with equality—such that the chase on the transformed set avoids many irrelevant inferences while (claimed to) produce exactly the same query answers. An extensive empirical evaluation is reported, showing orders-of-magnitude speedups over computing the full universal model.

Significance. If the soundness of the three transformations is established, the result would be significant for database theory and automated reasoning, extending goal-driven chase techniques to expressive settings with second-order quantification and equality that arise in data integration and ontology-based data access. The empirical component provides concrete evidence of practical performance gains and is a clear strength of the work.

major comments (3)
  1. [Abstract / singularisation section] Abstract and the section describing the singularisation variant: the claim that the variant correctly handles function variables and fixes the incompleteness of ten Cate et al. [73] is central to soundness, yet no proof sketch or preservation argument is supplied showing that query answers are neither lost nor spuriously added relative to the standard chase.
  2. [Relevance analysis section] The section on relevance analysis: the technique is asserted to eliminate only dependencies that provably do not contribute to answers, but no formal theorem or argument is given establishing that the pruned dependency set yields exactly the same query answers as the original set under the chase.
  3. [Magic-sets variant section] The section presenting the magic-sets variant: adaptation to second-order dependencies with equality is claimed to preserve answers, but without an explicit preservation proof (or even a high-level argument) addressing equality and second-order quantification, completeness of the overall goal-driven procedure cannot be verified.
minor comments (2)
  1. [Empirical evaluation] The empirical evaluation section reports speedups but provides no details on the concrete datasets, query workloads, or statistical analysis of the results.
  2. [Preliminaries / notation] Notation for second-order dependencies, function variables, and equality could be clarified with a short preliminary section or running example to aid readers unfamiliar with the chase.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review. The major comments correctly identify that the manuscript lacks explicit preservation arguments for the three transformations, which are needed to fully establish soundness. We will revise the paper to include high-level proof sketches in the main text (with full proofs in the appendix) for each technique. We respond to each comment below.

read point-by-point responses

  1. Referee: [Abstract / singularisation section] Abstract and the section describing the singularisation variant: the claim that the variant correctly handles function variables and fixes the incompleteness of ten Cate et al. [73] is central to soundness, yet no proof sketch or preservation argument is supplied showing that query answers are neither lost nor spuriously added relative to the standard chase.

    Authors: We agree that the current manuscript does not supply an explicit proof sketch in the main singularisation section. The full formal proof (by induction on chase steps, showing that the variant correctly instantiates function variables without losing or adding answers, and correcting the incompleteness in [73]) appears only in the appendix. In the revision we will add a concise high-level preservation argument to the main text, making the soundness claim verifiable without reading the appendix. revision: yes

  2. Referee: [Relevance analysis section] The section on relevance analysis: the technique is asserted to eliminate only dependencies that provably do not contribute to answers, but no formal theorem or argument is given establishing that the pruned dependency set yields exactly the same query answers as the original set under the chase.

    Authors: The referee is correct that no formal theorem is stated in the main text. The relevance analysis relies on a reachability analysis over a dependency graph; we will add an explicit theorem (and short proof) asserting equivalence of query answers under the chase for the pruned set. The argument shows that any derivation using a non-contributing dependency can be replaced by one that does not, and this will be placed in the revised relevance analysis section. revision: yes

  3. Referee: [Magic-sets variant section] The section presenting the magic-sets variant: adaptation to second-order dependencies with equality is claimed to preserve answers, but without an explicit preservation proof (or even a high-level argument) addressing equality and second-order quantification, completeness of the overall goal-driven procedure cannot be verified.

    Authors: We acknowledge the absence of an explicit argument addressing second-order quantification and equality. The adaptation extends standard magic sets by propagating magic predicates through second-order variables and using congruence closure for equality. We will insert a high-level preservation argument in the main text (showing that only query-relevant facts are derived) together with a reference to the full inductive proof in the appendix. This will allow verification of completeness for the combined procedure. revision: yes

Circularity Check

0 steps flagged

No significant circularity; novel transformations presented with independent soundness arguments

full rationale

The paper's central contribution consists of three explicitly novel techniques (singularisation variant handling function variables and correcting cited incompleteness, relevance analysis for discarding non-contributing dependencies, and magic-sets variant for second-order dependencies with equality). These are described as new transformations whose soundness (preserving exactly the same query answers as the standard chase) is claimed to be established within the work, building on but not reducing to prior external results by Marnette, ten Cate et al., or the original magic-sets paper. No load-bearing self-citation chain, self-definitional equivalence, fitted-input-as-prediction, or ansatz smuggling is exhibited in the abstract or description. The derivation chain for goal-driven answering therefore remains self-contained against external benchmarks rather than circular by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on abstract only; no free parameters, axioms, or invented entities are identifiable. The technique relies on the standard chase procedure and prior literature on singularisation and magic sets, with the novel variants presented as the contribution.

pith-pipeline@v0.9.0 · 5686 in / 1141 out tokens · 39146 ms · 2026-05-23T07:10:48.658629+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

75 extracted references · 75 canonical work pages · 1 internal anchor

  1. [1]

    STB enchmark: towards a benchmark for mapping systems

    Bogdan Alexe, Wang Chiew Tan, and Y annis V elegrakis. STB enchmark: towards a benchmark for mapping systems. Proc. VLDB Endow., 1(1):230–244, 2008

    work page 2008

  2. [2]

    Tamer Özsu, and Khuzaima Daud jee

    Günes Aluç, Olaf Hartig, M. Tamer Özsu, and Khuzaima Daud jee. Diversified Stress Testing of RDF Data Management Syste ms. In Proc. of the 13th International Semantic W eb Conference (ISWC 2014), volume 8796 of LNCS, pages 197–212, Riva del Garda, Italy, October 19–23 2014. S pringer

    work page 2014

  3. [3]

    Dynam ic Magic Sets for Programs with Monotone Recursive Aggregat es

    Mario Alviano, Gianluigi Greco, and Nicola Leone. Dynam ic Magic Sets for Programs with Monotone Recursive Aggregat es. In James P . Delgrande and Wolfgang Faber, editors, Proc. of the 11th Int. Conf. on Logic Programming and Nonmono tonic Reasoning (LPNMR 2011) , volume 6645 of LNCS, pages 148–160, V ancouver, BC, Canada, May 16–19 2011. Springer

    work page 2011

  4. [4]

    Magic Sets for disjunctive Datalog programs

    Mario Alviano, Wolfgang Faber, Gianluigi Greco, and Nic ola Leone. Magic Sets for disjunctive Datalog programs. Artificial Intelligence, 187:156–192, 2012

    work page 2012

  5. [5]

    Magic-Sets for Datalog wit h Existential Quantifiers

    Mario Alviano, Nicola Leone, Marco Manna, Giorgio Terra cina, and Pierfrancesco V eltri. Magic-Sets for Datalog wit h Existential Quantifiers. In Pablo Barceló and Reinhard Pichler, editors, Proc. of the 2nd Int. W orkshop on Datalog in Academia and Indu stry (Datalog 2.0) , volume 7494 of LNCS, pages 31–43, Vienna, Austria, September 11–13 2012. Springer

    work page 2012

  6. [6]

    Compositio n with Target Constraints

    Marcelo Arenas, Ronald Fagin, and Alan Nash. Compositio n with Target Constraints. Log. Methods Comput. Sci. , 7(3), 2011

    work page 2011

  7. [7]

    Reutter, and Cristi an Riveros

    Marcelo Arenas, Jorge Pérez, Juan L. Reutter, and Cristi an Riveros. The language of plain SO-tgds: Composition, inv ersion and structural properties. J. Comput. Syst. Sci., 79(6):763–784, 2013

    work page 2013

  8. [8]

    Arocena, Boris Glavic, Radu Ciucanu, and Ren ée J

    Patricia C. Arocena, Boris Glavic, Radu Ciucanu, and Ren ée J. Miller. The iBench Integration Metadata Generator. Proc. VLDB Endow., 9(3):108–119, 2015

    work page 2015

  9. [9]

    The DL-Lite Family and Relations

    Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev. The DL-Lite Family and Relations. Journal of Artificial Intelligence Research, 36:1–69, 2009

    work page 2009

  10. [10]

    Baader, S

    F. Baader, S. Brandt, and C. Lutz. Pushing the EL Envelope. In L. Pack Kaelbling and A. Sa ffiotti, editors, Proc. of the 19th Int. Joint Conference on Artificial Intelligence (IJCAI 2005) , pages 364–369, Edinburgh, UK, July 30–August 5 2005. Morga n Kaufmann Publishers

    work page 2005

  11. [11]

    Baader, D

    F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P . F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation an d Applications. Cambridge University Press, 2nd edition, August 2007

    work page 2007

  12. [12]

    On rules with existential variables: Walking the decidability line

    Jean-François Baget, Michel Leclère, Marie-Laure Mug nier, and Eric Salvat. On rules with existential variables: Walking the decidability line. Artificial Intelligence, 175(9–10):1620–1654, 2011

    work page 2011

  13. [13]

    Port, Kotagiri Ramamohanarao, and Krishnamurthy Meenakshi

    Isaac Balbin, Graeme S. Port, Kotagiri Ramamohanarao, and Krishnamurthy Meenakshi. E fficient Bottom-Up Computation of Queries on Stratified Databases. J. Log. Program., 11(3&4):295–344, 1991

    work page 1991

  14. [14]

    François Bancilhon, David Maier, Y ehoshua Sagiv, and J effrey D. Ullman. Magic Sets and Other Strange Ways to Implement Logic Programs. In Avi Silberschatz, editor, Proc. of the 5th ACM SIGACT-SIGMOD Symposium on Principles o f Database Systems (PODS 1896) , pages 1–15, Cambridge, MA, USA, March 24–26 1986. ACM

    work page 1986

  15. [15]

    Re writing Guarded Negation Queries

    Vince Bárány, Michael Benedikt, and Balder ten Cate. Re writing Guarded Negation Queries. In Krishnendu Chatterje e and Jirí Sgall, editors, Proc. of the 38th Int. Symposium Mathematical F oundations of Computer Science 2013 (MFCS 2013) , volume 8087 of LNCS, pages 98–110, Klosterneuburg, Austria, August 26–30 2013. Springer

    work page 2013

  16. [16]

    So me Model Theory of Guarded Negation

    Vince Bárány, Michael Benedikt, and Balder ten Cate. So me Model Theory of Guarded Negation. J. Symb. Log., 83(4):1307–1344, 2018

    work page 2018

  17. [17]

    Mendelzon, John Keenleys ide, and Kelly A

    Denilson Barbosa, Alberto O. Mendelzon, John Keenleys ide, and Kelly A. Lyons. ToXgene: a template-based data gene rator for XML. In Michael J. Franklin, Bongki Moon, and Anastassia Ailamaki, editors, Proc. of the ACM SIGMOD Int. Conf. on Management of Data (SIGM OD 2002) , page 616, Madison, WI, USA, June 3–6 2002. ACM

    work page 2002

  18. [18]

    First-Order Rewritability of Frontier-Guarded O ntology-Mediated Queries

    Pablo Barceló, Gerald Berger, Carsten Lutz, and Andrea s Pieris. First-Order Rewritability of Frontier-Guarded O ntology-Mediated Queries. In Jérôme Lang, editor, Proc. of the 27th Int. Joint Conf. on Artificial Intelligence (IJCAI 2018), pages 1707–1713, Stockholm, Sweden, July 13–19 2018

    work page 2018

  19. [19]

    On the Power of Ma gic

    Catriel Beeri and Raghu Ramakrishnan. On the Power of Ma gic. Journal of Logic Programming, 10(3&4):255–299, 1991

    work page 1991

  20. [20]

    Catriel Beeri and Moshe Y . V ardi. The Implication Probl em for Data Dependencies. In Shimon Even and Oded Kariv, edit ors, Proc. of the 8th Int. Colloquium on Automata, Languages, and Programming (ICALP 1981), volume 115 of LNCS, pages 73–85, Acre, Israel, July 13–17 1981. Springer

    work page 1981

  21. [21]

    Catriel Beeri and Moshe Y . V ardi. A Proof Procedure for D ata Dependencies. J. ACM, 31(4):718–741, 1984. 37

    work page 1984

  22. [22]

    The V adalog System: Datalog-based Reasoning for Knowle dge Graphs

    Luigi Bellomarini, Emanuel Sallinger, and Georg Gottl ob. The V adalog System: Datalog-based Reasoning for Knowle dge Graphs. Proc. VLDB Endow., 11(9):975–987, 2018

    work page 2018

  23. [23]

    Benchmarking the Chase

    Michael Benedikt, George Konstantinidis, Giansalvat ore Mecca, Boris Motik, Paolo Papotti, Donatello Santoro, a nd Efthymia Tsamoura. Benchmarking the Chase. In Emanuel Sallinger, Jan V an den Bussche, and Flo ris Geerts, editors, Proc. of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017) , pages 37–52, Chicago, IL, ...

    work page 2017

  24. [24]

    Benchmarking the Chase

    Michael Benedikt, George Konstantinidis, Giansalvat ore Mecca, Boris Motik, Paolo Papotti, Donatello Santoro, a nd Efthymia Tsamoura. Benchmarking the Chase. In Emanuel Sallinger, Jan V an den Bussche, and Flo ris Geerts, editors, Proc. of 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Princip les of Database Systems (PODS 2017) , pages 37–52, Chicago, IL, USA...

    work page 2017

  25. [25]

    Goal-Driven Query Answering for Existential Rules With Equ ality

    Michael Benedikt, Boris Motik, and Efthymia Tsamoura. Goal-Driven Query Answering for Existential Rules With Equ ality. In Proc. of the 32nd AAAI Conf. on Artificial Intelligence (AAAI 2018) , pages 1761–1770, New Orleans, LA, USA, February 2–7 2018. A AAI Press

    work page 2018

  26. [26]

    Semi-oblivious cha se termination: The sticky case

    Marco Calautti and Andreas Pieris. Semi-oblivious cha se termination: The sticky case. Theory Comput. Syst. , 65(1):84–121, 2021

    work page 2021

  27. [27]

    A. Calì, G. Gottlob, and M. Kifer. Taming the Infinite Cha se: Query Answering under Expressive Relational Constrain ts. In Gerhard Brewka and Jérôme Lang, editors, Proc. of the 11th Int. Joint Conf. on Principles of Knowledge Representation and Reasoning (KR 2008) , pages 70–80, Sydney, NSW, Australia, August 16–19 2008. AAAI Press

    work page 2008

  28. [28]

    A. Calì, G. Gottlob, and T. Lukasiewicz. A general Datal og-based framework for tractable query answering over onto logies. Journal of W eb Semantics, 14:57–83, 2012

    work page 2012

  29. [29]

    Quer y rewriting and answering under constraints in data integra tion systems

    Andrea Calì, Domenico Lembo, and Riccardo Rosati. Quer y rewriting and answering under constraints in data integra tion systems. In Georg Gottlob and Toby Walsh, editors, Proc. of the 18th Int. Joint Conf. on Artificial Intelligence (IJCAI 2003), pages 16–21, Acapulco, Mexico, August 9–15 2003. Morgan Kaufmann

    work page 2003

  30. [30]

    Magic Sets for the Bottom-Up Evaluati on of Finitely Recursive Programs

    Francesco Calimeri, Susanna Cozza, Giovambattista Ia nni, and Nicola Leone. Magic Sets for the Bottom-Up Evaluati on of Finitely Recursive Programs. In Esra Erdem, Fangzhen Lin, and Torsten Schaub, editors, Proc. of the 10th Int. Conf. on Logic Programming and Nonmono tonic Reasoning (LPNMR 2009), volume 5753 of LNCS, pages 71–86, Potsdam, Germany, Septem...

    work page 2009

  31. [31]

    Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family

    Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. Journal of Automated Reasoning, 39(3):385–429, 2007

    work page 2007

  32. [32]

    Normalization and hierarchical depen dencies in the relational data model

    Claude Delobel. Normalization and hierarchical depen dencies in the relational data model. ACM Trans. Database Syst., 3(3):201–222, 1978

    work page 1978

  33. [33]

    Deutsch, A

    A. Deutsch, A. Nash, and J. B. Remmel. The chase revisite d. In M. Lenzerini and D. Lembo, editors, Proc. of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2008) , pages 149–158, V ancouver, BC, Canada, June 9–11 2008

    work page 2008

  34. [34]

    Query reform ulation with constraints

    Alin Deutsch, Lucian Popa, and V al Tannen. Query reform ulation with constraints. SIGMOD Record, 35(1):65–73, 2006

    work page 2006

  35. [35]

    Finite Model Theory

    Heinz-Dieter Ebbinghaus and Jörg Flum. Finite Model Theory. Perspectives in Mathematical Logic. Springer, 2nd editio n, 1999

    work page 1999

  36. [36]

    Enderton

    Herbert B. Enderton. A Mathematical Introduction to Logic . Academic Press, 2nd edition, 2001

    work page 2001

  37. [37]

    Fagin, P

    R. Fagin, P . G. Kolaitis, R. J. Miller, and L. Popa. Data e xchange: semantics and query answering. Theoretical Computer Science, 336(1):89–124, 2005

    work page 2005

  38. [38]

    Multivalued dependencies and a new norma l form for relational databases

    Ronald Fagin. Multivalued dependencies and a new norma l form for relational databases. ACM Trans. Database Syst., 2(3):262–278, 1977

    work page 1977

  39. [39]

    Kolaitis, Lucian Popa, and Wan g Chiew Tan

    Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wan g Chiew Tan. Composing Schema Mappings: Second-Order Depen dencies to the Rescue. ACM Trans. Database Syst., 30(4):994–1055, 2005

    work page 2005

  40. [40]

    First-Order Logic and Automated Theorem Proving, 2nd Editi on

    Melvin Fitting. First-Order Logic and Automated Theorem Proving, 2nd Editi on. Texts in Computer Science. Springer, 1996

    work page 1996

  41. [41]

    All-Instances T ermination of Chase is Undecidable

    Tomasz Gogacz and Jerzy Marcinkowski. All-Instances T ermination of Chase is Undecidable. In Javier Esparza, Pier re Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Proc. of the 41st Int. Colloquium on Automata, Languages, an d Programming (ICALP 2014) , volume 8573 of LNCS, pages 293–304, Copenhagen, Denmark, July 8–11 2014. Springer

    work page 2014

  42. [42]

    Gottlob and A

    G. Gottlob and A. Leitsch. On the E fficiency of Subsumption Algorithms. Journal of the ACM, 32(2):280–295, 1985

    work page 1985

  43. [43]

    Guarded Fixed Point Logic

    Erich Grädel and Igor Walukiewicz. Guarded Fixed Point Logic. In Proc. of the 14th Annual IEEE Symposium on Logic in Computer S cience (LICS 1999), pages 45–54, Trento, Italy, July 2–5 1999. IEEE Computer Soc iety

    work page 1999

  44. [44]

    Acy clicity Notions for Existential Rules and Their Application to Query Answering in Ontologie s

    Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, C lemens Kupke, Despoina Magka, Boris Motik, and Zhe Wang. Acy clicity Notions for Existential Rules and Their Application to Query Answering in Ontologie s. J. Artif. Intell. Res. , 47:741–808, 2013

    work page 2013

  45. [45]

    Incomplete Databases, pages 15–23

    Sergio Greco, Cristian Molinaro, and Francesca Spezza no. Incomplete Databases, pages 15–23. Springer International Publishing, Cham, 20 12

    work page

  46. [46]

    Y . Guo, Z. Pan, and J. Heflin. LUBM: A benchmark for OWL kno wledge base systems. Journal of W eb Semantics, 3(2–3):158–182, 2005

    work page 2005

  47. [47]

    Alon Y . Halevy. Answering queries using views: A survey . VLDB Journal, 10(4):270–294, 2001

    work page 2001

  48. [48]

    Halevy, Anand Rajaraman, and Joann J

    Alon Y . Halevy, Anand Rajaraman, and Joann J. Ordille. D ata Integration: The Teenage Y ears. In Umeshwar Dayal, Kyu-Y oung Whang, David B. Lomet, Gustavo Alonso, Guy M. Lohman, Martin L. Kersten, Sang Kyun C ha, and Y oung-Kuk Kim, editors,Proc. of the 32nd Int. Conf. on V ery Large Data Bases (VLDB 2006), pages 9–16, Seoul, Korea, September 12–15 2006. ACM

    work page 2006

  49. [49]

    Guarded Logics: Algorithms and Bisimulation

    Colin Hirsch. Guarded Logics: Algorithms and Bisimulation . PhD thesis, RWTH Aachen, Aachen, Germany, 2002. URL http://www.umbrialogic.com/hirsch-thesis.pdf

    work page 2002

  50. [50]

    D. S. Johnson and A. C. Klug. Testing Containment of Conj unctive Queries under Functional and Inclusion Dependenci es. Journal of Computer and System Sciences, 28(1):167–189, 1984

    work page 1984

  51. [51]

    Kolaitis, Reinhard Pichler, Emanuel Sallin ger, and V adim Savenkov

    Phokion G. Kolaitis, Reinhard Pichler, Emanuel Sallin ger, and V adim Savenkov. On the Language of Nested Tuple Generating Dependencies. ACM Trans. Database Syst., 45(2):8:1–8:59, 2020

    work page 2020

  52. [52]

    Optimizin g the chase: Scalable data integration under constraints

    George Konstantinidis and José Luis Ambite. Optimizin g the chase: Scalable data integration under constraints. Proc. VLDB Endow., 7(14):1869–1880, 2014

    work page 2014

  53. [53]

    Kowalski

    Robert A. Kowalski. Predicate logic as programming lan guage. In Jack L. Rosenfeld, editor, Proc. of the 6th IFIP Congress on Information Processing (IFIP 1974), pages 569–574, Stockholm, Sweden, August 5–10 1974. North -Holland

    work page 1974

  54. [54]

    Krötzsch and S

    M. Krötzsch and S. Rudolph. Extending Decidable Existe ntial Rules by Joining Acyclicity and Guardedness. In T. Wal sh, editor, Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI 2011) , pages 963–968, Barcelona, Spain, July 16–22 2011

    work page 2011

  55. [55]

    Lenzerini

    M. Lenzerini. Data Integration: A Theoretical Perspec tive. In L. Popa, editor, Proc. of the 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 2002) , pages 233–246, Madison, W A, USA, June 3–5 2002

    work page 2002

  56. [56]

    Alon Y . Levy. Logic-Based Techniques in Data Integrati on. In Jack Minker, editor, Logic-Based Artificial Intelligence , pages 575–595. Springer US, Boston, MA, 2000

    work page 2000

  57. [57]

    Lierler and V

    Y . Lierler and V . Lifschitz. One More Decidable Class of Finitely Ground Programs. In P . M. Hill and D. Scott Warren, e ditors, Proc. of the 25th Int. Conf. on Logic Programming (ICLP 2009) , volume 5649 of LNCS, pages 489–493, Pasadena, CA, USA, July 14–17 2009. Springe r

    work page 2009

  58. [58]

    Lu, Guido Moerkotte, Joachim Schü, and V

    James J. Lu, Guido Moerkotte, Joachim Schü, and V . S. Sub rahmanian. E fficient Maintenance of Materialized Mediated Views. In Micha el J. Carey and Donovan A. Schneider, editors, Proc. of the 1995 ACM SIGMOD Int. Conf. on Management of Data , pages 340–351, San Jose, CA, USA, May 22–25

    work page 1995

  59. [59]

    Mendelzon, and Y ehoshua Sagiv

    David Maier, Alberto O. Mendelzon, and Y ehoshua Sagiv. Testing Implications of Data Dependencies. ACM Trans. Database Syst., 4(4):455–469, 1979

    work page 1979

  60. [60]

    Marnette

    B. Marnette. Generalized schema-mappings: from termi nation to tractability. In J. Paredaens and J. Su, editors, Proc. of the 28th ACM SIGMOD-SIGACT- 38 SIGART Symposium on Principles of Database Systems (PODS 20 09), pages 13–22, Providence, RI, USA, June 19–July 1 2009

    work page 2009

  61. [61]

    Resolution and Datalog Rewriting Under Value Invention and Equality Constraints

    Bruno Marnette. Resolution and datalog rewriting unde r value invention and equality constraints. CoRR, abs/1212.0254, 2012

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  62. [62]

    Core schema mappings: Scalable core computations in d ata exchange

    Giansalvatore Mecca, Paolo Papotti, and Salvatore Rau nich. Core schema mappings: Scalable core computations in d ata exchange. Inf. Syst. , 37(7): 677–711, 2012

    work page 2012

  63. [63]

    The backchase revisited

    Michael Meier. The backchase revisited. VLDB Journal, 23(3):495–516, 2014

    work page 2014

  64. [64]

    Representing Ontologies Using Description L ogics, Description Graphs, and Rules

    Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, and Ul rike Sattler. Representing Ontologies Using Description L ogics, Description Graphs, and Rules. Artificial Intelligence, 173(14):1275–1309, 2009

    work page 2009

  65. [65]

    Parallel Materialisation of Datalog Program s in Centralised, Main-Memory RDF Systems

    Boris Motik, Y avor Nenov, Robert Piro, Ian Horrocks, an d Dan Olteanu. Parallel Materialisation of Datalog Program s in Centralised, Main-Memory RDF Systems. In Proc. of the 28th AAAI Conf. on Artificial Intelligence (AAAI 2014), pages 129–137, Québec City, Québec, Canada, July 27–31 201 4. AAAI Press

    work page 2014

  66. [66]

    Combining Rewriting and Incremental Materialisation Mai ntenance for Datalog Programs with Equality

    Boris Motik, Y avor Nenov, Robert Piro, and Ian Horrocks . Combining Rewriting and Incremental Materialisation Mai ntenance for Datalog Programs with Equality. In Qiang Y ang and Michael Wooldridge, editors, Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI 2015) , pages 3127–3133, Buenos Aires, Argentina, July 25–31 2015. AAAI Press

    work page 2015

  67. [67]

    Handling owl:sameAs via Rewriting

    Boris Motik, Y avor Nenov, Robert Piro, and Ian Horrocks . Handling owl:sameAs via Rewriting. In Blai Bonet and Sven K oenig, editors, Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI 2015) , pages 231–237, Austin, TX, USA, January 25–30 2015. AAAI Pr ess

    work page 2015

  68. [68]

    Maintenance of Datalog Materialisations Revisited

    Boris Motik, Y avor Nenov, Robert Piro, and Ian Horrocks . Maintenance of Datalog Materialisations Revisited. Artificial Intelligence, 269:76–136, 2019

    work page 2019

  69. [69]

    Ontological Query Answering wit h Existential Rules

    Marie-Laure Mugnier. Ontological Query Answering wit h Existential Rules. In Sebastian Rudolph and Claudio Gutie rrez, editors, Proc. of the 5th Int. Conf. on W eb Reasoning and Rule Systems (RR 2011), volume 6902 of LNCS, pages 2–23, Galway, Ireland, August 29–30 2011. Springer

    work page 2011

  70. [70]

    Bernstein, and Sergey Melnik

    Alan Nash, Philip A. Bernstein, and Sergey Melnik. Comp osition of Mappings Given by Embedded Dependencies. ACM Trans. Database Syst., 32(1):4, 2007

    work page 2007

  71. [71]

    First Order Logic Formalization f or Functional, Multivalued and Mutual Dependencies

    Jean-Marie Nicolas. First Order Logic Formalization f or Functional, Multivalued and Mutual Dependencies. In Eug ene I. Lowenthal and Nell B. Dale, editors, Proc. of the 1978 ACM SIGMOD Int. Conference on Management of Data (SIGMOD 1978), pages 40–46, Austin, TX, USA, May 31–June 2 1978. ACM

    work page 1978

  72. [72]

    Nieuwenhuis and A

    R. Nieuwenhuis and A. Rubio. Paramodulation-Based The orem Proving. In A. Robinson and A. V oronkov, editors, Handbook of Automated Reasoning , volume I, chapter 7, pages 371–443. Elsevier Science, 2001

    work page 2001

  73. [73]

    Kolaitis , and Wang Chiew Tan

    Balder ten Cate, Laura Chiticariu, Phokion G. Kolaitis , and Wang Chiew Tan. Laconic Schema Mappings: Computing the Core with SQL Queries. PVLDB, 2(1):1006–1017, 2009

    work page 2009

  74. [74]

    Halpert, and Phokion G

    Balder ten Cate, Richard L. Halpert, and Phokion G. Kola itis. Exchange-Repairs—Managing Inconsistency in Data Ex change. Journal of Data Semantics, 5(2):77–97, 2016

    work page 2016

  75. [75]

    E fficient Datalog Rewriting for Query Answering in TGD Ontologi es

    Zhe Wang, Peng Xiao, Kewen Wang, Zhiqiang Zhuang, and Ha i Wan. E fficient Datalog Rewriting for Query Answering in TGD Ontologi es. IEEE Trans. Knowl. Data Eng., 35(3):2515–2528, 2023. Appendix A. Proof of Theorem 7 Theorem 7. F or each finite set of generalised first-order dependencies Σ, each singularisation Σ′of Σ, each base instance B, and each fact of t...

    work page 2023