Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/29006
Title: | Satisfiability for SCULPT-Schemas for CSV-Like Data. | Authors: | DOLESCHAL, Johannes MARTENS, Wim NEVEN, Frank Witkowski, Adam |
Issue Date: | 2018 | Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | Source: | Kimelfeld, Benny; Amsterdamer, Yael (Ed.). 21st International Conference on Database Theory (ICDT 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik,p. 14:1-14:19 | Series/Report: | Leibniz International Proceedings in Informatics (LIPIcs) | Series/Report no.: | 98 | Abstract: | SCULPT is a simple schema language inspired by the recent working effort towards a recommendation by the World Wide Web Consortium (W3C) for tabular data and metadata on the Web. In its core, a SCULPT schema consists of a set of rules where left-hand sides select sets of regions in the tabular data and the right-hand sides describe the contents of these regions. A document (divided in cells by row- and column-delimiters) then satisfies a schema if it satisfies every rule. In this paper, we study the satisfiability problem for SCULPT schemas. As SCULPT describes grid-like structures, satisfiability obviously becomes undecidable rather quickly even for very restricted schemas. We define a schema language called L-SCULPT (Lego SCULPT) that restricts the walking power of SCULPT by selecting rectangular shaped areas and only considers tables for which selected regions do not intersect. Depending on the axes used by L-SCULPT, we show that satisfiability is PTIME-complete or undecidable. One of the tractable fragments is practically useful as it extends the structural core of the current W3C proposal for schemas over tabular data. We therefore see how the navigational power of the W3C proposal can be extended while still retaining tractable satisfiability tests. | Keywords: | CSV; Schema languages; Semi-structured data | Document URI: | http://hdl.handle.net/1942/29006 | ISBN: | 9783959770637 | DOI: | 10.4230/LIPIcs.ICDT.2018.14 | Rights: | Johannes Doleschal, Wim Martens, Frank Neven, and Adam Witkowski; licensed under Creative Commons License CC-BY 21st International Conference on Database Theory (ICDT 2018). Editors: Benny Kimelfeld and Yael Amsterdamer; Article No. 14; pp. 14:1–14:19 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs-ICDT-2018-14.pdf | Published version | 579.17 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 2, 2020
Page view(s)
32
checked on Sep 6, 2022
Download(s)
2
checked on Sep 6, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.