تجزیهٔ بدون‌اتلافِ دادهٔ حسگر با پایتون؛ وابستگی تابعی و رکوردِ اضافی

تقسیم یک جدول به دو جدول کوچک‌تر، به‌تنهایی نشان نمی‌دهد اطلاعاتِ اولیه قابل بازسازی است. ممکن است اتصال دوباره، ترکیب‌هایی بسازد که هیچ‌وقت ثبت نشده‌اند. در این درس، طرحی کوچک برای شناسه، محل و واحد حسگر می‌سازیم و فرقِ آزمون یک نمونه با تضمینِ شرطیِ طرح را روشن می‌کنیم. کد فقط رابطه‌های متناهی در حافظه دارد و پایگاه داده‌ای ایجاد نمی‌کند.

۱. شناسهٔ حسگر چه چیزی را تعیین می‌کند؟

رابطهٔ ما سه صفت sensor، location و unit دارد. چهار رکورد تألیفی داریم: S1 در benchA با mV، همان S1 در benchB با mV، حسگر S2 در benchA با mA و S3 در benchC با mV. این‌ها فرادادهٔ ساختگی‌اند؛ اندازه‌گیری ولتاژ یا جریان نیستند. نامِ واحد، برچسبِ دامنه است و هیچ تبدیل عددی میان میلی‌ولت و میلی‌آمپر انجام نمی‌شود.

قاعدهٔ دامنه را چنین انتخاب می‌کنیم: هر شناسهٔ منطقیِ حسگر، یک واحد دارد؛ یعنی sensor واحد را تعیین می‌کند. محل می‌تواند تغییر کند یا بیش از یک ثبت مکانی داشته باشد. پس sensor به‌تنهایی کلیدِ همهٔ این رابطه نیست. وجود دو سطر برای S1، نقض قاعدهٔ واحد نیست، چون هر دو واحد یکسان دارند.

یادداشت طراحی پایگاه دادهٔ Berkeley CS186 وابستگی تابعی را با توافقِ دو رکورد بر صفاتِ سمت چپ تعریف می‌کند: در آن صورت باید بر صفات سمت راست هم توافق کنند. این تعریف دربارهٔ برابری مقدارهاست؛ شباهت نوشتاری، هم‌بستگی آماری یا این ادعا که حسگر علت فیزیکیِ واحد است، در آن دخالت ندارد.

این وابستگی را از چهار رکورد کشف نکرده‌ایم؛ آن را به‌عنوان سیاست فرض کرده‌ایم. اگر یک شناسه در دوره‌های مختلف با واحدهای متفاوت ثبت می‌شود، باید دامنهٔ شناسه یا صفتی مثل نسخهٔ پیکربندی را بازتعریف کنیم. کافی نیست یک نمونهٔ کوچک تصادفاً سازگار باشد و بعد همان قاعده را برای تمام داده‌های آینده قطعی بدانیم.

۲. بستار صفات و معیارِ تجزیهٔ دوتایی

بستارِ یک مجموعهٔ صفت، صفاتی است که با وابستگی‌های فرض‌شده از آن‌ها نتیجه می‌گیریم. از sensor آغاز می‌کنیم؛ خودش را داریم و با قاعدهٔ حاضر unit نیز اضافه می‌شود. location از این اطلاعات به دست نمی‌آید. در کد، قواعد را تا جایی تکرار می‌کنیم که صفت تازه‌ای افزوده نشود؛ چرخهٔ قواعد باعث چرخش بی‌پایان نمی‌شود.

برای دو زیرطرح که اجتماعشان کل طرح است، معیارِ بدون‌اتلافِ مبتنی بر وابستگی‌های تابعی چنین است: بستارِ اشتراک دو زیرطرح باید تمام صفاتِ دست‌کم یکی از آن‌ها را پوشش دهد. این معیارِ یادداشت Berkeley دربارهٔ تمام رابطه‌هایی است که وابستگی‌های فرض‌شده را رعایت می‌کنند. دربارهٔ تجزیهٔ چندجزئی یا قیود دیگری مانند وابستگی چندمقداری، همین تابع را حکم عمومی معرفی نمی‌کنیم.

تقسیمِ خوب، sensor/unit و sensor/location است. اشتراک sensor است و بستارش unit را هم دارد؛ بنابراین تمام زیرطرح اول تعیین می‌شود. در تقسیمِ دیگر، sensor/location و location/unit را می‌گیریم. اشتراک location است، ولی از آن نه sensor را می‌دانیم و نه unit را؛ آزمونِ طرح برای این وابستگیِ تنها، جواب منفی می‌دهد.

منفی شدنِ معیار نمی‌گوید هر نمونهٔ ممکن حتماً خراب بازسازی می‌شود. مثلاً رابطهٔ تک‌رکوردیِ آزمون، حتی با تقسیمِ دوم هم همان یک رکورد را می‌دهد. معنای منفی این است که تضمینِ همگانی تحتِ قواعدِ اعلام‌شده نداریم. برای رد چنین تضمینی، یک نمونهٔ قانونیِ دارای بازسازیِ اضافی کافی است؛ سناریوی چهاررکوردی همین نقش را دارد.

۳. کد کاملِ تصویرکردن و پیوندِ طبیعی

فایل را با نام lossless_sensor_decomposition.py ذخیره و با python lossless_sensor_decomposition.py اجرا کنید. اجرای ثبت‌شده Python 3.14.5 و فقط کتابخانهٔ استاندارد دارد. Theory را از build می‌سازیم؛ قواعد شامل دو فهرست یا تاپل از نام صفات‌اند. نام ناشناخته و تکراری رد می‌شود؛ سمتِ خالیِ وابستگی برای قاعدهٔ مقدار ثابت مجاز است.

"""Finite set relations and FD-only binary losslessness; no SQL or database."""
from dataclasses import dataclass
from itertools import combinations, product
import json
import platform


def attributes(value, allow_empty=False):
    if type(value) not in (tuple, list):
        raise TypeError('attribute names must be a list or tuple')
    if any(type(x) is not str or not x.isidentifier() for x in value):
        raise ValueError('actual nonempty identifier strings required')
    if len(set(value)) != len(value) or (not value and not allow_empty):
        raise ValueError('distinct attributes required')
    return tuple(value)


@dataclass(frozen=True)
class Theory:
    attrs: tuple
    rules: tuple

    @classmethod
    def build(cls, attrs, rules):
        attrs = attributes(attrs)
        if type(rules) not in (tuple, list):
            raise TypeError('finite rule list or tuple required')
        normalized = []
        for rule in rules:
            if type(rule) not in (tuple, list) or len(rule) != 2:
                raise ValueError('each FD requires a left and right side')
            left = frozenset(attributes(rule[0], True))
            right = frozenset(attributes(rule[1], True))
            if not (left | right) <= set(attrs):
                raise ValueError('unknown attribute in FD')
            normalized.append((left, right))
        return cls(attrs, tuple(normalized))

    def closure(self, seed):
        known = set(attributes(seed, True))
        if not known <= set(self.attrs):
            raise ValueError('unknown seed attribute')
        while True:
            previous = set(known)
            for left, right in self.rules:
                if left <= known:
                    known.update(right)
            if known == previous:
                return frozenset(known)

    def binary_lossless(self, left, right):
        left, right = set(attributes(left)), set(attributes(right))
        if left | right != set(self.attrs):
            raise ValueError('two projections must cover exactly the schema')
        common_closure = self.closure(tuple(sorted(left & right)))
        return left <= common_closure or right <= common_closure


@dataclass(frozen=True)
class Relation:
    attrs: tuple
    rows: frozenset

    @classmethod
    def build(cls, attrs, rows):
        attrs = attributes(attrs)
        if type(rows) not in (tuple, list):
            raise TypeError('finite row list or tuple required')
        result = []
        for row in rows:
            if type(row) not in (tuple, list) or len(row) != len(attrs):
                raise ValueError('row arity mismatch')
            if any(type(cell) is not str for cell in row):
                raise TypeError('actual string cells required; no NULL')
            result.append(tuple(row))
        return cls(attrs, frozenset(result))

    def project(self, names):
        names = attributes(names)
        if not set(names) <= set(self.attrs):
            raise ValueError('unknown projection attribute')
        indices = tuple(self.attrs.index(name) for name in names)
        return Relation.build(names, [tuple(row[i] for i in indices) for row in self.rows])

    def satisfies(self, left, right):
        left, right = attributes(left, True), attributes(right, True)
        if not set(left + right) <= set(self.attrs):
            raise ValueError('unknown FD attribute')
        li, ri = [self.attrs.index(x) for x in left], [self.attrs.index(x) for x in right]
        observed = {}
        for row in self.rows:
            key, value = tuple(row[i] for i in li), tuple(row[i] for i in ri)
            if key in observed and observed[key] != value:
                return False
            observed[key] = value
        return True


def natural_join(left, right):
    common = tuple(name for name in left.attrs if name in right.attrs)
    extras = tuple(name for name in right.attrs if name not in left.attrs)
    rows = []
    for a in left.rows:
        for b in right.rows:
            if all(a[left.attrs.index(name)] == b[right.attrs.index(name)] for name in common):
                rows.append(a + tuple(b[right.attrs.index(name)] for name in extras))
    return Relation.build(left.attrs + extras, rows)


def closed_superset_oracle(theory, seed):
    # Enumerate all FD-closed supersets; no forward-chaining closure loop.
    supersets = []
    for mask in range(1 << len(theory.attrs)):
        candidate = {name for i, name in enumerate(theory.attrs) if mask & (1 << i)}
        if set(seed) <= candidate and all(not left <= candidate or right <= candidate
                                          for left, right in theory.rules):
            supersets.append(candidate)
    return frozenset(set.intersection(*supersets))


def candidate_join_oracle(original, left, right):
    # Enumerate full candidate tuples and test projection membership directly.
    # Does not call natural_join or Relation.project.
    domains = [sorted({row[i] for row in original.rows}) for i in range(len(original.attrs))]
    expected = set()
    for candidate in product(*domains):
        values = dict(zip(original.attrs, candidate))
        if (tuple(values[x] for x in left.attrs) in left.rows
                and tuple(values[x] for x in right.attrs) in right.rows):
            expected.add(candidate)
    return frozenset(expected)


def rejects(call):
    try:
        call()
    except (TypeError, ValueError):
        return True
    return False


def run():
    names = ('sensor', 'location', 'unit')
    rows = [('S1', 'benchA', 'mV'), ('S1', 'benchB', 'mV'),
            ('S2', 'benchA', 'mA'), ('S3', 'benchC', 'mV')]
    relation = Relation.build(names, rows)
    theory = Theory.build(names, [(('sensor',), ('unit',))])
    sensor_unit = relation.project(('sensor', 'unit'))
    sensor_location = relation.project(('sensor', 'location'))
    location_unit = relation.project(('location', 'unit'))
    good = natural_join(sensor_unit, sensor_location).project(names)
    bad = natural_join(sensor_location, location_unit).project(names)
    spurious = bad.rows - relation.rows
    checks = {}
    checks['hand_relation_and_projection_sizes'] = (len(relation.rows), len(sensor_unit.rows), len(sensor_location.rows)) == (4, 3, 4)
    checks['hand_attribute_closures'] = (theory.closure(('sensor',)) == frozenset(('sensor', 'unit'))
                                       and theory.closure(('location',)) == frozenset(('location',)))
    checks['binary_lossless_criterion_good_and_bad'] = (theory.binary_lossless(('sensor', 'unit'), ('sensor', 'location'))
                                                      and not theory.binary_lossless(('sensor', 'location'), ('location', 'unit')))
    checks['good_projection_join_reconstructs_exactly'] = good == relation
    checks['two_spurious_rows_hand_witness'] = spurious == frozenset([('S1', 'benchA', 'mA'), ('S2', 'benchA', 'mV')]) and len(bad.rows) == 6
    checks['independent_candidate_join_membership'] = all(joined.rows == candidate_join_oracle(relation, left, right)
        for joined, left, right in [(good, sensor_unit, sensor_location), (bad, sensor_location, location_unit)])
    malformed = Relation.build(names, rows + [('S1', 'benchD', 'V')])
    checks['FD_policy_distinct_from_instance_and_violation'] = relation.satisfies(('sensor',), ('unit',)) and not malformed.satisfies(('sensor',), ('unit',))
    checks['set_semantics_duplicates_and_empty_relation'] = (Relation.build(names, rows + rows) == relation
        and natural_join(Relation.build(('sensor', 'unit'), []), sensor_location).rows == frozenset())
    chain = Theory.build(('sensor', 'kind', 'unit', 'location'),
                         [(('sensor',), ('kind',)), (('kind',), ('unit',)), (('unit',), ('kind',))])
    policies = [chain, Theory.build(chain.attrs, []), Theory.build(chain.attrs, [((), ('unit',))])]
    oracle_cases = 0; oracle_ok = True
    for policy in policies:
        for mask in range(16):
            seed = tuple(x for i, x in enumerate(policy.attrs) if mask & (1 << i))
            oracle_ok &= policy.closure(seed) == closed_superset_oracle(policy, seed)
            oracle_cases += 1
    checks['48_closed_superset_oracle_cases_ONE_group'] = bool(oracle_ok) and oracle_cases == 48
    checks['closure_transitivity_rule_order_and_constant'] = (chain.closure(('sensor',)) == frozenset(('sensor', 'kind', 'unit'))
        and Theory.build(chain.attrs, [(tuple(a), tuple(b)) for a, b in reversed(chain.rules)]).closure(('sensor',)) == chain.closure(('sensor',))
        and policies[2].closure(()) == frozenset(('unit',)))
    tiny_universe = list(product(('S0', 'S1'), ('L0', 'L1'), ('U0', 'U1')))
    legal = 0; reconstruction_ok = True
    for mask in range(256):
        candidate = Relation.build(names, [row for i, row in enumerate(tiny_universe) if mask & (1 << i)])
        if candidate.satisfies(('sensor',), ('unit',)):
            restored = natural_join(candidate.project(('sensor', 'unit')), candidate.project(('sensor', 'location'))).project(names)
            reconstruction_ok &= restored == candidate
            legal += 1
    checks['all_256_tiny_instances_fd_legal_subset_ONE_group'] = bool(reconstruction_ok) and legal > 0
    singleton = Relation.build(names, [rows[0]])
    checks['bad_schema_can_accidentally_reconstruct_one_instance'] = (
        natural_join(singleton.project(('sensor', 'location')), singleton.project(('location', 'unit'))).project(names) == singleton)
    checks['input_and_schema_boundaries'] = all([
        rejects(lambda: Theory.build(names, [(('absent',), ('unit',))])),
        rejects(lambda: theory.binary_lossless(('sensor',), ('unit',))),
        rejects(lambda: theory.closure(('sensor', 'sensor'))),
        rejects(lambda: Relation.build(('sensor', 'sensor'), [])),
        rejects(lambda: Relation.build(names, [('S1', 'benchA', None)])),
        rejects(lambda: Relation.build(names, [('S1', 'benchA')])),
        rejects(lambda: relation.project(('absent',))),
        rejects(lambda: relation.satisfies(('absent',), ('unit',))),
    ])
    assert all(type(value) is bool and value for value in checks.values()), checks
    return {'python': platform.python_version(), 'dependencies': 'standard library only',
            'scope': 'finite set relations; FD-only two-component decomposition; no SQL or NULL',
            'schema': names, 'assumed_fd': 'sensor -> unit', 'original_rows': sorted(relation.rows),
            'good_reconstructed_rows': sorted(good.rows), 'bad_reconstructed_count': len(bad.rows),
            'spurious_rows': sorted(spurious), 'closure_sensor': sorted(theory.closure(('sensor',))),
            'closed_superset_oracle_cases_inside_one_group': oracle_cases,
            'tiny_relations_enumerated_inside_one_group': 256, 'FD_legal_tiny_relations': legal, 'checks': checks}


if __name__ == '__main__':
    print(json.dumps(run(), ensure_ascii=False, indent=2))

Relation نیز باید از build ساخته شود. هر رکورد طولِ دقیقِ طرح را دارد و هر خانه str واقعی است؛ None، عدد و بولی به رشته تبدیل نمی‌شوند. نام صفات باید شناسهٔ معتبر و یکتا باشد. رشتهٔ تهی در خانه، صرفاً یک مقدار رشته‌ای است و مفهوم NULL ندارد. ساختِ مستقیم dataclass با دادهٔ ناسازگار، مسیر پشتیبانی‌شدهٔ این درس نیست.

رابطه را مجموعه می‌گیریم: تکرارِ همان رکورد حذف می‌شود و ترتیبِ ذخیرهٔ سطرها معنا ندارد. برای نمایش خروجی، سطرها صریح مرتب می‌شوند. تصویر یا projection فقط صفاتِ خواسته‌شده را نگه می‌دارد؛ ممکن است چند سطرِ اولیه پس از تصویر به یک سطر تبدیل شوند. پیوند طبیعی روی تمام نام‌های مشترک برابری می‌خواهد و سپس صفاتِ غیرمشترک را کنار هم می‌گذارد.

این محاسبه، معنای bag و NULL در SQL را پیاده نمی‌کند. درس تعداد ردیف JOIN و مقدارهای تهی آن تفاوت‌های اجرایی را بررسی می‌کند. همچنین قیود رکورد حسگر در SQLite دربارهٔ نوع و تبدیلِ ذخیره‌سازی است؛ اینجا مسئلهٔ تازه، بازیابیِ اطلاعات از دو تصویرِ یک رابطهٔ مجموعه‌ای است.

۴. رکورد ساختگی و مرجعِ مستقلِ بستار

در تقسیم خوب، سه زوج sensor/unit و چهار زوج sensor/location داریم؛ پیوند دوباره همان چهار رکورد اولیه را می‌سازد. در تقسیم نامطمئن، benchA با دو واحد mV و mA دیده می‌شود. پیوند روی محل، هر یک از دو حسگرِ آن محل را با هر دو واحد همراه می‌کند؛ دو رکورد اضافه پدید می‌آید و اندازهٔ نتیجه شش می‌شود.

{
  "python": "3.14.5",
  "dependencies": "standard library only",
  "scope": "finite set relations; FD-only two-component decomposition; no SQL or NULL",
  "schema": [
    "sensor",
    "location",
    "unit"
  ],
  "assumed_fd": "sensor -> unit",
  "original_rows": [
    [
      "S1",
      "benchA",
      "mV"
    ],
    [
      "S1",
      "benchB",
      "mV"
    ],
    [
      "S2",
      "benchA",
      "mA"
    ],
    [
      "S3",
      "benchC",
      "mV"
    ]
  ],
  "good_reconstructed_rows": [
    [
      "S1",
      "benchA",
      "mV"
    ],
    [
      "S1",
      "benchB",
      "mV"
    ],
    [
      "S2",
      "benchA",
      "mA"
    ],
    [
      "S3",
      "benchC",
      "mV"
    ]
  ],
  "bad_reconstructed_count": 6,
  "spurious_rows": [
    [
      "S1",
      "benchA",
      "mA"
    ],
    [
      "S2",
      "benchA",
      "mV"
    ]
  ],
  "closure_sensor": [
    "sensor",
    "unit"
  ],
  "closed_superset_oracle_cases_inside_one_group": 48,
  "tiny_relations_enumerated_inside_one_group": 256,
  "FD_legal_tiny_relations": 49,
  "checks": {
    "hand_relation_and_projection_sizes": true,
    "hand_attribute_closures": true,
    "binary_lossless_criterion_good_and_bad": true,
    "good_projection_join_reconstructs_exactly": true,
    "two_spurious_rows_hand_witness": true,
    "independent_candidate_join_membership": true,
    "FD_policy_distinct_from_instance_and_violation": true,
    "set_semantics_duplicates_and_empty_relation": true,
    "48_closed_superset_oracle_cases_ONE_group": true,
    "closure_transitivity_rule_order_and_constant": true,
    "all_256_tiny_instances_fd_legal_subset_ONE_group": true,
    "bad_schema_can_accidentally_reconstruct_one_instance": true,
    "input_and_schema_boundaries": true
  }
}

دو رکوردِ ساختگیِ افزوده دقیقاً S1/benchA/mA و S2/benchA/mV هستند. یادداشت lossless join در تمرین طراحی UMBC نیز مفهومِ رکوردِ اضافی پس از پیوند را توضیح می‌دهد. نمونه، شناسه‌ها و کد حاضر مستقل‌اند؛ مسئله، بیشتر شدنِ دانشِ واقعی دربارهٔ حسگر نیست، بلکه از بین رفتنِ ارتباطِ درست میان سه مقدار است.

مرجعِ مستقلِ بستار، همهٔ زیرمجموعه‌های صفات را بررسی می‌کند. از میانِ مجموعه‌های بسته‌ای که بذر را در بر دارند، اشتراک می‌گیرد. این مرجع، حلقهٔ رو به جلوی closure را صدا نمی‌زند. سه سیاستِ کوچک، شامل زنجیره، چرخه و وابستگیِ با سمت چپِ تهی، برای شانزده بذر بررسی می‌شوند؛ مجموعِ چهل‌وهشت مقایسه یک گروه آزمون است.

مرجعِ دوم برای پیوند، همهٔ رکوردهای کاملِ ممکن از دامنه‌های همین نمونه را می‌سازد و عضویتِ دو تصویر را مستقیم می‌سنجد؛ از natural_join استفاده نمی‌کند. همچنین همهٔ ۲۵۶ رابطه روی سه دامنهٔ دوعضوی بررسی می‌شوند. چهل‌ونه نمونه وابستگی sensor به unit را رعایت می‌کنند و تقسیمِ خوب برای همهٔ آن‌ها بازسازیِ دقیق دارد؛ این مجموعه نیز فقط یک گروه است.

تعداد واقعی گروه‌های نام‌دار سیزده است. این اجرا، آزمونِ محدودِ پیاده‌سازی و شاهدِ عددی است؛ اثباتِ قضیه از شمارِ نمونه‌ها به دست نمی‌آید. نگه‌داشتنِ وابستگی‌ها پس از تجزیه، انتخاب بهترین شکلِ نرمال و کاراییِ اتصال، مسائلِ جدا هستند. هیچ‌کدام در این برنامه به‌طور کامل حل یا اندازه‌گیری نشده‌اند.

۵. چهار پرسش پاسخ‌دار دربارهٔ بازسازی

پرسش اول: آیا sensor در رابطهٔ اولیه کلید است؟ پاسخ: خیر؛ S1 دو محل دارد. sensor فقط unit را تعیین می‌کند. با صفاتِ حاضر، زوج sensor/location همهٔ خانه‌های رکورد را تعیین می‌کند؛ تعریف واحد را با یکتایی تمام رکورد اشتباه نمی‌گیریم.

پرسش دوم: چرا اتصال روی location دو رکورد اضافه می‌سازد؟ پاسخ: benchA دو حسگر و دو واحد دارد؛ دو تصویر دیگر نشان نمی‌دهند کدام واحد با کدام حسگر همراه بوده است. پیوند چهار ترکیب می‌سازد، درحالی‌که فقط دو ترکیبِ مربوط به این محل اولیه بودند.

پرسش سوم: موفقیت رابطهٔ تک‌رکوردی، تقسیم دوم را تضمین می‌کند؟ پاسخ: خیر؛ فقط همان نمونه بازسازی شده است. معیارِ طرح باید برای تمام نمونه‌های قانونی برقرار باشد و نمونهٔ چهاررکوردی، نبود این تضمین را آشکار می‌کند.

پرسش چهارم: اگر S1 با واحد V هم ثبت شود، قاعده چه می‌شود؟ پاسخ: روش satisfies نقضِ نمونه را گزارش می‌کند؛ داشتنِ Theory سازگاریِ داده را تحمیل نمی‌کند. باید رکورد را رد یا دامنهٔ شناسه و نسخه را بازطراحی کرد. منابع در ۲۶ مهر ۱۴۰۵ خوانده شدند؛ تاریخ انتشار دقیق صفحه‌ها نامعلوم است و از نام دوره یا موعد تکلیف حدس زده نشده است.

منابع و مطالعهٔ بیشتر

• Berkeley CS186؛ وابستگی تابعی، بستار و معیار تجزیهٔ بدون‌اتلاف
• UMBC CMSC461؛ یادداشت lossless join در تمرین طراحی

بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.