XML Schema Mappings: Data Exchange

XML Schema Mappings: Data Exchange and Metadata Management 12:13
PROPOSITION 4.3. The data complexity of tree patterns evaluation is LOGSPACEcomplete,
and the combined complexity is in PTIME.
Let us go back to mappings. If an interpretation of function symbols is fixed, the
membership problem amounts to evaluating a single pattern. Fix a tree S, a mapping
M = (Ds, Dt, ) with no variables introduced on the target side, and a valuation F of
function symbols inM. Consider the following valuated tree pattern
δS,M,F =

{ψ( ¯a)|ϕ( ¯x, ¯y) −→ ψ( ¯x) ∈ and (S, F) |= ϕ( ¯a, ¯b)} . (3)
Its size is bounded by M · |S| M . A straightforward check gives the following.
LEMMA 4.4. T is a solution for S under M with the witnessing valuation F if and
only if T |= Dt and (T, F) |= δS,M,F.
The complexity of XML mappings is quite high, but it matches that of relational
mappings with Skolem functions [Fagin et al. 2004; Pichler and Skritek 2011]. We
strengthen the lower bounds a bit by showing hardness for mappings without joins.
THEOREM 4.5. For schema mappings from SM(⇓,⇒,∼, Fun), MEMBERSHIP is
NEXPTIME-complete, and MEMBERSHIP(M) is always in NP. Moreover, we get matching
lower bounds in both cases already for relational mappings with Skolem functions, but
without ∼.
PROOF. Let us first see that MEMBERSHIP is in NEXPTIME. Let M be a mapping,
and let S and T be the source and target trees. Checking conformance to DTDs can
be done in PTIME. Let us concentrate on dependencies. Denote by A the set of data
values used in S or in T. As usually, we can assume that no variables are introduced
on the target side of the constraints. By Lemma 4.4, T is a solution for S if there
exists a valuation F of function symbols such that (T, F) |= δS,M,F. In order to compute
and evaluate δS,M,F, it suffices to know the values of all subterms occurring in the
definition (3). Their number can be bounded by N = M · |S| M . The algorithm nondeterministically
chooses for each of those subterms a value from A∪ {⊥1,⊥2, . . . ,⊥N},
where ⊥i are distinct fresh values, checks that the obtained valuation is consistent with
the structure of the terms, computes δS,M,F and evaluates it on T. By Proposition 4.3,
all this can be done in time polynomial in N and the size of the input.
To show hardness, we will provide a reduction from the following NEXPTIME-hard
tiling problem [Papadimitriou 1994]: Given a finite list of tile types T = t0, t1, . . . , tk
together with horizontal and vertical adjacency relations H, V ⊆ T 2 and a number
n in unary, decide if there exists a tiling of the 2n × 2n-grid such that a t0 tile occurs
in the top left position, a tk tile occurs in the bottom right position, and all adjacency
relationships are respected.
We give a reduction to the relational case. Hardness for XML follows via the standard
reduction. We make additional effort to avoid using joins in the mappings.
Take an instance of the tiling problem. The source instance is
{False(0), True(1), Eq(0, 0), Eq(1, 1)} ∪ {Ni(0, 1, ... , 1
i−1
, 1, 0, ... , 0
i−1
)|i = 1, 2, . . . , n}
and the target instance contains the adjacency relations H and V together with
{B(t0), E(tk)}. Let us now define the set of dependencies. Intuitively, we encode tiles as
values of a function f . The tile on position (i, j) is encoded as f (ibin jbin). We need to
check the adjacency relations. This can be done because we can express incrementation
Journal of the ACM, Vol. 61, No. 2, Article 12, Publication date: April 2014.
12:14 S. Amano et al.
on n-bit words. For each j = 1, 2, . . . n add dependencies
Eq(x1, u1), . . . , Eq(xj , uj ), Eq(y1, v1), . . . , Eq(yn, vn)
Nn−j (xj+1, . . . , xn, uj+1, . . . , un)
−→ H( f ( ¯x, ¯y), f ( ¯u, ¯ v)) ,
Eq(x1, u1), . . . , Eq(xn, un), Eq(y1, v1), . . . , Eq(yj, vj )
Nn−j (yj+1, . . . , yn, vj+1, . . . , vn)
−→ V( f ( ¯x, ¯y), f ( ¯u, ¯ v)) .
We also need to check that we begin and end properly:
False(x1), . . . , False(xn), False(y1), . . . , False(yn) −→ B( f ( ¯x, ¯y)) ,
True(x1), . . . , True(xn), True(y1), . . . , True(yn) −→ E( f ( ¯x, ¯y)) .
In terms of data complexity, the algorithm described above is in NP: the size
of δS,M,F is polynomial for every fixed mapping. Let us now prove hardness. Recall
that if we replace the 2n × 2n-grid with the n × n-grid in the tiling problem
considered above, we end up with an NP-complete problem. The idea of the reduction
from this new problem to MEMBERSHIP(M) is the same as in the reduction
above, and the implementation is even simpler. As the source instance we take
{B(1), E(n), Eq(1, 1), Eq(2, 2), . . . , Eq(n, n), N(1, 2), N(2, 3), . . . , N(n − 1, n)}. The target
instance is just like before. The dependencies are
N(x, u), Eq(y, v) −→ H( f (x, y), f (u, v)) , B(x), B(y) −→ B( f (x, y)) ,
N(x, u), Eq(y, v) −→ V( f (y, x), f (v, u)) , E(x), E(y) −→ E( f (x, y)) .
It is routine to verify the correctness of the reduction.
The main source of hardness are Skolem functions. The first reduction above uses
function symbols of unbounded arity, but they can be easily encoded with binary functions
by using either nested terms or equality. If we bound the arity of terms (the total
number of occurrences of variables) and forbid explicit equalities between terms (repetition
of variables is allowed), the combined complexity drops to the third level of the
polynomial hierarchy. The data complexity is not affected, since the mappings used in
the second reduction above satisfy these restrictions. Complete proof of the following
result is in the appendix.
THEOREM 4.6. For schema mappings from SM(⇓,⇒,∼, Fun) with bounded arity of
terms and no explicit equality, MEMBERSHIP is
p
3 -complete, and the lower bound holds
already for relational mappings without ∼.
If we forbid Skolem functions altogether, the data complexity of mappings drops very
low, but combined complexity is still complete for the second level of the polynomial
hierarchy, like in the relational case [Gottlob and Senellart 2010]. If we additionally
bound the number of variables in dependencies, even combined complexity is polynomial.
THEOREM 4.7. For schema mappings from SM(⇓,⇒,∼), MEMBERSHIP(M) is
LOGSPACE-complete, while MEMBERSHIP is 
p
2-complete in general and in PTIME if
the maximum number of variables per pattern is fixed.
PROOF.
(1) Conformance to a fixed DTD can be checked in LOGSPACE. It remains to show
that we can check LOGSPACE if S and T satisfy a single constraint ϕ( ¯x, ¯y) −→ ψ( ¯x, ¯z).
Let ¯x = x1, x2, . . . , xk, ¯y = y1, y2, . . . , y, and ¯z = z1, z2, . . . , zm. Let A be the set of data
values used in S or T. We need to check that for each ¯a ∈ Ak and each ¯b ∈ A such that
S |= ϕ( ¯a, ¯b) there exists ¯ c ∈ Am such that T |= ψ( ¯a, ¯ c). Since the numbers k, ,m are
fixed (as parts of the fixed mapping), the space needed for storing all three valuations
Journal of the ACM, Vol. 61, No. 2, Article 12, Publication date: April 2014.
XML Schema Mappings: Data Exchange and Metadata Management 12:15
is logarithmic in the size of S and T. Using Proposition 4.3, we obtain a LOGSPACE
algorithm by simply iterating over all possible valuations ¯a, ¯b, and ¯c. LOGSPACEhardness
follows from Proposition 4.3.
(2) First, let us see that the problem is in 
p
2 . Consider the following algorithm for
the complementary problem: guess a constraint ϕ( ¯x, ¯y) −→ ψ( ¯x, ¯z) and a valuation ¯a, ¯b
of variables used in ϕ, and check that S |= ϕ( ¯a, ¯b) and T |= ψ( ¯a, ¯z). By Proposition 4.3,
the first check is polynomial. The second check however involves a tree pattern possibly
containing free variables, so it can only be done in coNP. Altogether the algorithm is in

p
2 . The 
p
2 lower bound for relational mappings using neither Skolem functions nor
equality [Gottlob and Senellart 2010] carries over to SM(↓) via the standard encoding.
The original reduction can be obtained as a natural modification of the one from
Theorem 4.6.
(3) Proceed just like in (1). The number of variables per pattern is bounded, so there
are only polynomially many possible valuations. Hence, we may iterate over all of them
using algorithm from Proposition 4.3 to check S |= ϕ( ¯a, ¯b) and T |= ψ( ¯a, ¯ c).
5. QUERY ANSWERING
5.1. Query Answering Problem
The fundamental problem of data exchange is answering queries over target data
in a way consistent with the source data. Inspired by the research on the relational
case [Barcel´o 2009; Fagin et al. 2005; Kolaitis 2005], we study query answering for
conjunctive queries and their unions. Conjunctive queries over trees are normally
represented with tree patterns [Gottlob et al. 2006, Bj¨orklund et al. 2008, 2011]. Thus,
for querying XML documents, we use the same language as for the dependencies: tree
patterns augmented with equalities as well as inequalities, to capture the analog of
relational conjunctive queries with inequalities. And, of course, we allow projection.
That is, a query is an expression of the form
∃ ¯x ϕ ,
where ϕ is a pattern using no function symbols, such that each free variable satisfies
the safety condition (see Definition 3.1). The semantics is defined in the standard way.
The output of the query is the set of those valuations of free variables that make the
query hold true. This class of queries is denoted by CTQ (conjunctive tree queries). Note
that CTQ is indeed closed under conjunctions, due to the semantics of λ, λ
 in patterns.
We also consider unions of such queries: UCTQ denotes the class of queries of the
form Q1( ¯x)∪· · ·∪Qm( ¯x), where each Qi is a query from CTQ. Like for schema mappings,
we write CTQ(σ) and UCTQ(σ) for σ ⊆ { ↓, ↓+
,→,→+
,=, =} to denote the subclass
of queries using only the symbols from σ.
Consider a source DTD Ds
europe → country∗ country : @name
country → ruler∗ ruler : @name
and a target DTD Dt
rulers → ruler∗ ruler : @name
ruler → successor successor : @name
Assuming the r

ผลลัพธ์ (ไทย) 1:

แมป XML Schema: แลกเปลี่ยนข้อมูลและจัดการข้อมูลเมตา 12:13ข้อเสนอที่ 4.3 ข้อมูลความซับซ้อนของการประเมินรูปแบบแผนภูมิเป็น LOGSPACEcompleteและซับซ้อนรวมอยู่ใน PTIMEให้เรากลับไปแมป ถ้าคงที่ตีความสัญลักษณ์ฟังก์ชัน การจำนวนสมาชิกปัญหาเพื่อประเมินรูปแบบเดียว แก้ไขแผนภูมิ S การแมปM = (Ds, Dt,) กับไม่มีตัวแปรที่นำมาใช้ในด้านเป้าหมาย และค่า F ของฟังก์ชันสัญลักษณ์ inM พิจารณารูปแบบแผนภูมิ valuated ต่อไปนี้ΔS, M, F ={∈ψ (¯a) |ϕ (¯x, ¯y) −→ψ (¯x) และ (S, F) | =ϕ (¯a, ¯b) } (3)ขนาดถูกล้อมรอบ โดย M · |S| ม. เครื่องหมายถูกตรงไปตรงมาให้ต่อไปนี้จับมือ 4.4 T เป็นโซลูชันสำหรับ S ใต้ M มีค่า witnessing F ถ้า และรับ T | = Dt และ (T, F) | = δS, M เอฟความซับซ้อนของแมป XML จะค่อนข้างสูง แต่มันตรงกับที่เกี่ยวข้องแม็ปกับฟังก์ชัน Skolem [Fagin et al. 2004 Pichler ก Skritek 2011] เราเสริมขอบเขตล่างเล็กน้อย โดยแสดงความแข็งสำหรับการแม็ปโดยรวมทฤษฎีบท 4.5 สำหรับแบบแผนการแมปจาก SM (⇓ ⇒ ∼ สนุก), เป็นสมาชิกทำ NEXPTIME และ MEMBERSHIP(M) ได้เสมอใน NP นอกจากนี้ เราได้รับการจับคู่ขอบเขตล่างในทั้งสองกรณีสำหรับแมปเชิงด้วยฟังก์ชั่น Skolem แล้ว แต่ไม่∼หลักฐานการ ให้เราครั้งแรกเห็นว่า เป็นสมาชิกใน NEXPTIME ให้ M เป็นการแม็ปและให้ S และ T เป็นต้นแหล่งที่มาและเป้าหมาย ตรวจสอบความสอดคล้องกันเพื่อสามารถ DTDsทำ PTIME ให้เรามีสมาธิในการอ้างอิง แสดง โดย A ชุดของข้อมูลค่าใช้ S หรือต. เป็นปกติ เราสามารถสมมติว่า ตัวแปรไม่มีการแนะนำทางด้านเป้าหมายของข้อจำกัด โดยจับมือ 4.4, T เป็นโซลูชันสำหรับ S ถ้ามีมีค่า F เช่นสัญลักษณ์ฟังก์ชันนั้น (T, F) | = δS, M เอฟ การคำนวณและประเมิน δS, M, F มัน suffices ต้องทราบค่าของ subterms ทั้งหมดที่เกิดขึ้นในการคำจำกัดความ (3) หมายเลขสามารถล้อมรอบ ด้วย N M · = |S| ม. อัลกอริทึม nondeterministicallyเลือกสำหรับแต่ละของ subterms ที่ได้ค่าจาก A∪ {⊥1, ⊥2,..., ⊥N },⊥i มีค่าสด ตรวจสอบว่าค่าที่ได้รับสอดคล้องกับโครงสร้างของเงื่อนไข δS, M, F คำนวณ และประเมินในต. 4.3 โดยเสนอทั้งหมดนี้สามารถทำได้ในเวลาโพลิโนเมีย N และขนาดของข้อมูลป้อนเข้าแสดงความแข็ง เราจะให้ลดจาก NEXPTIME ฮาร์ดดิสก์ต่อไปนี้ปัญหาการเรียง [Papadimitriou 1994]: กำหนดรายการจำกัดกระเบื้องชนิด T = t0, t1,..., ทีเคกับความสัมพันธ์แนวนอน และแนวตั้ง adjacency H ⊆ V T 2 และหมายเลขn ในเดี่ยว ตัดสินใจว่า ถ้า มีการเรียงตัวของ 2n × 2n-ตารางที่เกิดไพ่ t0ในตำแหน่งด้านซ้ายบน tk ไพ่เกิดขึ้นในตำแหน่งขวาล่าง และทั้งหมด adjacencyความสัมพันธ์ยอมรับเราให้ลดคดีเกี่ยวข้องกัน ความแข็งสำหรับ XML ต่อไปนี้ผ่านมาตรฐานลด เราทำเพิ่มเติมพยายามหลีกเลี่ยงการใช้การรวมในการแม็ปใช้อินสแตนซ์ของปัญหาเรียง อินสแตนซ์แหล่งเป็น{ False(0), True(1), Eq (0, 0) Eq (1, 1) } ∪ { Ni (0, 1, 1,...i−1, 1, 0, ... , 0i−1)|i = 1, 2, . . . , n}ตัวอย่างเป้าหมายมีความสัมพันธ์ adjacency H และ V ร่วมกับ{B(t0), E(tk) } ให้เรากำหนดชุดของการอ้างอิง สังหรณ์ใจ เราเข้ากระเบื้องค่าของ f เป็นฟังก์ชัน ไพ่ตำแหน่งที่ (i, j) จะถูกเข้ารหัสเป็น f (ฉันช่องเก็บช่องเจ) เราจำเป็นต้องตรวจสอบความสัมพันธ์ของ adjacency นี้สามารถทำได้เนื่องจากเราสามารถที่แสดง incrementationสมุดรายวันของพลอากาศ 61 ปี หมายเลข 2 บทความ 12 วันเผยแพร่: 2014 เมษายน12:14 S. อะมะโนะ et alคำ n บิต สำหรับแต่ละ j = 1, 2,... n เพิ่มขึ้นEq (x 1, u1), ..., Eq (xj, uj) Eq (y1, v1), ..., Eq (yn วีเอ็น)Nn−j (xj 1,..., xn, uj + 1,..., สหประชาชาติ)−→ H (f (¯x, ¯y) f (¯u ¯ v)),Eq (x 1, u1), ..., Eq (xn สหประชาชาติ) Eq (y1, v1), ..., Eq (yj, vj)Nn−j (yj + 1,..., yn, vj + 1,..., วีเอ็น)−→ V (f (¯x, ¯y) f (¯u ¯ v))เราต้องตรวจสอบว่า เราเริ่มต้น และสิ้นสุดอย่างถูกต้อง:False(x1),..., False(xn), False(y1),..., False(yn) −→ B (f (¯x, ¯y)),True(x1),..., True(xn), True(y1),..., True(yn) −→ E (f (¯x, ¯y))ในความซับซ้อนของข้อมูล อัลกอริทึมที่อธิบายไว้ข้างต้นเป็น NP: ขนาดของ δS, M, F เป็นพหุนามสำหรับการแม็ปทุกคง เราพร้อมพิสูจน์ความแข็ง เรียกคืนซึ่งถ้าเราแทน 2n × 2n-ตาราง n × n เส้นในปัญหาการเรียงพิจารณาข้างต้น เราจบลงด้วยการมีปัญหาทำ NP ความคิดในการลดจากปัญหานี้ใหม่กับ MEMBERSHIP(M) เป็นเดียวกันกับการลดข้างต้น และใช้งานได้ง่ายขึ้น เป็นอินสแตนซ์แหล่งที่เราใช้{ B(1), E(n), Eq (1, 1) (2, 2) คณะกรรมการ, ..., Eq (n, n), N (1, 2) N (2, 3), ..., N (n − 1, n) } เป้าหมายอินสแตนซ์คือเหมือนก่อน มีการขึ้นต่อกันN (x, u) Eq (y, v) −→ H (f (x, y) f (u, v)), B(x), B(y) −→ B (f (x, y)),N (x, u) Eq (y, v) −→ V (f (y, x) f (v, u)), E(x), E(y) −→ E (f (x, y))เป็นประจำเพื่อตรวจสอบความถูกต้องของการลดแหล่งที่มาหลักของความแข็งมีฟังก์ชัน Skolem ใช้ลดแรกข้างต้นทำงานสัญลักษณ์ของ arity งที่ แต่พวกเขาจะได้เข้ารหัส ด้วยฟังก์ชั่นการไบนารีโดยใช้เงื่อนไขซ้อนกันหรือความเสมอภาค ถ้าเราผูก arity เงื่อนไข (รวมจำนวนการเกิดขึ้นของตัวแปร) และห้าม equalities ชัดเจนระหว่างเงื่อนไข (ซ้ำของตัวแปรได้), ความซับซ้อนรวมลดลงในระดับที่สามของการพหุนามลำดับชั้น ความซับซ้อนของข้อมูลจะไม่ได้รับผลกระทบ ตั้งแต่การแม็ปที่ใช้ในลดสองข้างตอบสนองข้อจำกัดเหล่านี้ หลักฐานที่สมบูรณ์ต่อไปนี้ผลคือในภาคผนวกทฤษฎีบท 4.6 การแม็ปเค้าร่างจาก SM (⇓ ⇒ ∼ สนุก) กับกี่ arity ของเงื่อนไขและความเสมอภาคไม่ชัดเจน เป็นสมาชิก p3 - สมบูรณ์ และด้านล่างผูกถือแล้วสำหรับแมปเชิงไม่∼ถ้าเราห้ามฟังก์ชัน Skolem ทั้งหมด ความซับซ้อนของข้อมูลการแม็ปหยดมากความซับซ้อนต่ำ แต่รวมเสร็จยังคงระดับสองของโพลิโนเมียลำดับชั้น เช่นในกรณีเชิง [Gottlob และ Senellart 2010] ถ้าเรานอกจากนี้ผูกกับหมายเลขของตัวแปรในการอ้างอิง แม้ที่รวมความซับซ้อนเป็นพหุนามทฤษฎีบท 4.7 เป็นการแม็ปเค้าร่างจาก SM(⇓,⇒,∼), MEMBERSHIP(M)LOGSPACE-สมบูรณ์ ในขณะที่สมาชิกp2-ดำเนินการทั่วไป และ PTIME ถ้าได้รับการแก้ไขจำนวนของตัวแปรต่อรูปแบบหลักฐานการ(1) ความสอดคล้องกันกับ DTD ถาวรสามารถเช็คอินได้ LOGSPACE ยังคงแสดงที่เราสามารถตรวจสอบ LOGSPACE ว่า S และ T ตามข้อจำกัดเดียวϕ (¯x, ¯y) −→ψ (¯x, ¯z)ให้ ¯x = x 1, x 2,..., xk, ¯y = y1, y2,..., y และ ¯z = z1, z2,..., zm ให้ A เป็นชุดของข้อมูลค่าใช้ใน S หรือต. เราต้องตรวจสอบว่าในแต่ละ ¯a ∈ Ak และแต่ละ ¯b ∈ A ให้S | =ϕ (¯a, ¯b) มี c ∈¯น.เช่นที่ T | =ψ (¯a ¯ c) ตั้งแต่หมายเลข k,, m เป็นถาวร (เป็นส่วนหนึ่งของการแม็ปถาวร), พื้นที่จำเป็นสำหรับจัดเก็บประเมินมูลค่าสามทั้งหมดสมุดรายวันของพลอากาศ 61 ปี หมายเลข 2 บทความ 12 วันเผยแพร่: 2014 เมษายนแมป XML Schema: แลกเปลี่ยนข้อมูลและจัดการข้อมูลเมตา 12:15คือลอการิทึมขนาด S และต.ใช้เสนอ 4.3 เราได้ LOGSPACEอัลกอริทึม โดยเพียงแค่วนซ้ำทั้งหมดประเมินมูลค่าได้ ¯a, ¯b และ ¯c. LOGSPACEhardnessดังนี้จาก 4.3 เสนอ(2) ก่อน ให้เราเห็นว่า ปัญหาในp2 อัลกอริทึมต่อไปนี้สำหรับพิจารณาปัญหาเพิ่มเติม: เดาเป็นข้อจำกัดϕ (¯x, ¯y) −→ψ (¯x, ¯z) และการประเมินค่า ¯a, ¯bตัวแปรที่ใช้ในϕ และตรวจสอบว่า | =ϕ (¯a, ¯b) และ T | =ψ (¯a, ¯z) 4.3 โดยเสนอเช็คใบแรกที่เป็นพหุนาม เครื่องที่สองแต่เกี่ยวข้องกับรูปแบบแผนภูมิอาจประกอบด้วยตัวแปรอิสระ ดังนั้นมันจะทำได้เท่าใน coNP ทั้งหมด อัลกอริทึมอยู่ในp2 ที่pขอบล่าง 2 สำหรับแมปเชิงฟังก์ชัน Skolem ไม่ใช้ หรือความเสมอภาค [Gottlob และ Senellart 2010] ดำเนินผ่านการ SM(↓) ผ่านมาตรฐานการเข้ารหัสลดเดิมได้เป็นการปรับเปลี่ยนได้จากธรรมชาติทฤษฎีบท 4.6(3) ดำเนินเช่นเดียวกับใน (1) จำนวนตัวแปรต่อลายล้อมรอบ จึงมีได้เฉพาะ polynomially หลายสามารถประเมินค่า ดังนั้น เราอาจทำซ้ำทั้งหมดของพวกเขาโดยใช้อัลกอริทึมจาก 4.3 เสนอเข้า S | =ϕ (¯a, ¯b) และ T | =ψ (¯a ¯ c)5. แบบสอบถามตอบ5.1 การถามตอบปัญหาปัญหาพื้นฐานของการแลกเปลี่ยนข้อมูลจะตอบแบบสอบถามผ่านข้อมูลเป้าหมายในลักษณะที่สอดคล้องกับแหล่งข้อมูล โดยงานวิจัยบนที่สัมพันธ์กันกรณี [Barcel´o 2009 Fagin et al. 2005 Kolaitis 2005], เราเรียนตอบในแบบสอบถามสอบถาม conjunctive และสหภาพของพวกเขา สอบถาม conjunctive ผ่านต้นไม้ได้ตามปกติแสดง ด้วยแผนภูมิรูปแบบ [Gottlob et al. 2006, Bj¨orklund et al. 2008, 2011] ดังนั้นสำหรับการสอบถามเอกสาร XML เราใช้ภาษาเดียวกันกับการอ้างอิง: แผนภูมิรูปแบบออกเมนต์ equalities เป็นความเหลื่อมล้ำทาง การจับภาพแบบแอนะล็อกของสอบถาม conjunctive เชิงที่ มีความเหลื่อมล้ำทาง และ แน่นอน เราอนุญาตให้ฉายกล่าวคือ แบบสอบถามคือ นิพจน์ของแบบฟอร์ม∃ ¯x ϕϕเป็น รูปแบบโดยใช้สัญลักษณ์ไม่ฟังก์ชัน ให้เป็นไปตามแต่ละตัวแปรอิสระเงื่อนไขความปลอดภัย (ดูข้อกำหนด 3.1) ความหมายกำหนดไว้ในแบบมาตรฐานผลลัพธ์ของแบบสอบถามเป็นชุดของที่ประเมินค่าของตัวแปรอิสระที่ต้องการแบบสอบถามถือจริง คลาสนี้ของแบบสอบถามสามารถระบุ โดย CTQ (conjunctive ทรีแบบสอบถาม) หมายเหตุCTQ ที่แท้ปิดใต้สันธาน เนื่องจากความหมายของλ λในรูปแบบการนอกจากนี้เรายังพิจารณาสหภาพเช่นแบบสอบถาม: UCTQ หมายถึงประเภทของแบบสอบถามของการไตรมาสที่ 1 (¯x) ∪·· ·∪Qm (¯x), แบบสอบถามจาก CTQ ชี่แต่ละ ต้องการแม็ปเค้าร่างเราเขียน CTQ(σ) และ UCTQ(σ) สำหรับ⊆σ {↓ ↓ +,→,→+, =, =} แสดงการย่อยแบบสอบถามโดยใช้สัญลักษณ์จากσเท่านั้นพิจารณาแหล่ง DTD Dsประเทศยุโรป→ country∗: @nameไม้บรรทัดประเทศ→ ruler∗: @nameและเป้าหมาย DTD Dtไม้บรรทัดไม้บรรทัด→ ruler∗: @nameไม้บรรทัด→สืบสืบ: @nameสมมติว่า r

ผลลัพธ์ (ไทย) 2:

XML Schema แมป: การแลกเปลี่ยนข้อมูลและการบริหารจัดการ Metadata 00:13
ข้อเสนอ 4.3 ความซับซ้อนของข้อมูลของการประเมินผลรูปแบบต้นไม้ LOGSPACEcomplete,
และความซับซ้อนรวมอยู่ใน Ptime.
ขอให้เรากลับไปที่แมป ถ้าแปลความหมายของสัญลักษณ์ฟังก์ชั่นได้รับการแก้ไข
ปัญหาที่เป็นสมาชิกมีจำนวนการประเมินรูปแบบเดียว แก้ไข S ต้นไม้, การทำแผนที่
M = (DS, DT) กับตัวแปรที่ไม่มีการแนะนำให้รู้จักในด้านเป้าหมายและ F การประเมินมูลค่าของ
สัญลักษณ์ฟังก์ชัน INM พิจารณาต่อไปนี้รูปแบบการประเมินต้นไม้
δS, M, F =
?
{ψ (A) | φ (x, y) - →ψ (x) ∈และ (S, F) | = φ (a, ¯ ข)} (3)
ขนาดของมันมีขอบเขตโดย M · | S | M ตรงไปตรงมาให้ตรวจสอบต่อไป.
บทแทรก 4.4 T เป็นโซลูชั่นสำหรับเอสเอ็มที่มีอยู่ภายใต้การประเมินค่า F พยานถ้าและ
เฉพาะในกรณีที่ T | = Dt และ (T, F) |. = δS, M, F
ความซับซ้อนของการแมป XML ค่อนข้างสูง แต่มันตรงกับที่เชิงสัมพันธ์
แมปที่มีฟังก์ชั่น Skolem [Fagin และคณะ 2004; Pichler และ Skritek 2011] เรา
เสริมสร้างขอบเขตที่ต่ำกว่าเล็กน้อยด้วยการแสดงความแข็งสำหรับการแมปโดยไม่ต้องร่วม.
ทฤษฎีบท 4.5 สำหรับแมปสคีมาจากเอสเอ็ม (⇓, ⇒ ~ สนุก) เป็นสมาชิก
NEXPTIME สมบูรณ์และการเป็นสมาชิก (M) อยู่เสมอใน NP นอกจากนี้เรายังได้รับการจับคู่
ขอบเขตที่ต่ำกว่าในทั้งสองกรณีแล้วสำหรับแมปสัมพันธ์กับการทำงาน Skolem แต่
โดยไม่ต้อง ~.
หลักฐาน ให้เราก่อนเห็นว่าเป็นสมาชิกใน NEXPTIME ให้ M เป็นการทำแผนที่
และปล่อยให้ S และ T เป็นแหล่งที่มาและต้นไม้เป้าหมาย การตรวจสอบความสอดคล้องกับ DTDs สามารถ
ทำได้ใน Ptime ขอให้เรามีสมาธิในการอ้างอิง แสดงว่าโดยชุดของข้อมูล
ค่าใช้ใน S หรือ T. ในฐานะที่เป็นปกติเราสามารถสรุปได้ว่าตัวแปรที่ไม่ได้ถูกนำเสนอ
ในด้านเป้าหมายของข้อ จำกัด โดยบทแทรก 4.4, T เป็นโซลูชั่นสำหรับ S ถ้ามี
อยู่ F การประเมินมูลค่าของสัญลักษณ์ดังกล่าวว่าฟังก์ชั่น (T, F) | = δS, M, F เพื่อที่จะคำนวณ
และประเมินδS, M, F ก็พอเพียงที่จะรู้คุณค่าของ subterms ทั้งหมดที่เกิดขึ้นใน
ความหมาย (3) จำนวนของพวกเขาสามารถกระโดดจากจำนวน = M · | S | M อัลกอริทึม nondeterministically
เลือกสำหรับแต่ละผู้ subterms ค่าจากA∪ {⊥1, ⊥2, . . , ⊥N}
ที่⊥iเป็นค่าที่แตกต่างสดตรวจสอบว่าการประเมินมูลค่าที่ได้รับมีความสอดคล้องกับ
โครงสร้างของข้อตกลงคำนวณδS, M, F และประเมินไว้ใน T. โดยโจทย์ 4.3
ทั้งหมดนี้สามารถทำได้ในเวลา พหุนามใน n และขนาดของอินพุต.
เพื่อแสดงความแข็งเราจะให้ลดลงจากต่อไปนี้ NEXPTIME ยาก
ปัญหาปูกระเบื้อง [Papadimitriou 1994]: กำหนดขอบเขตของรายการประเภทกระเบื้อง T = t0, t1, . . , TK?
ร่วมกับแนวนอนและแนวตั้งถ้อยคำความสัมพันธ์ H, V ⊆ T 2 และจำนวน
n ในเอกตัดสินใจถ้ามีการปูกระเบื้องของ 2n × 2n ตารางดังกล่าวว่ากระเบื้อง t0 เกิดขึ้น
อยู่ในตำแหน่งด้านบนซ้าย, TK กระเบื้องเกิดขึ้นในตำแหน่งที่เหมาะสมด้านล่างและถ้อยคำทั้งหมด
ความสัมพันธ์ที่มีความเคารพนับถือ.
เราให้ลดกรณีสัมพันธ์ ความแข็งสำหรับ XML ต่อไปนี้ผ่านมาตรฐาน
ลดลง เราทำให้ความพยายามที่จะหลีกเลี่ยงการใช้ร่วมในการแมป.
นำตัวอย่างของปัญหาการปูกระเบื้อง เช่นแหล่งที่มาเป็น
{เท็จ (0) ทรู (1), สมการ (0, 0), สมการ (1, 1)} ∪ {Ni (0, 1,.?.?. 1?
I-1
, ?.?.?. 1, 0, 0?
I-1
) | i = 1, 2, . . , n}
และเช่นเป้าหมายมีถ้อยคำความสัมพันธ์ H และ V พร้อมกับ
{B (t0), E (TK)} ให้เรากำหนดชุดการอ้างอิง สังหรณ์ใจเราเข้ารหัสกระเบื้องเป็น
ค่านิยมของฟังก์ชัน f กระเบื้องกับตำแหน่ง (I, J) จะถูกเข้ารหัสเป็น f (? i ถัง? J? ถัง) เราจำเป็นต้อง
ตรวจสอบความสัมพันธ์ของถ้อยคำ ซึ่งสามารถทำได้เพราะเราสามารถแสดงความ incrementation
วารสาร ACM ฉบับ 61, ฉบับที่ 2, มาตรา 12, วันที่ประกาศ: เมษายน 2014.
00:14 เอสอะมาโนะ et al.
คำ n บิต เพราะว่าแต่ละ = 1, 2, . . n เพิ่มการอ้างอิง
สมการ (x1, U1) . . , สมการ (XJ, uj) สมการ (y1, v1) . . , สมการ (YN, VN)
NN-J (XJ + 1,, xn, uj + 1, ยกเลิก......)
- → H (f (x, y), f (u, ¯ V)),
สมการ (x1, U1) . . , สมการ (xn ยกเลิก), สมการ (y1, v1) . . , สมการ (ยงจุน, vj)
NN-J (ยงจุน + 1,, YN, vj + 1,, VN......)
- → V (f (x, y), f (u, ¯ v.))
นอกจากนี้เรายังต้องตรวจสอบว่าเราจะเริ่มต้นและจบลงอย่างถูกต้อง:
เท็จ (x1) . . , เท็จ (xn) เท็จ (y1) . . , เท็จ (YN) - → B (f (x, y)),
ทรู (x1) . . ทรู (xn) ทรู (y1) . . ทรู (YN) - → E (f (x, y)).
ในแง่ของความซับซ้อนของข้อมูลขั้นตอนวิธีการที่อธิบายข้างต้นอยู่ใน NP: ขนาด
ของδS, M, F เป็นพหุนามสำหรับการทำแผนที่การแก้ไขทุก ให้เราตอนนี้พิสูจน์ความแข็ง จำได้
ว่าถ้าเราเปลี่ยน 2n × 2n ตารางที่มี n × n ตารางในปัญหาการปูกระเบื้อง
พิจารณาข้างต้นเราจบลงด้วยปัญหา NP-สมบูรณ์ ความคิดของการลดลง
จากปัญหาใหม่นี้ไปยังสมาชิก (M) เป็นเช่นเดียวกับในการลด
ข้างต้นและการดำเนินการเป็นได้ง่าย ในฐานะที่เป็นแหล่งที่มาเช่นเราใช้
{B (1), E (n) สมการ (1, 1), สมการ (2, 2), . . , สมการ (N, N) N (1, 2), (2, 3) . . , N (n - 1, n)} เป้าหมาย
เช่นเป็นเหมือนก่อน อ้างอิงเป็น
N (x, U), สมการ (Y v) - → H (f (x, y), f (U, V)), B (x), B (Y) - → B (f ( x, y)),
N (x, U), สมการ (Y v) - → V (f (y, x), f (V, U)), E (x), E (Y) - E → (f (x, y)).
มันเป็นกิจวัตรประจำวันในการตรวจสอบความถูกต้องของการลด.
แหล่งที่มาหลักของความแข็งที่มีฟังก์ชั่น Skolem การลดครั้งแรกดังกล่าวข้างต้นจะใช้
สัญลักษณ์การทำงานของ arity มากมาย แต่พวกเขาสามารถเข้ารหัสได้อย่างง่ายดายด้วยฟังก์ชั่นไบนารี
โดยใช้เงื่อนไขที่ซ้อนกันหรือความเท่าเทียมกัน ถ้าเราผูกพัน arity ของข้อตกลง (รวม
จำนวนของการเกิดขึ้นของตัวแปร) และห้ามสมอย่างชัดเจนระหว่างข้อกำหนด (ซ้ำ
ของตัวแปรที่ได้รับอนุญาต) ความซับซ้อนรวมลดลงถึงระดับที่สามของ
ลำดับชั้นของพหุนาม ความซับซ้อนของข้อมูลที่ไม่ได้รับผลกระทบเนื่องจากการแมปที่ใช้ใน
การลดสองข้างต้นตอบสนองข้อ จำกัด เหล่านี้ หลักฐานที่สมบูรณ์ต่อไปนี้
ผลที่ได้คือในภาคผนวก.
ทฤษฎีบท 4.6 สำหรับแมปสคีมาจากเอสเอ็ม (⇓, ⇒ ~ สนุก) กับ arity ขอบเขตของ
ข้อกำหนดและไม่มีความเท่าเทียมกันอย่างชัดเจน, เป็นสมาชิก
พี
3 ที่สมบูรณ์และขอบเขตที่ต่ำถือ
แล้วสำหรับแมปสัมพันธ์โดยไม่ต้อง ~.
ถ้าเราห้ามฟังก์ชั่น Skolem ทั้งหมด ความซับซ้อนของข้อมูลของแมปลดลงมาก
ต่ำ แต่ความซับซ้อนรวมยังคงเป็นที่ที่สมบูรณ์แบบสำหรับระดับที่สองของพหุนาม
ลำดับชั้นเช่นเดียวกับในกรณีสัมพันธ์ [Gottlob และ Senellart 2010] ถ้าเรายัง
ผูกพันจำนวนของตัวแปรในการอ้างอิงรวมแม้กระทั่งความซับซ้อนเป็นพหุนาม.
ทฤษฎีบท 4.7 สำหรับแมปสคีมาจากเอสเอ็ม (⇓, ⇒ ~), สมาชิก (M) เป็น
LOGSPACE สมบูรณ์ในขณะที่เป็นสมาชิก?
P
2 สมบูรณ์โดยทั่วไปและใน Ptime ถ้า
จำนวนสูงสุดของตัวแปรต่อรูปแบบได้รับการแก้ไข.
หลักฐาน.
(1 ) สอดคล้องกับ DTD คงที่สามารถตรวจสอบได้ใน LOGSPACE มันยังคงที่จะแสดงให้
เห็นว่าเราสามารถตรวจสอบ LOGSPACE ถ้า S และ T ตอบสนองข้อ จำกัด เดียวφ (x, y) -. →ψ (x, Z)
ให้ x = x1, x2, . . , XK, y = y1, y2, . . , y ?, และ Z = z1, z2, . . , ZM ให้เป็นชุดของข้อมูล
ค่าใช้ใน S หรือ T. เราจำเป็นต้องตรวจสอบว่าแต่ละ∈ Ak และแต่ละ∈ B? เช่นที่
S | = φ (A, B) มีอยู่¯ค∈ Am เช่นที่ T | = ψ (a, ¯ค) ตั้งแต่หมายเลข k,?, ม. จะ
คงที่ (เป็นส่วนหนึ่งของการทำแผนที่คงที่) พื้นที่ที่จำเป็นสำหรับการจัดเก็บทั้งสามการประเมินมูลค่า
วารสาร ACM ฉบับ 61, ฉบับที่ 2, มาตรา 12, วันที่ประกาศ: เมษายน 2014.
XML Schema แมป: การแลกเปลี่ยนข้อมูลและการบริหารจัดการ Metadata 12:15
เป็นลอการิทึมในขนาดของ S และ T. ใช้โจทย์ 4.3 เราได้รับ LOGSPACE
อัลกอริทึมโดยเพียงแค่การทำซ้ำมากกว่า การประเมินมูลค่าที่เป็นไปได้ทั้งหมด A, B, C และ LOGSPACEhardness
ต่อจากโจทย์ 4.3.
(2) แรกให้เราเห็นว่าปัญหาคืออะไรบ้าง?
P
2 พิจารณาขั้นตอนวิธีการต่อไปนี้สำหรับ
ปัญหาที่สมบูรณ์: เดา จำกัด φ (x, y) - →ψ (x, Z) และการประเมินมูลค่า A, B
ของตัวแปรที่ใช้ในการφและตรวจสอบว่า S | = φ (A, B) และ T? | = ψ (A, Z) โดยข้อเสนอที่ 4.3
ตรวจสอบครั้งแรกเป็นพหุนาม การตรวจสอบครั้งที่สอง แต่เกี่ยวข้องกับรูปแบบอาจจะเป็นต้นไม้
ที่มีตัวแปรอิสระเพื่อที่จะสามารถทำได้ใน CONP พรึบอัลกอริทึมที่อยู่ใน
?
P
2 ?
P
2 ขอบเขตที่ต่ำสำหรับการแมปเชิงสัมพันธ์โดยใช้ฟังก์ชั่นไม่ Skolem หรือ
ความเท่าเทียมกัน [Gottlob และ Senellart 2010] ดำเนินไปยังเอสเอ็ม (↓) ผ่านการเข้ารหัสมาตรฐาน.
ลดเดิมสามารถที่ได้รับการดัดแปลงเป็นธรรมชาติของคนที่จาก
ทฤษฎีบท 4.6
(3) ดำเนินการเช่นเดียวกับใน (1) จำนวนของตัวแปรต่อรูปแบบเป็นที่สิ้นสุดจึงมี
เพียง polynomially การประเมินมูลค่าที่เป็นไปได้มาก ดังนั้นเราอาจจะย้ำกว่าทั้งหมดของพวกเขา
โดยใช้อัลกอริทึมจากโจทย์ 4.3 การตรวจสอบ S | = φ (A, B) และ T |. = ψ (a, ¯ค)
5 ตอบแบบสอบถาม
5.1 คำที่จะตอบปัญหา
ปัญหาพื้นฐานของการแลกเปลี่ยนข้อมูลจะตอบแบบสอบถามมากกว่าข้อมูลเป้าหมาย
ในทางที่สอดคล้องกับข้อมูลแหล่งที่มา แรงบันดาลใจจากการวิจัยในเชิง
กรณี [Barcel'o 2009; Fagin และคณะ 2005; Kolaitis 2005] เราศึกษาการตอบแบบสอบถามสำหรับ
คำสั่งที่เชื่อมต่อและสหภาพแรงงานของพวกเขา คำสั่งเยื่อตากว่าต้นไม้เป็นปกติ
แทนด้วยรูปแบบต้นไม้ [Gottlob และคณะ 2006 Björklundและคณะ 2008, 2011] ดังนั้น
สำหรับการสอบถามเอกสาร XML เราจะใช้ภาษาเดียวกันกับการอ้างอิง: ต้นไม้
รูปแบบการเสริมเข้ากับสมการเช่นเดียวกับความไม่เท่าเทียมกันในการจับภาพแบบอะนาล็อกของ
คำสั่งที่เชื่อมสัมพันธ์กับความไม่เท่าเทียมกัน และแน่นอนเราอนุญาตให้ฉาย.
นั่นคือแบบสอบถามคือการแสดงออกของรูปแบบ
∃ x φ,
ที่φเป็นรูปแบบการใช้สัญลักษณ์ไม่ทำงานเช่นที่ตอบสนองแต่ละตัวแปรฟรี
สภาพความปลอดภัย (ดูความละเอียด 3.1) ความหมายที่กำหนดไว้ในวิธีการมาตรฐาน.
เอาท์พุทของแบบสอบถามคือชุดของการประเมินมูลค่าที่ของตัวแปรอิสระที่ให้
ระงับการสอบถามความจริง ชั้นเรียนของคำสั่งนี้จะแสดงโดย CTQ (คำสั่งต้นไม้ที่เชื่อมต่อ) หมายเหตุ
ที่ CTQ นี้ปิดให้บริการแน่นอนภายใต้สันธานเนื่องจากความหมายของλ, λ
? . ในรูปแบบ
นอกจากนี้เรายังพิจารณาสหภาพแรงงานของคำสั่งดังกล่าว UCTQ หมายถึงระดับของการค้นหาของ
ไตรมาสที่ 1 รูปแบบ (x) ∪···∪Qm (x) ซึ่งแต่ละฉีเป็นแบบสอบถามจาก CTQ เหมือนแมปคี
เราเขียน CTQ (σ) และ UCTQ (σ) สำหรับσ⊆ {↓, ↓ +
, →, → +
=? =} เพื่อแสดง subclass
ของแบบสอบถามโดยใช้สัญลักษณ์เท่านั้นจากσ.
พิจารณา แหล่ง DTD Ds
ยุโรป→ประเทศ * ประเทศ: @name
ประเทศ→ผู้ปกครองผู้ปกครอง *: @name
และเป้าหมาย DTD Dt
โมหะ→ไม้บรรทัด * ไม้บรรทัด: @name
ไม้บรรทัด→สืบทายาท: @name
สมมติ R

ผลลัพธ์ (ไทย) 3:

XML schema แมป : แลกเปลี่ยนข้อมูลและข้อมูลการจัดการ 12 : 13
ข้อเสนอ 4.3 . ความซับซ้อนของข้อมูลการประเมินรูปแบบต้นไม้ logspacecomplete
และความซับซ้อน , รวมอยู่ใน ptime .
ให้เรากลับไปแมป . ถ้าการตีความสัญลักษณ์ ฟังก์ชันการแก้ไขปัญหา
สมาชิก ยอดเงินประเมินรูปแบบเดียว แก้ไขของต้นไม้ , การทำแผนที่
M = ( DS , เปลี่ยน) ที่ไม่มีตัวแปรที่แนะนำในด้านเป้าหมายและค่าของฟังก์ชัน f
สัญลักษณ์ inm . พิจารณาตามรูปแบบการประเมินต้นไม้
δ S , M , F =

{ ψ ( ¯ ) | ϕ ( ¯ X , ¯ Y ) −→ψ ( ¯ X ) ∈และ ( S , F ) | = ϕ ( ¯ , ¯ b ) } ( 3 )
ขนาดของมันจะล้อมรอบด้วย m ด้วย | S | M . ตรวจสอบตรงไปตรงมาให้ต่อไปนี้
แทรก 4.4 . T เป็นโซลูชั่นสำหรับใน M กับ F ถ้าเห็นมูลค่าและ
only if T |= Dt and (T, F) |= δS,M,F.
The complexity of XML mappings is quite high, but it matches that of relational
mappings with Skolem functions [Fagin et al. 2004; Pichler and Skritek 2011]. We
strengthen the lower bounds a bit by showing hardness for mappings without joins.
THEOREM 4.5. For schema mappings from SM(⇓,⇒,∼, Fun), MEMBERSHIP is
NEXPTIME-complete,และสมาชิก ( M ) คือเสมอใน NP นอกจากนี้เราได้รับการจับคู่
ขอบเขตล่างในทั้งสองกรณีแล้วแมปสัมพันธ์กับฟังก์ชัน skolem แต่ไม่มี∼
.
พิสูจน์ เราพบว่าสมาชิกใน nexptime . ให้ M เป็นการทำแผนที่
และให้ S และ T เป็นแหล่งที่มาและต้นไม้เป้าหมาย การตรวจสอบดังกล่าวสามารถ dtds สามารถ
ทำ ptime . เรามุ่งเน้นการพึ่งพา . แสดงโดยชุดข้อมูล
values used in S or in T. As usually, we can assume that no variables are introduced
on the target side of the constraints. By Lemma 4.4, T is a solution for S if there
exists a valuation F of function symbols such that (T, F) |= δS,M,F. In order to compute
and evaluate δS,M,F, it suffices to know the values of all subterms occurring in the
definition (3).จำนวนของพวกเขาสามารถล้อมรอบด้วย n = m ด้วย | S | M . ขั้นตอนวิธี nondeterministically
เลือกสำหรับแต่ละของผู้ subterms ค่าจาก∪⊥⊥ { 1 , 2 , . . . . . . . . ⊥ n , } ,
ที่⊥ผมเป็นค่านิยมใหม่ที่แตกต่างกันการตรวจสอบที่ได้รับการประเมินสอดคล้องกับ
โครงสร้างของเงื่อนไข คำนวณδ S , M , F และประเมินมันที โดยข้อเสนอ 4.3
all this can be done in time polynomial in N and the size of the input.
To show hardness, we will provide a reduction from the following NEXPTIME-hard
tiling problem [Papadimitriou 1994]: Given a finite list of tile types T = t0, t1, . . . , tk
together with horizontal and vertical adjacency relations H, V ⊆ T 2 and a number
n in unary,ตัดสินใจว่า ถ้า มีการปูกระเบื้องของ 2 × 2 ตารางดังกล่าวที่ t0
กระเบื้องเกิดขึ้นในตำแหน่งซ้ายสุด ชิ้นกระเบื้องเกิดขึ้นในตำแหน่งขวาล่างและความสัมพันธ์ทั้งหมดจะนับถือถ้อยคำ
.
เราให้ลดกรณีสัมพันธ์ ความแข็งตามมาตรฐาน XML ผ่านการ

เราทำให้เพิ่มเติมความพยายามที่จะหลีกเลี่ยงการใช้ร่วมในการแมป .
Take an instance of the tiling problem. The source instance is
{False(0), True(1), Eq(0, 0), Eq(1, 1)} ∪ {Ni(0, 1, ... , 1
i−1
, 1, 0, ... , 0
i−1
)|i = 1, 2, . . . , n}
and the target instance contains the adjacency relations H and V together with
{B(t0), E(tk)}. Let us now define the set of dependencies. Intuitively, we encode tiles as
values of a function f . The tile on position (i, j) is encoded as f (ibin jbin). We need to
check the adjacency relations. This can be done because we can express incrementation
Journal of the ACM, Vol. 61, No. 2, Article 12, Publication date: April 2014.
12:14 S. Amano et al.
on n-bit words. For each j = 1, 2, . . . n add dependencies
Eq(x1, u1), . . . , Eq(xj , uj ), Eq(y1, v1), . . . , Eq(yn, vn)
Nn−j (xj 1, . . . , xn, uj 1, . . . , un)
−→ H( f ( ¯x, ¯y), f ( ¯u, ¯ v)) ,
Eq(x1, u1), . . . , Eq(xn, un), Eq(y1, v1), . . . , Eq(yj, vj )
Nn−j (yj 1, . . . , yn, vj 1, . . . , vn)
−→ V( f ( ¯x, ¯y), f ( ¯u, ¯ v)) .
We also need to check that we begin and end properly:
False(x1), . . . , False(xn), False(y1), . . . , False(yn) −→ B( f ( ¯x, ¯y)) ,
True(x1), . . . , True(xn), True(y1), . . . ,ที่แท้จริง ( ใน ) −→ e ( F ( ¯¯ X , Y ) ) .
ในแง่ความซับซ้อนของข้อมูลขั้นตอนวิธีที่อธิบายข้างต้นอยู่ใน NP : ขนาดของδ
S , M , F เป็นพหุนามสำหรับทุกการแก้ไขแผนที่ ให้เราพิสูจน์ความแข็ง จำได้
ถ้าเราแทนที่ 2 × 2 ตารางกับ n × n-grid ในกระเบื้อง
ถือว่าปัญหาข้างต้น เราสิ้นสุดขึ้นเป็นปัญหาเอ็นพีสมบูรณ์ . ความคิดของการลด
จากปัญหานี้ใหม่ให้สมาชิก ( M ) คือ เช่นเดียวกับในการลด
ข้างบน และใช้งานได้ง่ายคือ . เป็นแหล่งตัวอย่างเราใช้
{ B ( 1 ) , E ( n ) EQ ( 1 , 1 ) , อีคิว ( 2 , 2 ) . . . . . . . , EQ ( N , N , N ( 1 , 2 ) , ( 2 , 3 ) . . . . . . . , N ( n − 1 , n ) } ตัวอย่างเป้าหมาย
เหมือนเมื่อก่อนเลย การอ้างอิงเป็น
n ( x , u ) EQ ( Y , V ) −→ H ( f ( x , y ) f ( u , v ) B ( X ) , B ( y ) −→ B ( f ( x , y )
n ( x , u ) , อีคิว ( Y , v) −→ V( f (y, x), f (v, u)) , E(x), E(y) −→ E( f (x, y)) .
It is routine to verify the correctness of the reduction.
The main source of hardness are Skolem functions. The first reduction above uses
function symbols of unbounded arity, but they can be easily encoded with binary functions
by using either nested terms or equality. If we bound the arity of terms (the total
จำนวนของการเกิดขึ้นของตัวแปร ) และห้าม equalities ชัดเจนระหว่างคำ ( ซ้ำ
ตัวแปรที่ได้รับอนุญาต ) , รวมความซับซ้อนลดลงถึงระดับที่สามของ
แบบโพลิโนเมียล ข้อมูลที่ซับซ้อนจะไม่ได้รับผลกระทบ เนื่องจากการแมปที่ใช้ในการตอบสนองข้อ จำกัด ข้างต้น
ที่สองเหล่านี้ หลักฐานที่สมบูรณ์ของผลในภาคผนวกต่อไปนี้
.
ทฤษฎีบท 4.6 . For schema mappings from SM(⇓,⇒,∼, Fun) with bounded arity of
terms and no explicit equality, MEMBERSHIP is
p
3 -complete, and the lower bound holds
already for relational mappings without ∼.
If we forbid Skolem functions altogether, the data complexity of mappings drops very
low, but combined complexity is still complete for the second level of the polynomial
hierarchy, like in the relational case [Gottlob and Senellart 2010]. If we additionally
bound the number of variables in dependencies, even combined complexity is polynomial.
THEOREM 4.7. For schema mappings from SM(⇓,⇒,∼), MEMBERSHIP(M) is
LOGSPACE-complete, while MEMBERSHIP is 
p
2-complete in general and in PTIME if
the maximum number of variables per pattern is fixed.
PROOF.
( 1 ) สอดคล้องกับ DTD คงที่สามารถตรวจสอบใน logspace . มันยังคงแสดง
ที่เราสามารถตรวจสอบ logspace ถ้า S และ T ตามϕข้อจำกัดเดียว ( ¯ X , ¯ Y ) −→ψ ( ¯ X , ¯ Z )
ให้¯ x = x1 , x2 , . . . . . . . . ¯ XK , y1 y2 Y = , , , , , , , , . . . . . . . . , Y  และ¯กขึ้น Z1 Z = , . . . . . . . . ๆ , . ปล่อยเป็นชุดของข้อมูลที่ใช้ใน S หรือ T .
ค่า เราต้องตรวจสอบว่าในแต่ละ¯เป็น∈ AK และแต่ละ¯ B ∈เป็น  เช่น
s | = ϕ ( ¯ ,¯ B ) มีอยู่¯ C ∈เป็นแบบนี้ T | = ψ ( ¯ , ¯ C ) เนื่องจากตัวเลข k ,  M เป็น
ถาวร ( เป็นส่วนของการแก้ไขแผนที่ ) , พื้นที่ที่จำเป็นสำหรับการจัดเก็บวารสารทั้งหมดสามจุด
ของ ACM เล่มที่ 61 2 ข้อ 12 , วันที่เผยแพร่ : เมษายน 2014
XMLHttpRequest แมป : แลกเปลี่ยนข้อมูลและข้อมูลการจัดการ 12 : 15
เป็นลอการิทึมใน ขนาด S และ T . ใช้ข้อเสนอ 4.3 ,เราได้รับ logspace
ขั้นตอนวิธีโดยเพียงแค่กว่ามูลค่าที่เป็นไปได้ทั้งหมด¯ , ¯ B และ C .
¯ logspacehardness ว่าข้อเสนอ 4.3 .
( 2 ) แรกให้เราดูที่ปัญหาใน 
p
2 พิจารณาอัลกอริทึมสำหรับปัญหาต่อไปนี้ :
เสริมว่าข้อจำกัดϕ ( ¯ X , ¯ Y ) −→ψ ( ¯ X , ¯ Z ) และมูลค่า¯ , ¯ B
ของตัวแปรที่ใช้ในϕและตรวจสอบว่า | = ϕ ( ¯ , ¯b) and T |= ψ( ¯a, ¯z). By Proposition 4.3,
the first check is polynomial. The second check however involves a tree pattern possibly
containing free variables, so it can only be done in coNP. Altogether the algorithm is in

p
2 . The 
p
2 lower bound for relational mappings using neither Skolem functions nor
equality [Gottlob and Senellart 2010] carries over to SM(↓) via the standard encoding.
The original reduction can be obtained as a natural modification of the one from
Theorem 4.6.
(3) Proceed just like in (1). The number of variables per pattern is bounded, so there
are only polynomially many possible valuations. Hence, we may iterate over all of them
using algorithm from Proposition 4.3 เพื่อตรวจสอบ | = ϕ ( ¯ , ¯ B ) และ T | = ψ ( ¯ , ¯ C )
5 สอบถามตอบ
5.1 สอบถามตอบปัญหา
ปัญหาพื้นฐานของข้อมูลที่แลกเปลี่ยนตอบแบบสอบถามกว่าข้อมูลเป้าหมาย
ในทางที่สอดคล้องกับข้อมูลแหล่งที่มา แรงบันดาลใจจากการวิจัยเกี่ยวกับความสัมพันธ์
กรณี [ barcel ใหม่ O 2009 ; เฟกิ้น et al . 2005 kolaitis 2005 ] เราศึกษาแบบสอบถามตอบแบบสอบถามที่เชื่อมต่อกัน
และสหภาพแรงงานของตนแบบสอบถามที่เชื่อมต่อกันผ่านต้นไม้ปกติ
แสดงต้นไม้รูปแบบ [ gottlob et al . 2006 , BJ ตั้ง orklund et al . 2008 , 2011 ] ดังนั้น
เพื่อสอบถามเอกสาร เราใช้ภาษาเดียวกันสำหรับการอ้างอิง : รูปแบบต้นไม้
ปริซึมกับ equalities เป็นอสมการ จับแบบอนาล็อกของ
สันธานแบบสอบถามกับอสมการ และแน่นอน เราอนุญาตให้ฉาย
นั่นคือแบบสอบถามคือการแสดงออกของรูปแบบ
x
ϕ∃¯ , ที่ϕเป็นรูปแบบไม่ใช้สัญลักษณ์ฟังก์ชัน เช่นที่ฟรีแต่ละตัวแปรตอบสนอง
ความปลอดภัยเงื่อนไข ( ดูคำนิยาม 3.1 ) ความหมายคือที่ระบุในแบบมาตรฐาน .
ของแบบสอบถามเป็นชุดของการประเมินมูลค่าของตัวแปรอิสระที่ให้
แบบสอบถามถือจริง คลาสของแบบสอบถามนี้แทน โดย ctq ( สอบถามต้นไม้ที่เชื่อมต่อกัน )