Efficient inclusion of conflict-free XML types with interleaving and counting (Extended abstract)

Giorgio Ghelli; Dario Colazzo; Carlo Sartiani

Efficient inclusion of conflict-free XML types with interleaving and counting (Extended abstract)

Giorgio Ghelli, Dario Colazzo, Carlo Sartiani

Research output: Contribution to conference › Paper › peer-review

Abstract

Inclusion between XML types is important but expensive, and is much more expensive when unordered types are considered. We prove here that inclusion for XML types with interleaving and counting can be decided in polynomial time in presence of two important restrictions: no element appears twice in the same content model, and Kleene star is only applied to disjunctions of single elements.

Original language	English
Pages	390-397
Number of pages	8
Publication status	Published - 1 Dec 2008
Externally published	Yes
Event	16th Italian Symposium on Advanced Database Systems, SEBD 2008 - Mondello, Palermo, Italy Duration: 22 Jun 2008 → 25 Jun 2008

Conference

Conference	16th Italian Symposium on Advanced Database Systems, SEBD 2008
Country/Territory	Italy
City	Mondello, Palermo
Period	22/06/08 → 25/06/08

Cite this

@conference{091883dcbbf947f0835aee718f48830b,

title = "Efficient inclusion of conflict-free XML types with interleaving and counting (Extended abstract)",

abstract = "Inclusion between XML types is important but expensive, and is much more expensive when unordered types are considered. We prove here that inclusion for XML types with interleaving and counting can be decided in polynomial time in presence of two important restrictions: no element appears twice in the same content model, and Kleene star is only applied to disjunctions of single elements.",

author = "Giorgio Ghelli and Dario Colazzo and Carlo Sartiani",

year = "2008",

month = dec,

day = "1",

language = "English",

pages = "390--397",

note = "16th Italian Symposium on Advanced Database Systems, SEBD 2008 ; Conference date: 22-06-2008 Through 25-06-2008",

}

TY - CONF

T1 - Efficient inclusion of conflict-free XML types with interleaving and counting (Extended abstract)

AU - Ghelli, Giorgio

AU - Colazzo, Dario

AU - Sartiani, Carlo

PY - 2008/12/1

Y1 - 2008/12/1

N2 - Inclusion between XML types is important but expensive, and is much more expensive when unordered types are considered. We prove here that inclusion for XML types with interleaving and counting can be decided in polynomial time in presence of two important restrictions: no element appears twice in the same content model, and Kleene star is only applied to disjunctions of single elements.

AB - Inclusion between XML types is important but expensive, and is much more expensive when unordered types are considered. We prove here that inclusion for XML types with interleaving and counting can be decided in polynomial time in presence of two important restrictions: no element appears twice in the same content model, and Kleene star is only applied to disjunctions of single elements.

M3 - Paper

AN - SCOPUS:84893214744

SP - 390

EP - 397

T2 - 16th Italian Symposium on Advanced Database Systems, SEBD 2008

Y2 - 22 June 2008 through 25 June 2008

ER -

Efficient inclusion of conflict-free XML types with interleaving and counting (Extended abstract)

Abstract

Conference

Fingerprint

Cite this