Efficient datalog rewriting for query answering in TGD ontologies

​

Wang, Zhe, Peng Xiao, Kewen Wang, Zhiqiang Zhuang, and Hai Wan.

​

1

Presented by Rucha Save for CSE 645: Seminar in Languages

Overview

• Introduction
• Motivation
• Contributions
• Compact Datalog rewriting Algorithm
• Termination condition class
• Conclusion
• Experiments and Evaluation

​

​

​

2

Introduction

3

• Ontology-mediated query answering
• TDG
• TDG ontology
• Query Rewriting

​

​

Ontology-mediated query answering

• Uses semantic knowledge expressed in ontologies to improve query answering over data.
• Allows user to formulate queries in a more familiar vocabulary which abstracts from the specific way data is stored.

​

​

​

​

4

OMQA techniques in medicine -

Patient has Hodgkin’s lymphoma, and takes a drug for hypertension

​

Query to find cancer patients being treated for high-blood pressure

Ontology

Cancer : Hodgkin’s lymphoma,....

high-blood pressure : hypertension,...

No results

OMQA systems will perform the necessary inferences in order to obtain all (deducible) answers to the query.

Ontology contains a hierarchy of terms, from highly specialized to generic, and the semantic relationships

​

• TGD:

Constraint on a relational database

TGD σ over a schema R

∀X.∀Y.[∃Z.φ(X, Z) ← ψ(X, Y)]

Where,

X,Y,Z are pairwise disjoint vectors of variables X∪Y∪Z⊂V

φ(X,Z)andψ(X,Y)are conjunctions of atoms over R containing only variables from respectively X ∪ Z and X ∪ Y

• TGD Ontology:

Query answering over ontologies expressed by means of tuple-generating dependencies (TGDs)

​

​

​

​

​

5

Tgds are used to define schema mappings in data exchange, to describe how data structured under one schema (the source schema) is to be transformed into data structured under a second schema (the target schema).

​

Query Rewriting

Step 1:

Encode the relevant information from ontology into the query.

Step 2:

Evaluate query over the data using a database system.

​

​

​

​

6

Original Query

Database

Ontology

Encode the relative information

Evaluate query over the database

Query rewriting Algo

​

1. Can be given to existing database system to get the results.
2. It should preserve the results to original queries.

Motivation

7

• Existing query rewriting systems for existential rules are typically based on first-order rewritings
• The results of rewriting can suffer from a huge blow up and hence it becomes difficult for existing DBMS to handle the re-written the query.
• Datalog query rewriting can be much more compact.
• Existing research on Datalog rewriting of TGDs are mostly theoretical.

8

​

Conjunctive query:

q(x) = ∃y.ancestor(y,x)

Ontology with existential rules:

∃y.ancestor(y,x)← man(x),

ancestor(x,y)←ancestor(x,z)⋀ ancestor(z,y)

​

​

​

Datalog rewriting q

Q(x)←ancestor(y,x), Q(x)←man(x),

Q(x) ←man(z)^ancestor(z,x),

ancestor(x,y)←ancestor(x,z) ∧ ancestor(z,y)

First-order rewriting q

∃y.ancestor(y,x) v man(x) v ∃y∃z.[ancestor(y,z)^ancestor(z,x)] ν ∃z.[man(z) ^ancestor(z,x)] v . . . . .

Every man X has ancestor Y

Person x who has ancestor Y

Ref : https://www.ijcai.org/proceedings/2020/video/26707 around 1.42 mins

Contributions

​

• A compact datalog rewriting approach
• Identified several existing and new datalog rewritable classes
• An efficient implementation and experimental evaluation using prototype system Drewer.

9

Compact Datalog rewriting

​

• Notion of unfolding - split long datalog rules into compact ones

head(ρ)τ ← Λ(body(ρ) \ B)τ ∧ Λ body(σ)τ.

Splitting the datalog rules into two:

head(ρ)τ ← Λ(body(ρ) \ B)τ ∧ P(X), (1)

P(X) ← Λ body(σ)τ, (2)

where X = (Xρ ∪ Vbody(ρ)\B )τ ∩ Xσ τ , and P is a fresh predicate with arity |X|, called a separating predicate. Here the separating predicate is a unary one.

​

​

​

​

10

Compact Datalog rewriting

​

• Result of unfolding :

P(X) ← Λ body(σ)τ,

head(ρ)τ ← Λ(body(ρ) \ B)τ ∧ P(X)

• Unfold: Q(x) ←man(z) ⋀ ancestor(z,x)

By: ancestor(z,x) ← ancestor(z,w)⋀ ancestor(w,x)

Results: Q(x) ←man(z) ⋀ ancestor(z,w)⋀ ancestor(w,x)

Results: Q(x) ← man(z) ⋀ P(z,x), and

P(z,x) ← ancestor(z,w)⋀ ancestor(w,x)

​

Ref : https://www.ijcai.org/proceedings/2020/video/26707 around 4.16 mins

​

​

​

​

11

Compact Datalog rewriting

​

​

• Q(x,y) ← A(x,y) ⋀ A(y,z)

By: r1 : ∃y.A(y,z) ← B(y), and r2:B(y)← A(w,y),

Results: r3:Q(x,y)←A(x,y) ⋀ P(y), r4:P(y)← B(y),

r5:Q(x,y) ← A(x,y) ⋀ B(y),

r6:Q(x,y) ← A(x,y) ⋀ P’(y), r7:P’(y)← A(w,y),

r8:Q(x,y) ← A(x,y) ⋀ A(w,y),

r9:Q(x,y) ← P(x), r10:P(x)← B(x),

r11:Q(x,y) ← B(x).

Note: P is reused for termination.

Note: auxiliary rules can be removed at the end.

​

Ref : https://www.ijcai.org/proceedings/2020/video/26707 around 6.44 mins

​

​

​

12

A New Rewritable Class

​

Correctness: For an OMQ Σq , rew(Σq ) is a Datalog rewriting of Σq whenever rew(Σq) is finite.

• The results of rewriting is always finite if auxiliary rules are not kept.
• If the rewriting of the body atoms can be done separately, then auxiliary rules are not needed.
• There are different classes for the rewriting termination

​

​

​

​

13

The Finite unification sets(FUS)

​

• It is known that the unfolding of a CQ always terminates on the class of finite unification sets(FUS) of TGDs.
• Authors proves that the their Datalog rewriting terminates for FUS too.

For an OMQ Σq whose ontology is FUS, rew(Σq ) is finite.

​

​

​

14

The Separable Class

​

• Many common Datalog rewritable ontologies are not in FUS
• Ontology satisfying transitivity: A(X,Y)←A(X,Z) ⋀ A(Z,Y), is not FUS because the rewriting of the above rule doesn’t terminate due to infinitely many auxiliary rules are generated.
• An ontology Σ is separable if for any atom query,the rewriting is still correct without generating auxiliary rules.
• The class of separable ontologies is sep.

​

​

​

15

The Shy Class

​

• Two atoms in the same rule body are chained if
• They share a variable that is attacked
• They each contains a frontier variable and these two variables are both attacked by the same variable.
• An existing class called Shy: if it does not contain two chained atoms.
• In forward chaining, no existential variable propagates into one join variable or into two variables occurring in the same head.
• Shy ⊂ Sep

​

​

16

The Block Finite Class

​

• The class of separate ontologies still cannot cover some useful Datalog rewritable cases.
• A block is set of body atoms that may be inseparable in rewriting.
• For a Datalog rule ρ, its block separation, denoted bsep(ρ), consists of the following Datalog rules

head(ρ)← Λ P_B (X_B), B is a block in body(ρ)

P_B (X_B ) ←Λ B, for each block B in body(ρ)

• Each rule with a non-empty body contains at least one block
• For an OMQ Σq, rewbs(Σq) is a Datalog rewriting of Σq whenever rewbs(Σq) is finite.

​

​

​

​

17

Comparison with State-of-the-art Systems

• TO - timeout

​

18

Graal - A first-order rewriting systems for general TGDs,

Rapid, Grind - Datalog rewriting systems for description logic ontologies. In particular,

Iqaros - A first-order rewriting system for OWL2 ontologies featuring in its rewriting minimisation.

​

Comparison with State-of-the-art Systems

• TO - timeout

​

19

Compared with existing query answering system for evaluation on overall Query answering

​

• Different benchmark are LUBM, DEEP,ONT- 256,STB-128,Adolena,LUBM
• Drewer performs the best for all increasing data sizes, ontology sizes, and query lengths.

​

20

Comparison with State-of-the-art Systems

Conclusions

• Proposed an efficient datalog rewriting approach for answering conjunctive queries over existential rules, and identify and combine existing fragments of existential rules(TGD) for which our rewriting method terminates.
• Experiments show that Drewer(bsep- rewriting and checker to identify the specific class such as Shy and BExp) is able to handle a wide range of benchmarks in the literature and its at par in compactness of rewriting and the efficiency of query answering with other state-of-the-art systems.

​

21

References

• Original Paper – Wang, Zhe, Peng Xiao, Kewen Wang, Zhiqiang Zhuang, and Hai Wan. "Efficient datalog rewriting for query answering in TGD ontologies." IEEE Transactions on Knowledge and Data Engineering (2021).
• Z. Wang, P. Xiao, K. Wang, Z. Zhuang, and H. Wan, “Query answering for existential rules via efficient datalog rewriting,” in Proc. of IJCAI-20, 2020, pp. 1933–1939.
• https://link.springer.com/referenceworkentry/10.1007/978-0-387-39940-9_1274

​

​

22

Thank you.

23