• Login
    View Item 
    •   Shocker Open Access Repository Home
    • Engineering
    • Electrical Engineering and Computer Science
    • EECS Faculty Scholarship
    • EECS Research Publications
    • View Item
    •   Shocker Open Access Repository Home
    • Engineering
    • Electrical Engineering and Computer Science
    • EECS Faculty Scholarship
    • EECS Research Publications
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Rewriting XPath queries using materialized XPath views

    Date
    2012-07
    Author
    Ramanan, Prakash
    Metadata
    Show full item record
    Citation
    Ramanan, P. 2012. "Rewriting XPath queries using materialized XPath views". Journal of Computer and System Sciences. 78 (4): 1006-1025.
    Abstract
    Let XP(/, //, []) be the fragment of XPath 1.0, consisting of queries that involve only the child and descendant axes, and predicates without disjunction or negation (and no wildcard nodetests); these queries can be represented as tree patterns. We consider the problem of rewriting a query Q using a materialized view V. where Q, V is an element of XP(/, //, []). We present more efficient algorithms for the following: (1) Determine if an equivalent rewriting of Q using V exists; find the smallest such rewriting, when it exists. A previously-known algorithm runs in O(vertical bar Q vertical bar(2) + vertical bar Q vertical bar vertical bar V vertical bar) time. For the special case when Q is known to be minimal, we present an O(vertical bar Q vertical bar vertical bar V vertical bar) algorithm. (2) Determine if a (nonempty) contained rewriting of Q using V exists. We present an O(vertical bar Q vertical bar vertical bar V vertical bar) algorithm, compared to the previous O(ver! tical bar Q vertical bar vertical bar V vertical bar(2)) algorithm. We also present a more efficient algorithm for finding a maximal such rewriting, when it exists. Then we extend this result to a subset of XP(/, //, [], *) that allows restricted occurrences of wildcard nodetests.
    Description
    Click on the DOI link below to access the article (may not be free).
    URI
    http://hdl.handle.net/10057/5176
    http://dx.doi.org/10.1016/j.jcss.2011.12.001
    Collections
    • EECS Research Publications

    Browse

    All of Shocker Open Access RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsBy TypeThis CollectionBy Issue DateAuthorsTitlesSubjectsBy Type

    My Account

    LoginRegister

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    DSpace software copyright © 2002-2023  DuraSpace
    DSpace Express is a service operated by 
    Atmire NV