Modeling and Manipulating the Structure of Hierarchical Schemas for the Web
by Theodore Dalamagas, Alexandra Meliou, Timos K. Sellis
Abstract:
The Semantic Web is the next step of the current Web where information will become more machine-understandable to support effective data discovery and integration. Hierarchical schemas, either in the form of tree-like structures (e.g., DTDs, XML schemas), or in the form of hierarchies on a category/subcategory basis (e.g., thematic hierarchies of portal catalogs), play an important role in this task. They are used to enrich semantically the available information. Up to now, hierarchical schemas have been treated rather as sets of individual elements, acting as semantic guides for browsing or querying data. Under that view, queries like "find the part of a portal catalog which is not present in another catalog" can be answered only in a procedural way, specifying which nodes to select and how to get them. For this reason, we argue that hierarchical schemas should be treated as full-fledged objects so as to allow for their manipulation. This work proposes models and operators to manipulate the structural information of hierarchies, considering them as first-class citizens. First, we explore the algebraic properties of trees representing hierarchies, and define a lattice algebraic structure on them. Then, turning this structure into a boolean algebra, we present the operators S-union, S-intersection and S-difference to support structural manipulation of hierarchies. These operators have certain algebraic properties to provide clear semantics and assist the transformation, simplification and optimization of sequences of operations using laws similar to those of set theory. Also, we identify the conditions under which this framework is applicable. Finally, we demonstrate an application of our framework for manipulating hierarchical schemas on tree-like hierarchies encoded as RDF/s files.
Citation:
Theodore Dalamagas, Alexandra Meliou, and Timos K. Sellis, Modeling and Manipulating the Structure of Hierarchical Schemas for the Web, Information Sciences, Elsevier, vol. 178, no. 4, 2008, pp. 985–1010.
Bibtex:
@article{DBLP:journals/isci/DalamagasMS08,
    Abstract = {The Semantic Web is the next step of the current Web where
    information will become more machine-understandable to support effective
    data discovery and integration. Hierarchical schemas, either in the form
    of tree-like structures (e.g., DTDs, XML schemas), or in the form of
    hierarchies on a category/subcategory basis (e.g., thematic hierarchies of
    portal catalogs), play an important role in this task. They are used to
    enrich semantically the available information. Up to now, hierarchical
    schemas have been treated rather as sets of individual elements, acting as
    semantic guides for browsing or querying data. Under that view, queries
    like "find the part of a portal catalog which is not present in another
    catalog" can be answered only in a procedural way, specifying which nodes
    to select and how to get them. For this reason, we argue that hierarchical
    schemas should be treated as full-fledged objects so as to allow for their
    manipulation. This work proposes models and operators to manipulate the
    structural information of hierarchies, considering them as first-class
    citizens. First, we explore the algebraic properties of trees representing
    hierarchies, and define a lattice algebraic structure on them. Then,
    turning this structure into a boolean algebra, we present the operators
    S-union, S-intersection and S-difference to support structural
    manipulation of hierarchies. These operators have certain algebraic
    properties to provide clear semantics and assist the transformation,
    simplification and optimization of sequences of operations using laws
    similar to those of set theory. Also, we identify the conditions under
    which this framework is applicable. Finally, we demonstrate an application
    of our framework for manipulating hierarchical schemas on tree-like
    hierarchies encoded as RDF/s files.},
    Author = {Theodore Dalamagas and Alexandra Meliou and Timos K. Sellis},
    Journal = {Information Sciences, Elsevier},
    Number = {4},
    Pages = {985-1010},
    doi = {10.1016/j.ins.2007.09.022},
    Title = {\href{http://people.cs.umass.edu/ameli/papers/InfSci2008.pdf}{Modeling and Manipulating the Structure of Hierarchical Schemas for the Web}},
    Venue = {InfSci},
    Volume = {178},
    Year = {2008}
}