{"ID":3083746,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T06:54:00.442624098Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.06127","arxiv_id":"2606.06127","title":"Validation of graph databases against PG-Schema","abstract":"The problem of validating a given graph database instance against a given PG-Schema graph type without integrity constraints is NP- complete in terms of combined complexity and in PTIME in terms of data complexity. The combined complexity drops to PTIME when the alternation between type combinations and unions is suitably restricted","short_abstract":"The problem of validating a given graph database instance against a given PG-Schema graph type without integrity constraints is NP- complete in terms of combined complexity and in PTIME in terms of data complexity. The combined complexity drops to PTIME when the alternation between type combinations and unions is suita...","url_abs":"https://arxiv.org/abs/2606.06127","url_pdf":"https://arxiv.org/pdf/2606.06127v1","authors":"[\"Jacek Ciszewski\",\"Jakub Kłos\",\"Maxime Jakubowski\",\"Dominik Tomaszuk\",\"Filip Murlak\"]","published":"2026-06-04T13:15:12Z","proceeding":"cs.DB","tasks":"[\"cs.DB\"]","methods":"[]","has_code":false}