48
Processamento de Consultas XML em Ambientes Distribuídos Niterói, Março de 2013. Luiz Augusto Matos da Silva Vanessa Braganholo (orientadora)

Processamento consultas-xml-v2

Embed Size (px)

Citation preview

Page 1: Processamento consultas-xml-v2

Processamento de Consultas XML em Ambientes Distribuídos

Niterói, Março de 2013.

Luiz Augusto Matos da SilvaVanessa Braganholo (orientadora)

Page 2: Processamento consultas-xml-v2

2

Organização

• Contexto e Motivação

• Objetivos

• Trabalhos Relacionados

• Solução Proposta

• Considerações Finais

Page 3: Processamento consultas-xml-v2

3

• + transações => Aumento no volume de dados

• Informação útil para a tomada de decisão

• Armazenamento distribuído de dados

• Diferentes formas de representação de dados

Contexto e Motivação

Page 4: Processamento consultas-xml-v2

4

XML

consulta

resultadoSistema de Apoio

à Decisão

CONSULTAS DE ALTO CUSTO

? ? ?

Page 5: Processamento consultas-xml-v2

5

Como tornar mais eficiente o

processamento de consultas XML em

ambientes distribuídos?

Page 6: Processamento consultas-xml-v2

6

Fragmentação de Dados

Page 7: Processamento consultas-xml-v2

7

Por que fragmentar?

- Compartilhamento de dados (confiabilidade)

- Distribuição e paralelização de processamento

(perfomance) [ÖZSU e VALDURIEZ, 2011]

GANHO DE DESEMPENHO

Page 8: Processamento consultas-xml-v2

8

Processamento paralelo

• Paralelismo Interconsulta

Processamento simultâneo de diferentes consultas de

baixo custo em nós distintos.

• Paralelismo Intraconsulta

Processamento simultâneo da mesma consulta em

múltiplos nós. [MATTOSO, 2009]

Page 9: Processamento consultas-xml-v2

9

Single Document (SD)

Multiple Documents (MD)

Page 10: Processamento consultas-xml-v2

10

Como fragmentar?

Fragmentação Física

Page 11: Processamento consultas-xml-v2

Fragmentação Horizontal

Seleção ()

Seleção ()

Modelo RelacionalModelo XML

Unidade de dados= tuplas

Unidade de dados = árvores [SILVA, 2013]

f1

f2

11

Page 12: Processamento consultas-xml-v2

F1Residencial:= <CContatos,σcontato/telefone/tipo=’Residencial’>F2Outros:= <CContatos,σcontato/telefone/tipo <> ‘Residencial’>

F1Residencial F2Outros

<contato> <id>001</id> <nome>Maria Silva</nome> <endereco> <logradouro> Rua A </logradouro> <numero>10</numero> <complemento>Casa 3</complemento> </endereco> <email>[email protected]</email> <telefone> <tipo> Residencial </tipo> <ddd>21</ddd> <numero>22220000</numero> <telefone></contato>

<contato> <id>002</id> <nome>José Abreu </nome> <endereco> <logradouro> Rua C</logradouro> <numero>155</numero> <complemento>Ap. 501</complemento> </endereco> <email>[email protected]</email> <telefone> <tipo> Celular </tipo> <ddd>31</ddd> <numero>99990000</numero> <telefone></contato>

[SILVA, 2013, adaptado]

12

Page 13: Processamento consultas-xml-v2

Fragmentação Vertical

Projeção ()Modelo Relacional

Modelo XML

Projeção () [SILVA, 2013]

f1

f2

13

Page 14: Processamento consultas-xml-v2

F1Contatos:= <CContatos, π/Contato, /Contato/Telefone>F2Contatos:= <CContatos, π/Contato/Telefone, {}>

Contato

IdNome

Endereço

Logradouro

Número

Complemento

BairroCidade

e-mail

Telefone

Tipo

DDD

Número

F1Contatos

F2Contatos

Contato

IdNome

Endereço

LogradouroNúmero

Complemento

Bairro

Cidade

e-mail

Telefone

Tipo

DDDNúmero

Esquema

[SILVA, 2013]

Page 15: Processamento consultas-xml-v2

15

XML

consulta

resultadoSistema de Apoio

à Decisão

- Consultas analíticas = grande volume de dados

- + operações de agregação

- Consultas ad-hoc = não há um padrão de execução

Page 16: Processamento consultas-xml-v2

16

Limitações da Fragmentação Física para este cenário

• Requer conhecimento prévio das consultas frequentes

• Para cada nova consulta, novo projeto de fragmentação

PROCESSO ONEROSO

Page 17: Processamento consultas-xml-v2

Fragmentação Virtual

OriginalQuery

Sub -Query2

Sub -Query3

Sub -Query4

Sub -Query1

DBMS

DBMS

DBMS

DBMS

C

C2

C3

C4

C1 DBMSSGBD

DBMSSGBD

DBMSSGBD

DBMSSGBD

[MATTOSO et al., 2005, adaptada]

BD

BD

BD

BD

17

Page 18: Processamento consultas-xml-v2

Select sum(price) from ITEM

Select sum(price) from ITEM

where item_no >= 1

and item_no < 250,001

Select sum(price) from ITEM

where item_no >= 1

and item_no < 250,001

Select sum(price) from ITEM

where item_no >= 500,001

and item_no < 750,001

Select sum(price) from ITEM

where item_no >= 500,001

and item_no < 750,001

Select sum(price) from ITEM

where item_no >= 250,001

and item_no < 500,001

Select sum(price) from ITEM

where item_no >= 250,001

and item_no < 500,001

Select sum(price) from ITEM

where item_no >= 750,001

and item_no < 1,000,001

Select sum(price) from ITEM

where item_no >= 750,001

and item_no < 1,000,001

[MATTOSO et al., 2005]

18

Page 19: Processamento consultas-xml-v2

19

Problema

• Seleção do atributo de fragmentação

RESTRIÇÕES DE UNICIDADE

Page 20: Processamento consultas-xml-v2

Fragmentação Virtual Adaptativa

Original

Query

DBMS

DBMS

DBMS

DBMS

C

DBMSSGBD

DBMSSGBD

DBMSSGBD

DBMSSGBD

Subconsultas [MATTOSO et al., 2005, adaptada]

Page 21: Processamento consultas-xml-v2

21

Page 22: Processamento consultas-xml-v2

22

OBJETIVOS

Page 23: Processamento consultas-xml-v2

23

Definir

um processo,

uma arquitetura e

um conjunto de algoritmos eficientes

para a Fragmentação Virtual Adaptativa de

bases de dados XML distribuídas, no intuito de

otimizar o desempenho do processamento de

consultas.

Page 24: Processamento consultas-xml-v2

24

TRABALHOS RELACIONADOS

Page 25: Processamento consultas-xml-v2

[MA e SCHEWE, 2003]

Contribuição: Define técnicas de fragmentação horizontal e

vertical em dados XML.

Limitações: DTD (modelo), XML-QL (consulta), somente

documentos, sem alocação, exige projeto de fragmentação.

25/40

25

Page 26: Processamento consultas-xml-v2

[BREMER e GERTZ, 2003]

Contribuição: Abordagem para fragmentação

horizontal/vertical e alocação de dados XML.

Limitações: Esquema específico (RepositoryGuide),

baixo desempenho em consultas e atualizações

distribuídas, exige projeto de fragmentação.26/40

26

Page 27: Processamento consultas-xml-v2

27/40

[ANDRADE et al., 2006]

Contribuições: Define as técnicas de fragmentação

vertical, horizontal e híbrida, descreve critérios de

correção.

Limitação: Exige projeto de distribuição.

27

Page 28: Processamento consultas-xml-v2

28

[FIGUEIREDO et al., 2010]

Contribuições: Automatiza as técnicas de fragmentação

e os critérios de correção definidos em [Andrade et al.,

2006], trata da redução de fragmentos irrelevantes.

Limitação: Modelo de consultas utiliza subconjunto

limitado da XQuery, exige projeto de distribuição.

Page 29: Processamento consultas-xml-v2

29

[FIGUEIREDO et al., 2010]

Arquitetura Mediador-Adaptadores para o processamento de consultas XML

Page 30: Processamento consultas-xml-v2

[KLING et al., 2010]

Contribuições: Automatiza a fragmentação, consulta

e alocação dos dados fragmentados, poda de

fragmentos irrelevantes.

Limitação: Modelo de consultas utiliza subconjunto

limitado da XQuery, não trata da fragmentação híbrida,

exige projeto de distribuição.

30/40

30

Page 31: Processamento consultas-xml-v2

31/40

[RODRIGUES et al., 2011]

Contribuições: Fragmentação virtual para o modelo

XML, não exige projeto de distribuição.

Limitação: Variação do tempo de recuperação da função

position(), desbalanceamento de carga.

31

Page 32: Processamento consultas-xml-v2

32

/books/book[position()=2)]

Page 33: Processamento consultas-xml-v2

33

[RODRIGUES, 2011]

Page 34: Processamento consultas-xml-v2

34

[RODRIGUES et al., 2011]

Visão Geral da Arquitetura para a Fragmentação Virtual XML

Page 35: Processamento consultas-xml-v2

[LIMA et al., 2010]

Contribuições: Ajusta dinamicamente os tamanhos dos

fragmentos durante a execução da consulta, implementa o

balanceamento de carga.

Limitação: Aplicado somente ao modelo relacional.

35/40

35

Page 36: Processamento consultas-xml-v2

36

SOLUÇÃO PROPOSTA

Page 37: Processamento consultas-xml-v2

Adaptar a técnica de Fragmentação Virtual Adaptativa

utilizada no modelo relacional para o modelo XML.

37/40

BD

consulta

coordenador . . .

clustersubconsultas

1 – Executa a subconsulta com intervalo inicial

2 – Incrementa o intervalo e executa a subconsulta enquanto o tempo de execução for aceitável

3 – Para de incrementar o intervalo

4 – Se o tempo aumentou desproporcionalmente então reduz o tamanho do intervalo e volta para o passo 1.

BD

37

Page 38: Processamento consultas-xml-v2

38/40

cluster

for $r in doc(‘books.xml’)//book

[position() >= 1 and position() < 20000]

where $r/book[@year=“2003”]

subconsultas

for $r in doc(‘books.xml’)//book

[position() >= 20001 and position() < 40000]

where $r/book[@year=“2003”]

1

for $r in doc(‘books.xml’)//book

where $r/book[@year=“2003”]

2for $r in doc(‘books.xml’)//book

[position() >= 1 and position() < 2000]

where $r/book[@year=“2003”]

for $r in doc(‘books.xml’)//book

[position() >= 2001 and position() < 4000]

where $r/book[@year=“2003”]

for $r in doc(‘books.xml’)//book

[position() >= 4001 and position() < 8000]

where $r/book[@year=“2003”]

for $r in doc(‘books.xml’)//book

[position() >= 8001 and position() < 10500]

where $r/book[@year=“2003”]

11

consulta

1

[Tempo OK]

[Tempo OK]

[Tempo Exce

dido]

BD

. . .

BD

38

Page 39: Processamento consultas-xml-v2

E se um nó finalizar o processamento antes de outro nó?

39/40

. . .

cluster 1 – Se o Nó 1 ainda possuir dados a serem processados e o Nó 2 já tiver concluído seu processamento, então

2 – Nó 1 divide a quantidade de dados a serem processados em dois intervalos

3 – A faixa de intervalos mais alta é informada ao Nó 2, que irá processá-la.

BD

BD

39

Page 40: Processamento consultas-xml-v2

40

[FIGUEIREDO et al., 2010]

Arquitetura Mediador-Adaptadores para o processamento de consultas XML

FVA-XML

Page 41: Processamento consultas-xml-v2

41

CONSIDERAÇÕES FINAIS

Page 42: Processamento consultas-xml-v2

Com o aumento da quantidade de dados …

Como tornar mais eficiente o

processamento de consultas

XML em ambientes distribuídos?

42/40

42

Page 43: Processamento consultas-xml-v2

O que já existe para o modelo relacional?

43/40

43

Page 44: Processamento consultas-xml-v2

Trabalho Armazena-mento

Técnica Frag-mentação

Modelo Consulta Exige Projeto Frag.

[FIGUEIREDO et al., 2006]

SD e MD Horizontal, vertical e híbrida

XML Schema

XQuery Sim

[KLING et al., 2010]

SD e MD Horizontal, vertical

XML Schema

XQuery Sim

[RODRIGUES et al., 2011]

SD e MD Virtual Simples XML Schema

XQuery Não

Nossa Proposta SD e MD Virtual Adaptativa

XML Schema

XQuery Não

O que já existe para o modelo XML?

44/40

44

Page 45: Processamento consultas-xml-v2

Próximos passos …

Experimentos com SGBD XML Nativos

(armazenamento, índices, consultas etc.)

45/40

45

Page 46: Processamento consultas-xml-v2

46

[SILVA JÚNIOR, 2012]

Page 47: Processamento consultas-xml-v2

Próximos passos …

Definição da arquitetura/metodologia;

Definição e codificação dos algoritmos;

Prototipação;

Validação.

47/40

47

Page 48: Processamento consultas-xml-v2

Referências

ANDRADE, Alexandre; RUBERG, Gabriela; BAIÃO, Fernanda; BRAGANHOLO, Vanessa; MATTOSO, Marta. Efficiently Processing XML Queries over Fragmented Repositories with PartiX. In: INTERNATIONAL WORKSHOP ON DATABASE TECHNOLOGIES FOR HANDLING XML INFORMATION ON THE WEB (DATAX), 2., 2006, Munique. Proceedings... . Munique, 2006. p. 150-163.

BREMER, Jan-Marco; GERTZ, Michael. On Distributing XML Repositories. In: INTERNATIONAL WORKSHOP ON THE WEB AND DATABASES (WebDB), 2003, San Diego. Proceedings… . San Diego, 2003.

KLING, Patrick; ÖZSU, M. Tamer; DAUDJEE, Khuzaima. Distributed XML Query Processing: fragmentation, localization and pruning. Relatório Técnico, Universidade de Waterloo, Ontario, Canada, 2010.

LIMA, Alexandre A. B. ; MATTOSO, Marta; VALDURIEZ, Patrick. Adaptive Virtual Partitioning for OLAP Query Processing in a Database Cluster. Journal of Information and Data Management, v. 1, p. 75-87, 2010.

MA, Hui; SCHEWE, Klaus-Dieter. Fragmentation of XML Documents. In: SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (SBBD), 18., 2003, Manaus. Anais... . Manaus, 2003. p. 200-214.

MATTOSO, M. Database clusters. In Encyclopedia of Database Systems, L. Liu and M. T. Özsu (Eds.). Springer, pp. 700-704, 2009.

ÖZSU, M. T.; VALDURIEZ, P. Principles of Distributed Database Systems. 3. ed. Springer, 2011.

RODRIGUES, C.; BRAGANHOLO, V.; MATTOSO, M. Virtual Partitioning ad-hoc Queries over Distributed XML Databases. In Journal of Information and Data Management, v. 2, n. 3, pp. 495-510, 2011.