Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Kasneci, Gjergji
Schwentick, Thomas

dblp
dblp

Not MPG Author(s):

Schwentick, Thomas

Editor(s):

Libkin, Leonid

dblp



BibTeX cite key*:

KasneciSchwentick2007PODS

Title, Booktitle

Title*:

The Complexity of Reasoning about Pattern-based XML Schemas

Booktitle*:

26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2007)

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Beijing, China

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

23 February 2007

Event End Date:

23 February 2007

Publisher

Name*:

ACM

URL:


Address*:

New York

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

155-164

Year*:

2007

VG Wort Pages:

34

ISBN/ISSN:

978-1-59593-685-1

Sequence Number:


DOI:

http://doi.acm.org/10.1145/1265530.1265552



Note, Abstract, ©


(LaTeX) Abstract:

In a recent paper, Martens et al. introduced a specification
mechanism for {XML} tree languages, based on rules of the
form r ! s, where r, s are regular expressions. Sets of such
rules can be interpreted in an existential or a universal fashion.
An {XML} tree is existentially valid with respect to a
rule set, if for each node there is a rule such that the root
path of the node matches r and the children sequence of the
node matches s. It is universally valid if each node matching
r also matches s. This paper investigates the complexity of
reasoning about such rule sets, in particular the satisfiability
and the implication problem. Whereas, in general these reasoning
problems are complete for ExpTime, two important
fragments are identified with PSpace and PTime complexity,
respectively.



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Databases and Information Systems Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{KasneciSchwentick2007PODS,
AUTHOR = {Kasneci, Gjergji and Schwentick, Thomas},
EDITOR = {Libkin, Leonid},
TITLE = {The Complexity of Reasoning about Pattern-based {XML} Schemas},
BOOKTITLE = {26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2007)},
PUBLISHER = {ACM},
YEAR = {2007},
PAGES = {155--164},
ADDRESS = {Beijing, China},
ISBN = {978-1-59593-685-1},
DOI = {http://doi.acm.org/10.1145/1265530.1265552},
}


Entry last modified by Martin Theobald, 04/15/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Gjergji Kasneci
Created
02/23/2007 10:38:44 AM
Revisions
12.
11.
10.
9.
8.
Editor(s)
Martin Theobald
Adriana Davidescu
Adriana Davidescu
Adriana Davidescu
Adriana Davidescu
Edit Dates
04/15/2009 03:56:09 PM
15.01.2008 15:24:21
20.07.2007 17:03:27
06.07.2007 14:31:01
06.07.2007 14:27:36